You can see the puzzle solution space as a tree. If you try a '3' here, you go down this branch of the tree; if you try a '4' here, you go down another branch. Probably the vast majority of the branches will be dead ends (that is, you won't find a solution to the puzzle), but if you're doing a brute force search you need to visit all of them.
[Side note: in the worst case this will take 9 tries per cell, over 81 cells, or 9^81 different boards that you're looking at. That's 1.9662705x10^77 boards, which is way too many -- so you'll definitely have to do something smarter in the long run.]
Anyway, I was talking about trees. So every recursive call to the function will visit another branch of the tree. Then it will visit all possible solutions from there and return. At this point you have to reset the board so that you can visit another branch of the tree. That's the purpose of the "puzzle[x][y] = unknown" line (it's outside the if statement). Since the code just set puzzle[x][y] to try one branch of the tree, and the recursion checked all branches that lead out from there, it's time to try something else, so reset what you just tried and start with something else.
Incidentally, I wrote a sudoku solver once, a very long time ago. All it did was look at the board, and try to apply various heuistics to come up with a correct answer. (e.g., if there is only one unknown cell in a row or column, you can immediately figure out what it is.) The point of Sudoku puzzles, of course, is that
*you never need to guess*. There is only one solution. That's why brute force really doesn't make much sense in this case.
To get on with the story: I programmed in a bunch of heuristics, and the program would try applying each one in turn; as soon as one succeeded, it would start going through the list again (because the board would have changed by this point). It was fairly good at solving puzzles -- well, almost exactly as good as I was, because I only coded the heuristics that I knew about.
I could dig my program up if you're interested, but it's really more fun to write it yourself.
By the way, an analogous problem is solving a maze. Let's say you have a starting point, a finishing point, and lots of dead ends, and you can move north, west, south, and east. To solve the maze, you want to keep track of where you've been (so that the program doesn't lock into an infinite loop). You want to try one direction, then if that doesn't work, try another direction. Sample code (I'll put braces in this time) to solve this might look like
Code:
enum {
EMPTY,
WALL,
VISITED,
GOAL
};
/**
@param board Each cell of the board is EMPTY if it could be visited,
VISITED if it has already been visited, and WALL if it cannot be visited.
*/
void solve_maze(char board[WIDTH][HEIGHT], int xp, int yp) {
// base case: already at the goal
if(board[xp][yp] == GOAL) {
// found solution
}
try_direction(board, xp-1, yp);
try_direction(board, xp+1, yp);
try_direction(board, xp, yp-1);
try_direction(board, xp, yp+1);
}
void try_direction(char board[WIDTH][HEIGHT], int xp, int yp) {
// make sure position is valid
if(xp < 0 || yp < 0 || xp >= WIDTH || yp >= height) return;
if(board[xp][yp] == EMPTY) {
board[xp][yp] = VISITED;
solve_maze(board, xp, yp);
board[xp][yp] = EMPTY; // reset map to try next direction
}
}
Hmm, that ended up looking more like code than it needed to. Anyway, hopefully it gets the point across. You try one direction (if EMPTY) and take note that you've visited there (set to VISITED); then recurse to try everything from there on; and then the recursion returns so you backtrack (reset to EMPTY) and try some other direction.
Is that any less confusing?
[edit] Code coloured with codeform, by the way.
http://dwks.theprogrammingsite.com/myprogs/cfonline.htm [/edit]
Originally Posted by dwks
You can see the puzzle solution space as a tree. If you try a '3' here, you go down this branch of the tree; if you try a '4' here, you go down another branch. Probably the vast majority of the branches will be dead ends (that is, you won't find a solution to the puzzle), but if you're doing a brute force search you need to visit all of them.
