Creating Sudoku Solver with Python and Pyomo in Easy Steps

Solving one of the popular number placement puzzles in newspapers using constraint optimization

Classic 9x9 Sudoku Puzzle

The classic Sudoku game involves a grid of 81 squares. The grid is divided into nine blocks, each containing nine squares.

The rules of the filling the grid are simple:

1. Each of the nine blocks (each 3x3 bold bordered squares in above image) has to contain all the numbers 1–9 within its squares
2. Each number can only appear once in a row, column or block

Mathematical formulation

Lets consider a 3D array, X, with indices as i, j, k. Where Xijk assumes the value of 1, if (i, j) of the sudoku matrix contains k, and 0 otherwise. With values of i, j and k ranging between the integers 1–9.

Image showing the placement of number 3 on sudoku grid with value of Xijk assuming 1, and 0 therwise

Constraint 1: Row constraint i.e., no repetition of numbers in each row of sudoku grid

Constraint 2: Column constraint i.e., no repetition of numbers in each column of sudoku grid

Constraint 3: Block constraint i.e., no repetition of numbers in each block

Constraint 4: Constraint for not leaving any cell empty without assignment

Constraint 5: Constraint for fixing already provided grid cells i.e., constraint for know cell values

Objective Function: For solving sudoku there is no function which we want to minimize or maximize. Due to this fact sudoku problem can be considered as satisfiability or feasibility problem i.e., the objective here is to just find a basic feasible solution satisfying defined constraints. Hence we can have a constant/arbitrary objective function to solve the purpose (value of 1 is considered as objective function in the current article).

Implementation in Python

I have used Pyomo along with CBC solver for solving above formulated linear programming problem. You can download CBC solver from COIN-OR repository which provides many open source solvers for solving optimization problems.

Creating sample sudoku grid

Lets take a sample sudoku grid to solve with zero replaced for missing cells.

Sample sudoku grid to solve

### Grid size
N = list(range(1, 9 + 1))
### Creating grid
completeGrid = []
for i in N:
    for j in N:
        completeGrid.append((i,j))
completeGrid = pd.DataFrame(completeGrid, columns = ['i', 'j'])
### Known cell values
data = [(1, 7, 2), (2, 2, 8), (2, 6, 7), (2, 8, 9),
  (3, 1, 6), (3, 3, 2), (3, 7, 5), (4, 2, 7),
  (4, 5, 6), (5, 4, 9), (5, 6, 1), (6, 5, 2), 
  (6, 8, 4), (7, 3, 5), (7, 7, 6), (7, 9, 3),
  (8, 2, 9), (8, 4, 4), (8, 8, 7), (9, 3, 6)]
data = pd.DataFrame(data, columns = ['i', 'j', 'k'])
###
finalGrid = pd.merge(completeGrid, data, how = 'left')
finalGrid = finalGrid.fillna(0)

Defining constraints and objective function

### Defining model
model = ConcreteModel()
model.X = Var(N, N, N, within = Binary)
### Definding constraints
## Row constraint
model.row_constr = ConstraintList()
for i in N:
    for k in N:
        model.row_constr.add(1 == sum(model.X[i, j, k] for j in N))
        
## Column constraint
model.col_constr = ConstraintList()
for j in N:
    for k in N:
        model.col_constr.add(1 == sum(model.X[i, j, k] for i in N))
        
## Block constraint
model.block_constr = ConstraintList()
for i in list(range(1, 9, 3)):
    for j in list(range(1, 9, 3)):
        for k in N:
            model.block_constr.add(1 == sum(model.X[p, q, k] for p in range(i, i+3) for q in range(j, j+3)))
            
## Constraint for assigning all cells
model.allCell_constr = ConstraintList()
for i in N:
    for j in N:
        model.allCell_constr.add(1 == sum(model.X[i, j, k] for k in N))
        
## Constraint for assigning known cells
model.knownCell_constr = ConstraintList()
for i, j, k in zip(finalGrid['i'], finalGrid['j'], finalGrid['k']):
    if k != 0:
        #print(k)
        model.knownCell_constr.add(1 == model.X[i,j,k])
        
## Defining objective function
model.Obj = Objective(expr = 1)

Solving the puzzle

## Solving 
opt = SolverFactory('cbc', executable = '')
opt.solve(model)
### Looking at final solved grid
solutionDf = pd.DataFrame({
'i': [i[0] for i in model.X.iterkeys()], 
'j': [i[1] for i in model.X.iterkeys()], 
'k': [i[2] for i in model.X.iterkeys()], 
'assignment': [i.value for i in model.X.itervalues()]})
solutionDf = solutionDf[solutionDf['assignment'] == 1]
solutionDf.pivot(index = 'i', columns = 'j', values = 'k')

Input puzzle (left) and Output Puzzle (right)

Please click here to view Google Collab notebook with end to end implementation.

I appreciate any feedback and constructive criticism. Happy learning!