Hi,
I try to program an algorithm to solve a sudoku using recursive backtracking. I have two function. The first one is to check if a number can be placed at a certain place in the sudoku, returning 1 if it can or 0 if not:
function safe = checkSudoku(board, row, col, num)
board(row, col) = num;
if ~(length(find(board(row, :) == num)) > 1) && ~(length(find(board(:, col) == num))>1)
safe = 1;
else
safe = 0;
end
end
Then, I have another function responsible of the backtracking:
function solvedBoard = solveSudoku(board)
emptyInd = find(isnan(board));
[row, col] = ind2sub(size(board), emptyInd);
valuesAssigned = ones(length(row), 1);
for ind = 1:length(emptyInd);
for n = valuesAssigned(ind):length(board)
board(row(ind), col(ind)) = n;
t = checkSudoku(board, row(ind), col(ind), n);
if t
n = 1;
valuesAssigned(ind) = n;
break
end
if n == 9 && ~t
board(row(ind), col(ind)) = nan;
valuesAssigned(ind) = 1;
ind = ind-1;
board(row(ind), col(ind)) = nan;
end
end
end
solvedBoard = board;
end
The problem is that when I run the code with this sudoku matrix (or any other matrix):
board =
1 NaN NaN NaN
NaN 2 NaN NaN
NaN NaN 3 NaN
NaN NaN NaN 4
I get this
1 3 2 4
3 2 1 4
2 1 3 4
4 4 4 4
Which is obviously not a solved sudoku. When I try with other sudokus, I get some NaN left behing.
Any thoughts ? Thanks !
