Recursive Backtracking not Properly Working to Solve a Sudoku

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);

%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 !

Answer 1

[Abhivandan Pandey]

Hi Louis,

As far as i could undertand, there seems to be a problem in logic of your code. You should check this if-condition

            if n == 9 && ~t
                board(row(ind), col(ind)) = nan;
                valuesAssigned(ind) = 1;
                ind = ind-1;
                board(row(ind), col(ind)) = nan;
                
            end

Size of board in the example you gave is 4 so the sudoku should be filled only with 1,2,3,4 but here you are checking for n==9 i.e. you are assuming that board size is always 9x9.