What's the fastest approach to solving Sudokus?

UmberGryphon

I've been playing around with writing Sudoku-solving programs, since it seemed like an interesting problem. I started out with a fairly straightforward brute-force searcher, which worked (although slowly). I then started Googling for better basic methods, found this forum, and decided that I liked dodo's basic approach, as seen here. It isn't that far removed from brute-force, but it seemed much more efficient and easy-to-optimize than what I'd been doing.

I've done lots of optimizations, including a 9-by-9 array that does nothing but give an index into the boxes[] bitsets given x and y coordinates (because apparently (x/3)*3+y%3 isn't as cheap as you'd think), a 512-element array that does nothing but tell you how many bits are set in a given number, and reordering the rows so that the easiest row in the easiest 3-row block gets priority when cells tie for number of candidates (which isn't much help in top1011, but helps a lot in top95).

After all that, I can solve top1011 in 0.178 seconds and top95 in 0.488 seconds on a 3 GHz P4 (using Cygwin gcc -O9). But other people get better times on slower computers. Is there a faster fundamental approach? Am I missing some important optimization? Does cygwin-gcc suck? I'm confused.

UmberGryphon
(who suspects there's a faster algorithm)

xyzzy · Posted: Thu Oct 06, 2005 2:17 am Post subject:

Keep track of more data and do less recalculating.

As far as I've found, I've written the fastest soduko solver yet, and I used gcc. But not cygwin, bleh, Linux only.

dukuso · Posted: Thu Oct 06, 2005 8:57 am Post subject:

maybe you should include some more lookahead using
some of the known "technics".
http://www.setbb.com/phpbb/viewtopic.php?t=178&mforum=sudoku

UmberGryphon · Posted: Thu Oct 06, 2005 4:00 pm Post subject:

dukuso · Posted: Fri Oct 07, 2005 6:23 am Post subject:

your 20% gain on top95 is not so much, but maybe the
effect is stronger for larger sudokus, 16*16,25*25,..

let me compare it with these :

----------------------------------------

Dotu/delVal/Cebrian : ("dom-lessO")
select the variable with the minimum domain size
and then select the value which occurs the fewest times in the domains
of the variables of the rows and columns [and blocks] of the selected variable

Regin/Gomes : ("dom-maxB-lessO")
when two variables have the same size of domain we select the one for
which the number of instantiated variables of the row and of the
column [and of the block] is maximum.

UmberGryphon :
when two variables have the same size of domain we select the one for
which the product of the domainsizes of the variables in
the same row/column/block/chute is minimum
(I'm not sure about the exact preferrence row/col/block/chute here)

variable : cell
domian of a variable : candidates for that cell
value : smbol or digit which goes into a sudoku-cell
instantiated variable : filled cell,clue,only one candidate

----------------------------------------

UmberGryphon · Posted: Fri Oct 07, 2005 4:25 pm Post subject:

xyzzy · Posted: Fri Oct 07, 2005 9:42 pm Post subject:

Dancing links are fast, but I didn't use dancing links and am faster. For 9x9 sudoku complex logic is slower, I've yet to make anything more than singles show an overall speed improvement. I'm close with subsets though. For 16x16, using subsets (all forms) does offer a speed improvement. When you preform a depth first search, it's very important to have a good heuristic to choose which branch to take first. Think about the operations you will perform, and create your data structures so that these operations can be preformed quickly. And of course think about ways to use lookup tables to avoid multiplication, division, and looping.

Ruud · Site Admin

You could do the easy pickings (singles, box-row, subsets) first and then hand it to a backtracking solver like dancing links. With an integrated data model, the "logic" code can disable DLX rows on the fly. That would save initialization time for the DLX solver.

Ruud
(who also refuses to do inline assembly)

UmberGryphon · Posted: Tue Oct 11, 2005 5:21 pm Post subject: