# Recursiveness in backtracking algorithm

In order to familiarise with using basic algorithms in Mathematica, I am coding a sudoku solver using a backtracking algorithm. I am treating the sudoku itself as an association (I want to learn to use them well) s.t. the keys are the positions of the cells in the sudoku, and the values are the actual numerical value corresponding to such position. This way, I have created a function to draw the sudoku pretty nicely. Hence, this association

su1 =
<|{1, 2} -> 7, {1, 3} -> 8, {1, 9} -> 4, {2, 3} -> 6, {3, 1} -> 3, {3, 4} -> 6,
{3, 5} -> 1, {3, 6} -> 7, {4, 1} -> 7, {4, 5} -> 3, {5, 4} -> 7, {5, 6} -> 4,
{6, 2} -> 5, {6, 6} -> 8, {6, 8} -> 9, {7, 3} -> 9, {7, 7} -> 7, {8, 2} -> 6,
{8, 6} -> 5, {8, 7} -> 8, {9, 2} -> 2, {9, 3} -> 3, {9, 7} -> 5|>;


corresponds to

.

I have also created two functions to be used in the main program:

1. A function that returns an the position of an empty cell of a sudoku or False if there are no empty cells (solved sudoku).

FindEmptyCell[s_Association] :=
If[Length @ s == 81,
Return @ False,
Join @@
Table[
If[MemberQ[Keys @ s, {i, j}], Nothing, {i, j}],
{i, 9}, {j, 9}] // First];

2. A function that for a given sudoku, position and cell returns True if it is valid (satisfies games rules) and False if not.

CheckValid[s_Association, value_Integer, pos_List] :=
Module[
{hline = s[#] & /@ Cases[Keys @ s, {_, pos[[2]]}],
vline  = s[#] & /@ Cases[Keys @ s, {pos[[1]], _}],
box = BoxValues[s, pos]},
If[!MemberQ[hline, value] && !MemberQ[vline, value] && !MemberQ[box, value],
Return @ True,
Return @ False]];


Well, the main program is just a backtracking algorithm which uses recursiveness:

SolveSudoku[s_Association] :=
Module[{empty = FindEmptyCell @ s},
If[empty == False,
Return @ True,
For[i = 1, i < 10, i++,
If[CheckValid[s, i, empty],
s[empty] = i;
If[SolveSudoku[s],
Return @ True && Break[],
s = KeyDrop[s, {empty}] && Return @ False]]];]];


However, I get the following:

I have restarted the kernel multiple times. but the code does not work. I guess the problem is related to the local variable empty defined within the module. However, I can't find out which is the correct way of writing it. Could someone help me, please?

• From MMA help: "lhs==rhs returns False if lhs and rhs are determined to be unequal by comparisons between numbers or other raw data, such as strings. Therefore, MMA does not evaluate {1,1} == True. You need SameQ (===) to force the evaluation – Daniel Huber Sep 15 '20 at 18:52