3.5.1 A Sudoku Instance (sudokuP)

Run LPL Code  ,  PDF Document

Problem

The Sudoko is a well known game. Its rules are simple: “Fill in the grid (see, for example, Figure 5) so that every row, every column, and every 3 × 3 subblock contains the digits 1 to 9.”. The modeling has been explain in my Puzzlebook. An implementation can be found at sudoku.


PIC

Figure 5: A Sudoku Instance

Modeling Steps

A mathematical modeling of this problem is as follows :

∑
    xi,j,k = 1     forall i,j ∈ I
∑ k
    xi,j,k = 1     forall i,k ∈ I
  j
∑
    xi,j,k = 1     forall j,k ∈ I
∑ i
    xi′,j′,k = 1   forall i,k ∈ I
  j
                withi′ = i - (i - 1) mod  3 + ⌈(j - 1)∕3⌉
                     ′
                andj  = 3(i - 1)  mod  3 + (j - 1)  mod  3 + 1
xi,j,k = 1        forall i,j,k ∈ I,Pi,j = k
xi,j,k ∈ {0,1}    forall i,j,k ∈ I
I =  {1,...,9}

The first constraint make sure that in every cell exactlyone digit is placed. The second and thrid constraints garantuees that on each row and column every digit occurs exactly once, and the fourth constraint requires that in each 3 × 3 sub-block every digit occurs. Finally, the given entries must be set.

Further Comments

The script uses a default solver, if we want to use a different solver, we can modify the script as follows:

  import pulp as pl
  path_to_cplex = r’c:' ....' cplex.exe’
  solver = pl.CPLEX_CMD(path=path_to_cplex)
  ...
  result = model.solve(solver)

Note the concise form of writing the output in LPL.

LPL code (run sudokuP)

model sudoku "A Sudoku Instance"; 
  set i,j,k := 1..9; 
  parameter P{i,j}  := [5 3 0 0 7 0 0 0 0 
                        6 0 0 1 9 5 0 0 0 
                        0 9 8 0 0 0 0 6 0 
                        8 0 0 0 6 0 0 0 3 
                        4 0 0 8 0 3 0 0 1 
                        7 0 0 0 2 0 0 0 6 
                        0 6 0 0 0 0 2 8 0 
                        0 0 0 4 1 9 0 0 5 
                        0 0 0 0 8 0 0 7 9]; 
  binary variable x{i,j,k} "k is in cell (i,j)?"; 
  constraint 
    N{i,j}: sum{k} x = 1 "In each cell only one k"; 
    R{i,k}: sum{j} x = 1 "Every k in each row i"; 
    C{j,k}: sum{i} x = 1 "Every k in each column j"; 
    B{i,k}: sum{j}       //subblocks 
      x[i-(i-1)%3+Trunc((j-1)/3), 3*(i-1)%3+(j-1)%3+1, k] = 1; 
    F{i,j,k|P[i,j]=k}: x = 1 ; 
  solve; 
  integer parameter X{i,j} := argmax{k} x; 
  Write('+-------+-------+-------+' n'); 
  Write{i}('| %s| %s| %s|' n%s', 
    Format{j|j<=3}('%1d ',X), 
    Format{j|4<=j<=6}('%1d ',X), 
    Format{j|j>=7}('%1d ',X), 
    if(i=3 or i=6 or i=9, 
      Format('+-------+-------+-------+' n'),'')); 
end

Python/PuLP code (download sudokuP.py)

# Authors: Antony Phillips, Dr Stuart Mitcehll 
from pulp import * 
Sequence = ["1", "2", "3", "4", "5", "6", "7", "8", "9"] 
Vals = Sequence 
Rows = Sequence 
Cols = Sequence 
Boxes =[] 
for i in range(3): 
  for j in range(3): 
    Boxes += [[(Rows[3*i+k],Cols[3*j+l]) for k in range(3) for l in range(3)]] 
 
# the model 
prob = LpProblem("Sudoku Problem",LpMinimize) 
choices = LpVariable.dicts("Choice",(Vals,Rows,Cols),0,1,LpInteger) 
prob += 0, "Arbitrary Objective Function" 
for r in Rows: 
  for c in Cols: 
    prob += lpSum([choices[v][r][c] for v in Vals]) == 1, "" 
for v in Vals: 
  for r in Rows: 
    prob += lpSum([choices[v][r][c] for c in Cols]) == 1,"" 
  for c in Cols: 
    prob += lpSum([choices[v][r][c] for r in Rows]) == 1,"" 
  for b in Boxes: 
    prob += lpSum([choices[v][r][c] for (r,c) in b]) == 1,"" 
prob += choices["5"]["1"]["1"] == 1,"" 
prob += choices["6"]["2"]["1"] == 1,"" 
prob += choices["8"]["4"]["1"] == 1,""

The same output of LPL and PuLP is as follows:

  +-------+-------+-------+
  | 5 3 4 | 6 7 8 | 9 1 2 |
  | 6 7 2 | 1 9 5 | 3 4 8 |
  | 1 9 8 | 3 4 2 | 5 6 7 |
  +-------+-------+-------+
  | 8 5 9 | 7 6 1 | 4 2 3 |
  | 4 2 6 | 8 5 3 | 7 9 1 |
  | 7 1 3 | 9 2 4 | 8 5 6 |
  +-------+-------+-------+
  | 9 6 1 | 5 3 7 | 2 8 4 |
  | 2 8 7 | 4 1 9 | 6 3 5 |
  | 3 4 5 | 2 8 6 | 1 7 9 |
  +-------+-------+-------+

... continue with Phyton code

 
prob += choices["4"]["5"]["1"] == 1,"" 
prob += choices["7"]["6"]["1"] == 1,"" 
prob += choices["3"]["1"]["2"] == 1,"" 
prob += choices["9"]["3"]["2"] == 1,"" 
prob += choices["6"]["7"]["2"] == 1,"" 
prob += choices["8"]["3"]["3"] == 1,"" 
prob += choices["1"]["2"]["4"] == 1,"" 
prob += choices["8"]["5"]["4"] == 1,"" 
... some lines have been cut ... 
prob += choices["6"]["6"]["9"] == 1,"" 
prob += choices["5"]["8"]["9"] == 1,"" 
prob.writeLP("Sudoku.lp") 
prob.solve() 
 
# the output 
sudokuout = open('sudokuout.txt','w') 
for r in Rows: 
    if r == "1" or r == "4" or r == "7": 
        sudokuout.write("+-------+-------+-------+' n") 
    for c in Cols: 
        for v in Vals: 
            if value(choices[v][r][c])==1: 
                if c == "1" or c == "4" or c =="7": 
                    sudokuout.write("| ") 
                sudokuout.write(v + " ") 
                if c == "9": 
                    sudokuout.write("|' n") 
sudokuout.write("+-------+-------+-------+") 
sudokuout.close() 
print ("Status:", LpStatus[prob.status]) 
print ("Solution Written to sudokuout.txt")