Puzzles and Recreation
Computer Science

Solve a Sudoku using Recursion

Open in Cloud
Download Notebook

There are different methods for solving sudoku puzzles; here, we use recursion to solve sudoku.

Create a grid of 9 x 9 numbers with the missing numbers marked by crosses:

In[1]:=

grid=

;

In[2]:=

Grid[Map[#/.XFramed[Style[X,Black,15,Gray],RoundingRadius50,BackgroundLightBlue]&,grid],Dividers{{{Directive[{Thick,Black}],{Dashed,Red},{Dashed,Red}}},{{Directive[{Thick,Black}],{Dashed,Red},{Dashed,Red}}}}]

Out[2]=

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

Define a function that takes a row and column, extracts all the "known" numbers, and takes a complement of those digits from

Range

[9] to generate some "safe" numbers (numbers not yet present in row, column or submatrix):

In[3]:=

getSafeNumbers[grid_,{row_,col_}]:=Block{rownum,colnum,submatrix},rownum=Cases[grid〚row〛,Except[X,_Integer]];colnum=Cases[grid〚All,col〛,Except[X,_Integer]];submatrix=Cases[#,Except[X,_Integer]]&@FlattenWhichrow≤3&&col≤3, Take[grid,3,3],row≤3&&col≤6, Take[grid,3,4;;6],row≤3&&col≤9, Take[grid,3,7;;9],row≤6&&col≤3, Take[grid,4;;6,3],row≤6&&col≤6, Take[grid,4;;6,4;;6],row≤6&&col≤9, Take[grid,4;;6,7;;9],row≤9&&col≤3, Take[grid,7;;9,3],row≤9&&col≤6, Take[grid,7;;9,4;;6],row≤9&&col≤9, Take[grid,7;;9,7;;9];Complement[Range[9],Union[rownum,colnum,submatrix]]

One safe number is pushed in place of a missing number "X" and the grid is recursively passed on to generate other safe numbers that are further pushed. The process gets repeated until no X's remain in the grid and a solution has been found:

In[4]:=

sudoku[grid_]:=Module{missingposition,safenumbers},missingposition=FirstPosition[grid,X];safenumbers=getSafeNumbers[grid,missingposition];IfHead[missingposition]=!=Missing, sudoku[ReplacePart[grid,missingposition#]]&/@safenumbers, Sow[grid];

Solve the puzzle and generate the filled grid:

In[5]:=

(sol=Reap[sudoku[grid]]〚2〛//Flatten[#,2]&;)//AbsoluteTiming

Out[5]=

{0.0019691,Null}

In[6]:=

(rule=Map[#Framed[Style[sol〚Sequence@@#〛,Bold],RoundingRadius50,BackgroundLightBlue]&,Position[grid,X]])//Short

Out[6]//Short=

{1,2}

,{1,3}

,{1,9}

,{2,1}

,{2,3}

,{2,6}

,{2,7}

,{3,2}

,20,{8,3}

,{8,6}

,{9,2}

,{9,4}

,{9,6}

,{9,7}

,{9,8}

,{9,9}



In[7]:=

Grid[ReplacePart[sol,Dispatch[rule]],Dividers{{{Directive[{Thick,Black}],{Dashed,Red},{Dashed,Red}}},{{Directive[{Thick,Black}],{Dashed,Red},{Dashed,Red}}}}]

Out[7]=

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

Publisher Information

Contributed by: Ali Hashmi

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

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

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

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

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

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