Why doesn't this code have a recursion error?
1 Ansicht (letzte 30 Tage)
Ältere Kommentare anzeigen
Richard McCulloch
am 1 Mai 2016
Kommentiert: Richard McCulloch
am 2 Mai 2016
There is a link to a Matlab sudoku solver here: Matlab Sudoku Solver (shown below). I wrote my own solver (shown below) and I get "recursion error" when it runs. It's basically the exact same thing with different variable names. Why does my code get a recursion error while the code in the link doesn't? Thanks!
Matlab Code
function X = sudoku(X)
% SUDOKU Solve Sudoku using recursive backtracking.
% sudoku(X), expects a 9-by-9 array X.
% Fill in all “singletons”.
% C is a cell array of candidate vectors for each cell.
% s is the first cell, if any, with one candidate.
% e is the first cell, if any, with no candidates.
[C,s,e] = candidates(X);
while ~isempty(s) && isempty(e)
X(s) = C{s};
[C,s,e] = candidates(X);
end
% Return for impossible puzzles.
if ~isempty(e)
return
end
% Recursive backtracking.
if any(X(:) == 0)
Y = X;
z = find(X(:) == 0,1); % The first unfilled cell.
for r = [C{z}] % Iterate over candidates.
X = Y;
X(z) = r; % Insert a tentative value.
X = sudoku(X); % Recursive call.
if all(X(:) > 0) % Found a solution.
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); % Number of candidates.
s = find(X==0 & L==1,1);
e = find(X==0 & L==0,1);
end % candidates
end % sudoku
My Code
function X=SD(X)
% C is a cell array of candidate vectors for each cell.
% s is the first cell, if any, with one candidate.
% e is the first cell, if any, with no candidates.
[C,s,e] = candidate(X);
while ~isempty(s) && isempty(e)
X(s) = C{s};
[C,s,e] = candidate(X);
end
% Return for impossible puzzles.
if ~isempty(e)
return
end
% Recursive Backtracking
if any(X(:) > 0)
Y=X;
[row,col]=find(X==0,1,'first');
for k=1:length(C{col,row})
X=Y;
X(col,row)=C{col,row}(k);
X=SD(X);
if all(X(:)>0)
return
end
end
end
function [C,s,e]=candidate(X)
C=cell(9,9);
for j=1:9
for i=1:9
% remove numbers already in current row/column
p=1:9;
t1=nonzeros(X(j,:));
t2=nonzeros(X(:,i));
% remove numbers already in current minor matrix
t3=nonzeros(X(3*ceil(j/3)-2:3*ceil(j/3),3*ceil(i/3)-2:3*ceil(i/3)));
p(nonzeros([t1' t2' t3']))=0;
C{j,i}=nonzeros(p);
end
end
L = cellfun(@length,C);
s = find(X==0 & L==1,1);
e = find(X==0 & L==0,1);
end
end
2 Kommentare
John D'Errico
am 1 Mai 2016
Bearbeitet: John D'Errico
am 1 Mai 2016
Maybe this should teach you not to take code from someone else, change the variable names, and without even bothering to understand the code, hope to hand it in for your homework assignment. Karma.
Akzeptierte Antwort
Stephen23
am 2 Mai 2016
You changed this:
if any(X(:) == 0)
into this:
if any(X(:) > 0)
Think about it.
3 Kommentare
Stephen23
am 2 Mai 2016
Bearbeitet: Stephen23
am 2 Mai 2016
Simply calling a function is not the definition of recursion: it is the depth of recursion that matters (for the limit). So clearly you are calling your function lots of times, but without recursion to 500 calls deep.
fun1a
fun2a
fun3a
fun2b
fun3b
fun3c
fun2c
etc
See: lots of calls, but only depth of three. This is what recursion means. To check the recursion depth you could add a depth variable to the function input and output, and keep track of that.
Weitere Antworten (0)
Siehe auch
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!