18
$\begingroup$

So, I'll preface this by saying that I am not 100% whether this fits better here or on SO.

That said: I've been trying to generate Sudokus using a backtracking algorithm to fill in the whole thing. Specifically, I label all the cells with a number, go through them 1-81 sequentially and enter random numbers. If I find I cannot enter any valid numbers, I go back one cell and try a new number for that one - keeping in mind I never repeat numbers for any cell.

Here's the thing: the labeling of the cells seems VERY important. If I go line-by-line, left-to-right, this process completes in a matter of milliseconds. If, however, I label the cells of the Sudoku matrix 1-81 randomly... the process never seems to finish, not being able to find new correct values around the time it has filled 60 or so.

Is there a reason the puzzle behaves in this way, and if so is there an even more efficient labeling pattern to generate the puzzles?

$\endgroup$
  • $\begingroup$ Are you doing this programmatically? What language? What data structure? $\endgroup$ – Donnelle Mar 14 '17 at 23:28
  • $\begingroup$ Not quite seeing how that matters if the algorithm is known? Yes I did it programmatically but by hand I'm getting the same results: line-by-line it takes on average only 20 backtracks (with rarely much more), while random assignment seems to never complete. $\endgroup$ – Weckar E. Mar 14 '17 at 23:32
  • 2
    $\begingroup$ Maybe this should be on Code Review $\endgroup$ – boboquack Mar 15 '17 at 0:52
  • 1
    $\begingroup$ @boboquack not without working code, one of the major requirements to post there. $\endgroup$ – user2052 Mar 16 '17 at 2:53
  • $\begingroup$ @Snowman But the code is working, just not efficiently. $\endgroup$ – boboquack Mar 16 '17 at 3:45
35
$\begingroup$

You will be forced to backtrack more quickly if you proceed line-by-line, because the sudoku constraints are enforced line by line (and column by column and in each sub-square). If you fill in cells in a random order, you will have to fill in many cells before you ever get a conflict in a line, or in a column, or in a 3-by-3 sub-square.

Specifically, if you put in nine values in a single row, you are certain to hit a constraint. If you put nine values into the full array at random cells, it is highly unlikely you'll hit a constraint. Without hitting a constraint, you will not need to backtrack.

$\endgroup$
  • $\begingroup$ I'm afraid I'm not quite sure what difference it makes. Going line-by-line you get 17 values for which backtracking never is needed (the far right and bottom cells), unless you need to backtrack past them for a later cell. Going randomly should give you an equal amount of gimmes... Even so, accepting that by your explanation lines are simply more efficient, why is the difference so enormous? (For reference, a program trying the random method is currently on 500k backtracks and yet to complete) $\endgroup$ – Weckar E. Mar 15 '17 at 0:11
  • 8
    $\begingroup$ @WeckarE. If I'm understanding everything correctly, I think the issue is not necessarily how often you need to backtrack, but how far. If you're filling things in randomly, you won't know that you've hit an unsolvable configuration until you fill in substantially more cells, which means you'll need to back track much further (testing a heap more redundant impossible configurations in the meantime as the algorithm slowly proves that a configuration is invalid). $\endgroup$ – Alconja Mar 15 '17 at 0:37
  • 3
    $\begingroup$ @WeckarE Suppose you fill in the first 9 cells and those cells somehow make it impossible. Then you fill in another 51 cells before realising it. You're going to be stuck trying every possible combination of the 51 cells before you get to try another combination of the first 9, and that will take forever. $\endgroup$ – immibis Mar 15 '17 at 4:18
  • $\begingroup$ For a more extreme case, imagine you solved a jigsaw puzzle in a random order. To speed up the search you need to limit the size of the search tree. You can do this by shortening the branches (by choosing a fixed order that reaches contraints as early as possible), and by having fewer branches (by choosing the order dynamically based on how many possibilities each square has left). The latter is the basis for Knuth's Algorithm X. $\endgroup$ – Jaap Scherphuis Mar 15 '17 at 5:09
  • 1
    $\begingroup$ Just before I wanted to point you to Wikipedia, someone else provided an answer that pretty much explains what I had in mind: Backtracking vs. Constraint Propagation $\endgroup$ – Sentry Mar 15 '17 at 8:39
12
$\begingroup$

David G. Stork has already explained why the order of filling the cells matters: if you're going to have to backtrack, it's better to backtrack early, and the way to achieve that for Sudoku is to fill in the grid one row (or column or 3x3 square) at a time, so that all the constraints for that row (or column or square) get checked before you start making any unrelated choices elsewhere on the grid.

If you do wish to build up a Sudoku grid in a random order, the way to do that effectively is to not just check for immediate constraint failures after each choice, but to look deeper to make sure that each choice actually still leaves the puzzle solvable.

In particular, I would suggest something like the following algorithm:

  1. Pick a random unfilled cell and set it to a random value.

  2. Run an optimized full Sudoku solver on the puzzle to verify that it still has at least one solution. If it doesn't, undo your last random choice and try some other value for that cell; otherwise, lock in the choice and repeat from step 1.

There are various more or less obvious ways to optimize this algorithm, e.g. by avoiding obviously bad choices and by reusing information from earlier solver runs to speed up later ones. Still, as long as you use a reasonably efficient solver for step 2, even this naïve algorithm should run at an adequate speed. In particular, since you'll never need to backtrack more than one level, this algorithm will always complete a 9×9 grid in at most 9³ = 729 iterations.


Ps. One notable optimization that you may want to make is constraint propagation. That is, every time you set a cell to a definite value, check if that forces any other cells to also have only one possible value. If so, set them to that value and repeat until there are no more cells whose values are forced by your choice. (If you find any cells with no possible values while doing this, then your last random choice is inconsistent, and you can immediately backtrack it.)

In fact, your solver in step 2 will almost certainly do constraint propagation or something similar internally anyway. However, doing a separate propagation step before the full solve lets you immediately mark any cells with forced values as filled, and thus speeds up (and reduces the number of) later iterations.

Another natural optimization is to store for each cell a list (or, more efficiently, a bitmap) of all the possible values it can have (based on the constraints, given the choices made so far) and update this list during the constraint propagation step. This can both speed up the propagation and also let you avoid making obviously bad random choices.

Again, this is also something that Sudoku solvers typically do internally. In fact, since filling up a Sudoku grid basically is the same as solving it, it should not be surprising that, as you optimize this algorithm, it starts to look more and more like a solver in its own right, and you might even start to wonder what the point of calling a separate solver at the end of each iteration really is.

However, it turns out that one important aspect of properly optimizing a Sudoku solver is coming up with good heuristics for the order in which to try different possible solutions, once deterministic constraint propagation no longer helps. Using a separate "inner" solver just to verify continued solvability frees the outer loop to make its choices in any order you want, while still enjoying fast conflict detection by the inner solver.

$\endgroup$
  • $\begingroup$ If you are generating Sudoku's, it is actually quicker to start from a full grid and remove clues, instead of start from an empty grid and add clues. This way the calls to the inner solver are relatively quick. Even though the inner solver is now checking for uniqueness rather than solvability (so has to try to find two solutions instead of just one), most of the solves it has to do are really easy. With some minor changes, the inner solver can be used to generate the initial randomly filled grid. $\endgroup$ – Jaap Scherphuis Mar 15 '17 at 9:16
  • 3
    $\begingroup$ @JaapScherphuis you have to get the full grid somehow though, which is the purpose of the algorithm in question. $\endgroup$ – Kat Mar 15 '17 at 18:52
  • 1
    $\begingroup$ @Kat I was expanding on Ilmari Karonen's description of a Sudoku generator that uses an optimised inner solver. The details of that optimisation are discussed in the accepted answer by David G Stork's and its comments. Such an optimised solver can generate a random full grid starting from a completely empty grid by this modification: When a digit is about to be chosen for a new cell, don't run through the digits in order, but make a list of possible digits, shuffle it, run through that list trying each possible digit in turn, and recursively try solving the.rest of the grid after each choice. $\endgroup$ – Jaap Scherphuis Mar 16 '17 at 1:04

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.