8
$\begingroup$

I understand the basic method of generating sudoku puzzles, which is:

  1. Put a random number in the current square.
  2. If the puzzle is still valid, go to the next square. Otherwise, stay on the same square.
  3. Repeat from step 1.

However, sometimes a sudoku puzzle gets "stuck" so that no matter what you put in the square, it still won't work.

How can I avoid getting stuck in an infinite loop here?

$\endgroup$
  • 1
    $\begingroup$ Is this about actually authoring Sudoku, or about computer generation? $\endgroup$ – user121 May 15 '14 at 9:57
5
$\begingroup$

You must keep track of all numbers that you have tried in a square. Then, on the random number generation step, if all numbers have been tried, go back one square.

When going back, remember to clear the "numbers already tried" list; otherwise you can't get past that point. This won't lose any information, because sudoku generation is like branching out on a "tree" - you don't care what's past that branch as long as you know it's a dead end.

For this same reason, you must keep a "points tried" list on all squares, in case you have to go back two or more squares.

$\endgroup$
  • $\begingroup$ Some basic research seems to indicate there are less memory-intensive ways of doing this, but I have yet to gather enough info for a full answer myself. $\endgroup$ – Aza May 15 '14 at 7:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.