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?

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

1 Answer 1


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.

  • $\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$
    – user20
    Commented May 15, 2014 at 7:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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