Matlab_回溯法解决数独问题

Matlab_回溯法解决数独问题

function X = sudoku(X)
[C,s,e] = candidates(X);
while ~isempty(s) && isempty(e) X(s) = C{s};
[C,s,e] = candidates(X);
end
 
if ~isempty(e)
return
end
 
if any(X(:) == 0)
Y = X;
z = find(X(:) == 0,1);
for r = [C{z}]
X = Y;
X(z) = r;
X = sudoku(X);
if all(X(:) > 0)
return
end
end
end
function [C,s,e] = candidates(X)
C = cell(9,9);
tri = @(k) 3*ceil(k/3-1) + (1:3);
for j = 1:9
for i = 1:9
if X(i,j)==0
z = 1:9;
z(nonzeros(X(i,:))) = 0;
z(nonzeros(X(:,j))) = 0;
z(nonzeros(X(tri(i),tri(j)))) = 0;
C{i,j} = nonzeros(z)';
end
end
end
L = cellfun(@length,C);
s = find(X==0 & L==1,1);
e = find(X==0 & L==0,1);
end % candidates
end % sudoku

x = [8 1 6 0 0 0 0 0 3;
     3 5 7 0 0 0 0 8 0;
     4 9 2 1 0 0 0 0 0;
     0 0 3 8 1 6 0 0 0;
     0 0 0 3 5 7 0 0 0;
     0 0 0 4 9 2 1 0 0;
     0 0 0 0 0 3 8 1 6;
     0 2 0 0 0 0 3 5 7;
     1 0 0 0 0 0 4 9 2;];
 
y = sudoku(x)

参考资料请移步【下载】界面进行下载