Sudoku Solver (Recursive)

SOLUTION::usage = “Head of a valid solution”;
NOSOLUTION::usage = “Head of invalid sudoku”;

SudokuSolver[board_List] :=
Module[{requiredCells, possibilities, trys, result = NOSOLUTION[board]},
requiredCells = GetRequiredCells[board];
possibilities = GetPossibilities[board, requiredCells] ;
trys = GetTrys[possibilities] ;
Do[
If[i > 1,
Print["Backtracking on try ", trys[[i - 1]], ” trying “, trys[[i]]]];
result = TestTry[board, trys[[i]]];
If[Head[result] === SOLUTION,
Return[result]],
{i, 1, Length[trys]}
];

Return[result]
]

TestTry[board_List, try_] :=
Module[{nextBoard},
nextBoard = ReplacePart[board, try] ;
If[FreeQ[nextBoard, 0],
SOLUTION[nextBoard],
SudokuSolver[nextBoard]]
]
GetRequiredCells[board_List] := Position[board, 0]

GetPossibilities[board_List] :=
GetPossibilities[board, GetRequiredCells[board]]

GetPossibilities[board_List, requiredCells_] :=

GetPosibility[board, #] & /@ requiredCells

GetPosibility[board_List, pos_List ] :=

pos -> # & /@
Complement[Range[1, 9],
Union[board[[pos[[1]]]], board[[All, pos[[2]]]], Get3x3[board, pos]]]

Get3x3[board_, {x_, y_}] :=
Module[{lx, ly, ux, uy},
{lx, ly} = Floor[(# - 1)/3]*3 + 1 & /@ {x, y};
{ux, uy} = {lx, ly} + 2;
Flatten[board[[lx ;; ux, ly ;; uy]]]
]

GetTrys[possibilities_] := First[SortBy[possibilities, Length]]

 

sudoku1 = ({
{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}
});

In[114]:= MatrixForm@@SudokuSolver[sudoku1]
Out[114]//MatrixForm=

(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

)

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>