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?

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

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\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$ Commented May 15, 2014 at 7:42

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.