Recursive Backtracking not Properly Working to Solve a Sudoku
6 ビュー (過去 30 日間)
古いコメントを表示
Louis-Philippe Robichaud
2020 年 5 月 26 日
回答済み: Abhivandan Pandey
2020 年 6 月 13 日
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 !
0 件のコメント
採用された回答
Abhivandan Pandey
2020 年 6 月 13 日
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.
0 件のコメント
その他の回答 (0 件)
参考
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!