Sudoku with IP

Table of Contents

• 1  Solving Sudoku with Integer Programming
• 2  Solve using MIP
• 3  Solve using Gurobi

Solving Sudoku with Integer Programming¶

Sudoku is played on a grid of 9 x 9 spaces. Within the rows and columns are 9 “squares” (made up of 3 x 3 spaces). Each row, column and square (9 spaces each) needs to be filled out with the numbers 1-9, without repeating any numbers within the row, column or square. https://sudoku.com/how-to-play/sudoku-rules-for-complete-beginners/

Basic sudoku has size 9 x 9 with number 1-9 as the filling. However, the size and the filling can be changed.

Solve sudoku with Integer Programming

Define :

• $N$ is a set of sudoku filling
  • $N=[1,2,3,4,5,6,7,8,9]$
  • $N=[$a,b,c,d,e,f,g,h,i,j$]$
  • $N=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]$
  • etc
• $R$ is a set of sudoku row
  • $R=[1,2,3,4,5,6,7,8,9]$
  • etc
• $C$ is a set of sudoku columns
  • $C=[1,2,3,4,5,6,7,8,9]$
  • etc

Define decision variable $x_{n,r,c}$, $n\in N,r\in R,c\in C$ $$\displaystyle x_{n,r,c}=\begin{cases}1, \text{ if }n\text{ is in}(r,c) \\0, \text{ otherwise}\end{cases}$$

Constraint:

• For each row and columns, $n$ only appear once
  • $\displaystyle \forall r\in R,\forall c\in C : \sum_{n\in N}x_{n,r,c}=1$
• For each square $(3\times 3)$ (for sudoku with size $9\times 9$), $n$ only appear once
  • $\displaystyle \forall n\in N,\forall s\in [0,3,6],\forall t\in [0,3,6] : \sum_{r\in [1,2,3]}\sum_{c\in [1,2,3]}x_{n,r+s,c+t}=1$
• For each known $n$ with coordinat $(r,c)$ on the board
  • $\forall (n,r,c)$ known, $x_{n,r,c}=1$

Now we just need to solve the problem with whatever method or tools.

Solve using MIP¶

In [1]:

import itertools
import pandas as pd
import time
import mip

In [2]:

def solve_sudo_mip(fname='sudoku.xlsx',sheetname='test'):
    sudo=pd.read_excel(fname, sheet_name =sheetname,index_col=0)
    N=[i for i in range(1,10)] ; R=list(sudo.index) ; C=list(sudo.keys())
    print('Solving Sudoku With IP');
    print(pd.DataFrame([['-' if pd.isna(sudo[c][r])==True else int(sudo[c][r]) for r in R] for c in C], index=R, columns=C).T)
    #N=['a','b','c','d','e','f','g','h','i'] ; 
    m = mip.Model("SUDOKU")
    x = [[[m.add_var(var_type=mip.BINARY) for c in C] for r in R] for n in N]
    for r,c in [p for p in itertools.product(R,C)]:
        m.add_constr( mip.xsum(x[N.index(n)][R.index(r)][C.index(c)] for n in N) == 1 )
    for n,s,t in [p for p in itertools.product(N,[0,3,6],[0,3,6])]:
        m.add_constr( mip.xsum(mip.xsum(x[N.index(n)][R.index(r)][C.index(c)] for r in [s+1,s+2,s+3]) for c in [t+1,t+2,t+3]) == 1 )    
    for r,c in [p for p in itertools.product(R,C)]:
        if pd.isna(sudo[c][r])==False:
            m.add_constr(x[N.index(int(sudo[c][r]))][R.index(r)][C.index(c)]==1)
    tic = time.perf_counter()
    m.optimize()
    toc = time.perf_counter()
    print(f"\nOptimization Time {toc - tic:0.4f} seconds")
    sudomu = pd.DataFrame([[[n for n in N if x[N.index(n)][R.index(r)][C.index(c)].x>0] for r in R] for c in C])
    return sudomu.T

In [3]:

solve_sudo_mip(fname='sudoku.xlsx',sheetname='test')

Solving Sudoku With IP
   1  2  3  4  5  6  7  8  9
1  -  -  -  -  -  -  5  -  2
2  8  -  -  -  9  -  -  -  -
3  -  -  -  -  -  -  6  -  -
4  7  -  -  2  -  -  -  -  -
5  -  -  -  1  -  5  -  -  -
6  -  3  -  -  -  -  -  9  -
7  -  1  5  -  -  -  -  -  -
8  -  -  -  -  4  -  -  3  -
9  6  -  2  -  -  -  -  -  -

Optimization Time 0.0281 seconds

Out[3]:

	0	1	2	3	4	5	6	7	8
0	[3]	[9]	[7]	[2]	[3]	[6]	[5]	[9]	[2]
1	[8]	[5]	[6]	[7]	[9]	[8]	[1]	[7]	[4]
2	[4]	[1]	[2]	[4]	[5]	[1]	[6]	[3]	[8]
3	[7]	[9]	[6]	[2]	[8]	[9]	[8]	[3]	[6]
4	[4]	[5]	[2]	[1]	[3]	[5]	[1]	[4]	[2]
5	[8]	[3]	[1]	[7]	[4]	[6]	[7]	[9]	[5]
6	[7]	[1]	[5]	[2]	[6]	[3]	[7]	[8]	[4]
7	[8]	[4]	[3]	[1]	[4]	[9]	[1]	[3]	[2]
8	[6]	[9]	[2]	[5]	[7]	[8]	[6]	[9]	[5]

In [4]:

solve_sudo_mip(fname='sudoku.xlsx',sheetname='test2')

Solving Sudoku With IP
   1  2  3  4  5  6  7  8  9
1  8  -  1  -  -  -  -  -  9
2  -  -  -  -  -  2  -  3  -
3  7  -  -  5  -  -  -  -  -
4  9  -  -  -  -  -  -  -  1
5  -  -  -  3  -  -  5  -  -
6  -  -  -  -  -  4  -  -  -
7  -  -  -  -  1  -  2  -  -
8  -  2  -  -  -  -  -  4  -
9  -  -  -  -  8  -  -  -  -

Optimization Time 0.0027 seconds

Out[4]:

	0	1	2	3	4	5	6	7	8
0	[8]	[3]	[1]	[4]	[3]	[9]	[6]	[2]	[9]
1	[9]	[5]	[6]	[7]	[6]	[2]	[7]	[3]	[1]
2	[7]	[4]	[2]	[5]	[8]	[1]	[4]	[8]	[5]
3	[9]	[6]	[7]	[5]	[1]	[9]	[8]	[3]	[1]
4	[4]	[5]	[2]	[3]	[8]	[2]	[5]	[9]	[2]
5	[8]	[3]	[1]	[7]	[6]	[4]	[7]	[4]	[6]
6	[7]	[5]	[1]	[2]	[1]	[3]	[2]	[3]	[8]
7	[8]	[2]	[3]	[4]	[6]	[9]	[1]	[4]	[7]
8	[4]	[9]	[6]	[5]	[8]	[7]	[6]	[9]	[5]

Solve using Gurobi¶

In [1]:

import itertools
import pandas as pd
import time
import gurobipy as gp

In [2]:

def solve_sudo_gurobi(fname='sudoku.xlsx',sheetname='test'):
    sudo=pd.read_excel(fname, sheet_name =sheetname,index_col=0)
    N=[i for i in range(1,10)] ; R=list(sudo.index) ; C=list(sudo.keys())
    print('Solving Sudoku With IP');
    print(pd.DataFrame([['-' if pd.isna(sudo[c][r])==True else int(sudo[c][r]) for r in R] for c in C], index=R, columns=C).T)
    m = gp.Model("SUDOKU")
    x = m.addVars(N,R,C, vtype=gp.GRB.BINARY, name = 'x')
    for r,c in [p for p in itertools.product(R,C)]:
        m.addConstr( gp.quicksum(x[n,r,c] for n in N) == 1 )
    for n,s,t in [p for p in itertools.product(N,[0,3,6],[0,3,6])]:
        m.addConstr( gp.quicksum(x[n,s+r,t+c] for r,c in [p for p in itertools.product([1,2,3],[1,2,3])]) == 1 )
    for r,c in [p for p in itertools.product(R,C)]:
        if pd.isna(sudo[c][r])==False:
            m.addConstr(x[int(sudo[c][r]),r,c]==1, name='Constraint From Excel')
    m.setParam('OutputFlag', False)
    tic = time.perf_counter()
    m.optimize()
    toc = time.perf_counter()
    print(f"\nOptimization Time {toc - tic:0.4f} seconds")
    return pd.DataFrame([[[n for n in N if x[n,r,c].x>0][0] for r in R] for c in C], index=list(sudo.index), columns=list(sudo.index)).T    

In [3]:

solve_sudo_gurobi(fname='sudoku.xlsx',sheetname='test')

Solving Sudoku With IP
   1  2  3  4  5  6  7  8  9
1  -  -  -  -  -  -  5  -  2
2  8  -  -  -  9  -  -  -  -
3  -  -  -  -  -  -  6  -  -
4  7  -  -  2  -  -  -  -  -
5  -  -  -  1  -  5  -  -  -
6  -  3  -  -  -  -  -  9  -
7  -  1  5  -  -  -  -  -  -
8  -  -  -  -  4  -  -  3  -
9  6  -  2  -  -  -  -  -  -
Set parameter Username
Academic license - for non-commercial use only - expires 2023-08-03

Optimization Time 0.0026 seconds

Out[3]:

	1	2	3	4	5	6	7	8	9
1	3	9	7	2	3	6	5	9	2
2	8	5	6	7	9	8	1	7	4
3	4	1	2	4	5	1	6	3	8
4	7	9	6	2	8	9	8	3	6
5	4	5	2	1	3	5	1	4	2
6	8	3	1	7	4	6	7	9	5
7	7	1	5	2	6	3	7	8	4
8	8	4	3	1	4	9	1	3	2
9	6	9	2	5	7	8	6	9	5

In [4]:

solve_sudo_gurobi(fname='sudoku.xlsx',sheetname='test2')

Solving Sudoku With IP
   1  2  3  4  5  6  7  8  9
1  8  -  1  -  -  -  -  -  9
2  -  -  -  -  -  2  -  3  -
3  7  -  -  5  -  -  -  -  -
4  9  -  -  -  -  -  -  -  1
5  -  -  -  3  -  -  5  -  -
6  -  -  -  -  -  4  -  -  -
7  -  -  -  -  1  -  2  -  -
8  -  2  -  -  -  -  -  4  -
9  -  -  -  -  8  -  -  -  -

Optimization Time 0.0014 seconds

Out[4]:

	1	2	3	4	5	6	7	8	9
1	8	3	1	4	3	9	6	2	9
2	9	5	6	7	6	2	7	3	1
3	7	4	2	5	8	1	4	8	5
4	9	6	7	5	1	9	8	3	1
5	4	5	2	3	8	2	5	9	2
6	8	3	1	7	6	4	7	4	6
7	7	5	1	2	1	3	2	3	8
8	8	2	3	4	6	9	1	4	7
9	4	9	6	5	8	7	6	9	5

In [ ]: