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;endend
Then, I have another function responsible of the backtracking:
function solvedBoard = solveSudoku(board)emptyInd = find(isnan(board));[row, col] = ind2sub(size(board), emptyInd);%to keep track of values assigned
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 !
Best Answer