Digital Signal Processing Reference
In-Depth Information
if (blank)
% found a blank to fill in,
% so try all values 1..9
for value=1:9
% Try the current value there
puzzle(row,col) = value;
% maybe this value is already in this row,
% or in this column, or 3x3 submatrix ?
if (sudoku_check(puzzle))
% the value does not cause a problem
% so try to fill in any remaining blanks
sudoku_search(puzzle);
end
end
else
% Show the puzzle if no blanks were found.
% That is, we know the puzzle checks out
% (or this function would not have been called),
% so if no blanks are left, then we have a
% solution!
puzzle
end
Recursion allows the programmer to solve a complex problem by writing a rel-
atively small function. First, a recursive function checks to see if it is done. If not,
it takes the problem one step closer to the solution and calls itself. We could have
written the search function in a way that does not use recursion, but then we would
have to keep track of what changes we made to the puzzle and implement our own
mechanism to undo changes as needed.
Now that we have seen how the puzzle should work, let's see an example that
does not work so well. In the example puzzle above, we have 4 as the rst entry on
the second row. But what if we replace this with a blank? We will test it out with
the program.
>> puzzle = [ 0, 2, 3, 4, 0, 6, 7, 8, 0;
0, 0, 6, 7, 0, 9, 1, 0, 3;
7, 8, 0, 1, 0, 3, 0, 5, 6;
3, 1, 2, 0, 0, 0, 9, 7, 8;
0, 0, 0, 0, 0, 0, 0, 0, 0;
6, 9, 8, 0, 0, 0, 5, 1, 4;
