SUDOKU SOLVING STRATEGY USING INTEGER PROGRAMMING

Let us consider getting the solution to the above Sudoku problem in this article.

Importing the Package

from gurobipy import *

Setting the input grid

Grid = [
[0,0,0, 1,0,0, 0,0,0],
[0,2,4, 0,5,0, 0,0,0],
[0,0,0, 0,8,0, 3,7,5],

[9,0,0, 0,0,0, 4,0,0],
[0,7,0, 0,0,0, 0,3,0],
[0,0,2, 0,0,0, 0,0,8],

[1,5,8, 0,9,0, 0,0,0],
[0,0,0, 0,6,0, 9,1,0],
[0,0,0, 0,0,3, 0,0,0]]

#N represents the Big Square comprised of 9 smaller squares
N = range(9)

#K represents the numbers 1-9
K = range(1,10)

Setting the model

m = Model()

Defining the Variable

X = {(i,j,k): m.addVar(vtype=GRB.BINARY) for i in N for j in N for k in K}

Defining the Constraints

CONSTRAINT 1:

i,j,k is preassigned in the grid

PreAssign = {
    (i,j): m.addConstr(X[i,j,Grid[i][j]]==1)
    for i in N for j in N if Grid[i][j]>0}

CONSTRAINT 2:

Only one number in each cell

OnePerSquare = {
    (i,j): m.addConstr(quicksum(X[i,j,k] for k in K)==1)
    for i in N for j in N}

CONSTRAINT 3:

Each row must have every number 1–9

EachValueInRow = {
    (i,k): m.addConstr(quicksum(X[i,j,k] for j in N)==1)
    for i in N for k in K}

CONSTRAINT 4:

Each column must have every number 1–9

EachValueInCol = {
    (j,k): m.addConstr(quicksum(X[i,j,k] for i in N)==1)
    for j in N for k in K}

EachValueInSubSquares = {
    (ii,jj,k): m.addConstr(quicksum(X[i,j,k] 
                        for i in range(3*ii,3*ii+3)
                        for j in range(3*jj,3*jj+3))==1)
    for ii in range(3) for jj in range(3) for k in K}

OPTIMIZED RESULT

m.optimize()
print('---+---+---')
for i in N:
    if i==3 or i==6:
        print('---+---+---')
    for j in N:
        if j==3 or j==6:
            print('|', end='')
        for k in K:
            if X[i,j,k].x > 0.9:
                print(k,sep='',end='')
    print('')
print('---+---+---')
Gurobi Optimizer version 9.0.1 build v9.0.1rc0 (win64)
Optimize a model with 346 rows, 729 columns and 2938 nonzeros
Model fingerprint: 0x125478e4
Variable types: 0 continuous, 729 integer (729 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [0e+00, 0e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 1e+00]
Presolve removed 346 rows and 729 columns
Presolve time: 0.04s
Presolve: All rows and columns removed

Explored 0 nodes (0 simplex iterations) in 0.06 seconds
Thread count was 1 (of 8 available processors)

Solution count 1: 0 

Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
---+---+---
385|176|249
724|359|861
691|482|375
---+---+---
913|827|456
876|945|132
542|631|798
---+---+---
158|794|623
237|568|914
469|213|587
---+---+---

Basically, the Sudoku solution for this puzzle from the above output is as below:

*This algorithm can solve any Sudoku puzzle by just inputting the preassigned values in the grid.