New version of Turbo Sudoku (new logic rule!)

tomker

Hi everybody,

The only "logic" rule that Turbo Sudoku 1.0 had was to fill in squares that only have one legal move.

I added a new rule for version 1.1: if a row, column, or box only has one occurrence of a legal move, make that move in the appropriate square.

Version 1.0 solved my hardest test case in 36ms (1403 nodes). Version 1.1 solves the test case in 7ms (110 nodes). It's a pretty dramatic improvement.

Probably more interesting/useful to users, the light green squares in the GUI reflect the new rule (instead of just squares with the smallest number of possible moves).

http://www.mottosearch.com/sudoku/

Hope you like it,
Tom

gaby · Posted: Mon Jul 18, 2005 10:34 am Post subject:

I'm intrigued, what is your clever algorithm for solving sudoku in a fraction of a second, as stated on your web page?
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/

dukuso

flagitious · Posted: Thu Jul 21, 2005 11:01 pm Post subject:

Ya give us the test case so we can compare please.

tomker · Posted: Mon Jul 25, 2005 7:54 am Post subject: hard test case

Yes, absolutely, sorry it's taken me so long to reply. Here's my test case, which the most recent version of Turbo Sudoku solves in 7ms (on a 2ghz Athlon 64):

....1.78.5....9..........4..26.........6....3.74.8.........3..2.8..4..1.6..5.....

-Tom

tilps · Posted: Mon Jul 25, 2005 10:03 am Post subject:

Rates as 1.1.2, with my rating solver. Although I'm sure it took longer to solve then with your turbo solver.

Out of interest, you could try testing with

xyzzy · Posted: Wed Aug 24, 2005 12:53 am Post subject: Re: hard test case

dukuso · Posted: Wed Aug 24, 2005 3:45 am Post subject:

can you try these:
http://magictour.free.fr/TOP99
or these:
http://www.csse.uwa.edu.au/~gordon/sudokumin.php
or those from the contest at:
http://www.vbforums.com/showthread.php?t=351476&page=8&pp=40

or this 16*16:
http://www.setbb.com/phpbb/viewtopic.php?t=141&mforum=sudoku

xyzzy · Posted: Wed Aug 24, 2005 11:09 pm Post subject:

Total time for TOP99: 84.6 ms
1029 contest samples from NotLKH: 276.4 ms
That 16x16 sample: 1.17 sec

Keep in mind this is on a 333MHz computer, most of you are probably benchmarking on a system ten times faster than mine.

dukuso · Posted: Thu Aug 25, 2005 3:35 am Post subject:

your timings look good to me.
About 10 times better than mine(only basic techniques) and
maybe 3 times better than the best what I've seen here.
Will you tell us more about it ?!??

Puzzles hard for one solver are often easy for another one.
I get this, even when I just rotate the sudoku by 180'.

Has someone tried these puzzles on a standard SAT-solver or such ?

Merri · Posted: Thu Aug 25, 2005 2:51 pm Post subject:

Hmm, if I tested the correct ones, then about 2.4 times faster than my VB6 solver by doing simple math (my result * 1800 MHz / 333 MHz). Thus out of interest: what language you are using?

DHallman · Posted: Thu Aug 25, 2005 7:02 pm Post subject: New version of Turbo Sudoku

Tom?

Could please put the version (& date?) into the help about?

xyzzy · Posted: Thu Aug 25, 2005 7:08 pm Post subject:

My solver is written in C. I don't want to say too much about it, as there is that contest going on at vbforums. I also hope that maybe there will be a programming contest for all languages I can enter instead of one for just a few microsoft-only languages.

I think a 4x4 or 5x5 context might be more interesting than 3x3, which is just too easy.

For example, on the 1029 problem corpus from NotLKH my program can solve 54% of them with no wrong guesses. ie. I do it with logic-only or my search heuristic never makes a wrong guess that causes back-tracking. These problems take between 217 and 244 us. In contrast the hardest problem I've found takes 7011 us, or about 31 times longer.

So, if I added more logic or made my search heuristic smarter, in the best case I could make my program 31 times faster for that hardest problem. That seems like a lot of room for improvement.

But then I look what effect this would have on the NotKLH corpus. Suppose I make my program smarter, so that instead of solving 54% with no back-tracking, I can solve all of them with no back-tracking. My total time is 276.4 ms, with a perfect search heuristic that is no slower than the one I have, that total would go down to about 233 ms. In the best case, I make my search+logic perfect and no slower than it is now, I only get a 15% overall speedup.

Of course I can't make a perfect search heuristic and adding more logic or a smarter heuristic will be slower than what I have now. So I doubt, on a corpus of mostly simple problems anyway, that I can make my program any faster by making it smarter.

Merri · Posted: Thu Aug 25, 2005 8:00 pm Post subject:

What if I place up a contest for any language which is open for any entry all the time? This would be more of an open contest, ie. every submitted code would be visible to others, who could then try to beat that code by either improving the best submitted code or then by doing a new code with a better algorithm and faster code. An open contest instead of closed contest and without a time limit.

The VBForums contest is almost over, only a day to go, so even if you told with details how your code works, there would be no time to write and optimize the code.

Anyways, I think I'm able to host the contest as I'm also planning to open a sudoku page/site.

dukuso · Posted: Mon Aug 29, 2005 9:43 am Post subject:

I had missed the last posts here.

Merri, see these contests:http://spoj.sphere.pl/
maybe we can submit a sudoku-problem there.
They are open for new problem-submissions.

The whole thing is also interesting from a math. POV,
it's similar to quasigroup completion and I wonder
if it's not even better for theoretical considerations !

And yes, then when n becomes larger we will probably
need every sudoku rule and every trick we can find
to make it faster.
I mean, for each sudoku-rule there is probably a n
such that programs on boards larger than n*n can be
made faster by including that rule.