Help! My solver is fast when linear and broken when random!

sswift

I wrote a very clean implementation of a recursive brute-force solver for Sudoku, but I'm having a problem.

My solver, as first written, started at 0,0 and looped through each square.

It used a fast method of determining which numbers do not appear in the same row, column, or box to figure out which numbers are allowed for that square.

Then it tries each number in the square and calls the function again for each, and resets the square to empty if it finds no number which leads to a solution or the function call returns false telling it that it hit a dead end somewhere down the tree.

The function worked great like this. Very fast, less than 80 milliseconds on some of my test puzzles, and it's not even coded in C, it's coded in Basic.

But I hit a major snag. As soon as I started to randomize the empty tile the function would select on the next run through to try different possibilities on, suddenly, the program just sits there calculating for forever.

I thought maybe something was going on in the function that would cause a problem if the calls were randomized like this... Because a tile might try a 6 and then try to next fill in square 1,3 but when that fails, it would try a 7 and try to fill in square 4,5. And I thought that might cause problems.

So instead, I tried storing all the empty tiles in an array before I call the recusrive function. Then I increment a number passed to the function each time I recurse. This array of empty tiles was shuffled, so now it should step through the entire puzzle in a random order, visiting each cell once, very fast. But not visiting them in a linear order, like when I would just keep incrementing X and Y which ALWAYS started at 0 every time I called the function, until I hit an empty square.

But this didn't work either!

I've read here that another way of getting a random result with an empty input puzzle is to randomize the order in which I try each possiblity for a square, but I really didn't want to do shuffling in the recusrive function itself.

So is there something wrong with how I am thinking about this? Why would stepping through the empties in a snuffled, but fixed for the duration of finding the solution, order not work, when stepping through them from top lef tto bottom right works fine and fast?

Miles · Posted: Thu Feb 16, 2006 8:27 am Post subject:

Debug your code. Figure out what you want him to do and debug it to see if it does what it should do.

sswift · Posted: Thu Feb 16, 2006 9:27 am Post subject:

Debugging it was the first thing I tried. But there's a lot of data there to examine!

I'm not asking you to debug my program here. I'm asking if there is a known problem with solving sudokus using random squares like this. If there is not, then the problem is likely in my implementation. If there is, then I need to try a new algorithm.

sswift · Posted: Thu Feb 16, 2006 1:43 pm Post subject:

Just to let you know, I've solved the problem by swithcing from shuffling empty squares, to shuffling candidate values.

Agent Allen · Posted: Fri Feb 17, 2006 9:26 pm Post subject: No you didn't

Or may be you did.

To obtain a more even distribution without bias, the method I implemented shuffles the empty cells once at the beginning and then also goes through the possibles in Random order.
Suppose you try to randomly solve the puzzle I posted with 5 solutions (see Library).
You will get one of these solutions: