Recently, I am learning about linear optimization using python.

From Wiki..

*Sudoku is a logic-based, combinatorial number-placement puzzle. The objective is to fill 9 x 9 grid with digits so that each column, each row, and each of the 3 x 3 subgrids that compose the grid contains all of the digits from 1 to 9.*

I used python library named “pulp” to solve the problem.

https://pythonhosted.org/PuLP/index.html

For convenience, I used 4 x 4 grid contains 2 x 2 subgrid problem.

At first, I got partially filled box.

+----+----+ | |4 | | | 1 | +----+----+ |4 | | |2 1 | | +----+----+

To use pulp, user need to set objective function at first. In this problem. Objective function is set 0. Because Sudoku does not need minimize or maximize the objective function.

Vals, Rows, Cols are list. And Boxes represents the grid.

LpVariable.dicts creates a dictionary of LP variables.

So, following code,

LpVariable.dicts( “test”, ( [1,2],[3,4] ), 0,1, LpInteger )

returns

{1: {3: test_1_3, 4: test_1_4}, 2: {3: test_2_3, 4: test_2_4}}.

First argument is name that is used prefix and second is indexs and third and forth is lower and upper bound of the variables.

I used LpInteger, so each variable will take 0 or 1.

To solve the problem the code make 4 x 4 x 4, total 64 variables.

from pulp import * Sequence = [ str(i) for i in range(1,5) ] Vals = Sequence Rows = Sequence Cols = Sequence Boxes = [] for i in range( 2 ): for j in range( 2 ): Boxes += [ [ (Rows[ 2*i + k ], Cols[ 2*j + l]) for k in range( 2) for l in range( 2 ) ] ] prob = LpProblem( "sudoku4x4", LpMinimize ) choices = LpVariable.dicts( "choice",( Vals, Rows, Cols ), 0,1, LpInteger ) # set problem prob += 0, 'objective function'

Next, set constrain.

There are 4 variables for each square. In the each row and column only one of them can take value of “1”. And input default conditions.

# set constrain 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['4']['1']['3'] == 1 prob += choices['1']['2']['4'] == 1 prob += choices['4']['3']['1'] == 1 prob += choices['2']['4']['1'] == 1 prob += choices['1']['4']['2'] == 1

Now ready to solve the problem.

prob.solve() print( "status:", LpStatus[prob.status] ) f = open( "sudokuout.txt", "w" ) for r in Rows: if r == "1" or r == "3": f.write( "+----+----+\n" ) for c in Cols: for v in Vals: if value( choices[v][r][c] ) == 1: if c == "1" or c == "3": f.write( "|" ) f.write( v+" " ) if c == "4": f.write('|\n') f.write( "+----+----+\n" ) f.close()

Check the outputfile.

The problem was solved.

iwatobipen$ cat sudokuout.txt

+----+----+

|1 2 |4 3 |

|3 4 |2 1 |

+----+----+

|4 3 |1 2 |

|2 1 |3 4 |

+----+----+