The New Sudoku Players' Forum

[ovaltrade]

I wonder how programmers of Sudoku solvers could face up in a tough performance challenge. Personally, I would be very curious to see how my own coding measures up against other people craft...

Writing a recursive tree solver is not difficult. Building it with heuristic algorithms upfront to cut down on processing time could prove to be more of a task, probably involving the author own hability to manually solve the puzzles.

The rules should be as simple as the Sudoku ones (to be defined later).

Any programming language should be allowed, including any flavor of assembler: as long as the object code could be linked with a provided Main program acting as a measurement monitor (for correctness of the results and total consumed cycles).

When executed on a designated machine, the object code using the smallest amount of CPU cycles to solve a given set of tough Sudoku puzzles rules the world...

Any one interested?
Does this kind of challenge already exist somewhere?

How is your C lately?

[dukuso]

there was a contest at:
http://www.vbforums.com/showthread.php?t=351476&page=11&pp=40
the winning program took about 0.25ms per sudoku with 1 GHz.

please suggest your contest idea to
http://spoj.sphere.pl/forum/

[ovaltrade]

Wow! 0.25 ms at 1 GHz is surprisingly fast... 250,000 cycles only...

To solve this one I found in a post elsewhere on this same forum:

+-------+-------+-------+
| . . . | . 7 . | 9 4 . |
| . 7 . | . 9 . | . . 5 |
| 3 . . | . . 5 | . 7 . |
+-------+-------+-------+
| . 8 7 | 4 . . | 1 . . |
| 4 6 3 | . . . | . . . |
| . . . | . . 7 | . 8 . |
+-------+-------+-------+
| 8 . . | 7 . . | . . . |
| 7 . . | . . . | . 2 8 |
| . 5 . | 2 6 8 | . . . |
+-------+-------+-------+

This is the famous "toughest known puzzle".

Solving this puzzle requires an advanced deductive technique called Tabling. Currently, the only app that implements tabling is the Sudoku Susser.

my own code (VB + asm) consumed 1,515,000 cycles and it used an extra 2,679,000 cycles to make sure no other possibility exists...

I have the feeling this kind of competition could be much harder than I originally anticipated.

Thanks for the reply dukuso...

[dukuso]

it's hard to measure one single sudoku's hardness,
you can get quite different results by reordering the rows and columns.
So, I usually take 100 random equivalent permutations
and measure the average.
My 96 hardest are here:
http://magictour.free.fr/top96
time the whole list and report your result !
I need 1-2 ms with 2.5GHz for such a sudoku.

I think, the real fun starts with 16*16 sudokus or higher,
where the solvers experience certain delays, which are
uncommon with 9*9 !
Problems are probably similar as with QWH,
and thus of some practical relevance.
See:
http://www.setbb.com/phpbb/viewtopic.php?p=1424&mforum=sudoku#1424

[ovaltrade]

Thanks for the list. Here is what I got:

To find the 96 solutions it needs 363,185,680 cycles, average is 3,783,184 cycles.

My machine is running at 3.2 GHz. So, average time is 1.18 ms.

At 2.5 Ghz, it would therefore need 1.5 ms.
Now for me, it is optimization time !!! I think I can do better...

[ovaltrade]

Now for me, it is optimization time !!! I think I can do better...

After optimizing the solver code:

To find the 96 solutions it needs 103,020,896 cycles, average is 1,073,134 cycles.

My machine is running at 3.2 GHz. So, average time is 0.34 ms.

At 2.5 Ghz, it would therefore need 0.44 ms.

And I think there is still room for some more optimization but the gain would not be as spectacular...

[ovaltrade]

My "solver" is embedded into a 32-bit DLL Sudoku.dll called by a small VB main program Sudoku.exe.

This Sudoku.exe program is not designed for general public pressure but simply to test the speed of the solver. By example, it does not validate the Grid before sending it to the embedded solver. You may download into a temporary test directory on your machines the 2 files zipped at http://ovaltrade.com/sudoku/ovaltrade/sudoku.zip

As long as the DLL is in the same directory as the EXE, eveything should work ok (use a shortcut with its "start in" directory set to the location of the DLL).

To alter the grid, clic on any square, enter 1 to 9 or 0 or a space...

If you provide a Grid which requires too much time to solve, crash the program by closing it or use Task Manager to get rid of it.

[ovaltrade]

Hi Dukuso,

I got the list of the Sudoku puzzles used in the contest I missed at:
http://www.vbforums.com/showthread.php?351476&page=11&pp=40

the winning program took about 0.25ms per sudoku with 1 GHz.

My solver did the 69 entries in 3,192,280 P4 cycles, so the average is 46,265 cycles.

On a 1 GHz P4, this means .05 ms per puzzle

Your top96 list has obviously much tougher Sudoku's: 96 entries in 78,649,824 P4 cycles, so the average is 819,269 cycles.

On a 2.5 GHz P4, this means .33 ms (I have further optimized the solver code).

[scjurgen]

Hm, solved with my solver in 99 tries, is it really that difficult?

http://www.schwietering.com/sudoku/index.php?arg=....7.94..7..9...53....5.7..874..1..463...........7.8.8..7.....7......28.5.268...

Wow! 0.25 ms at 1 GHz is surprisingly fast... 250,000 cycles only...

To solve this one I found in a post elsewhere on this same forum:

+-------+-------+-------+
| . . . | . 7 . | 9 4 . |
| . 7 . | . 9 . | . . 5 |
| 3 . . | . . 5 | . 7 . |
+-------+-------+-------+
| . 8 7 | 4 . . | 1 . . |
| 4 6 3 | . . . | . . . |
| . . . | . . 7 | . 8 . |
+-------+-------+-------+
| 8 . . | 7 . . | . . . |
| 7 . . | . . . | . 2 8 |
| . 5 . | 2 6 8 | . . . |
+-------+-------+-------+

This is the famous "toughest known puzzle".

Solving this puzzle requires an advanced deductive technique called Tabling. Currently, the only app that implements tabling is the Sudoku Susser.

my own code (VB + asm) consumed 1,515,000 cycles and it used an extra 2,679,000 cycles to make sure no other possibility exists...

I have the feeling this kind of competition could be much harder than I originally anticipated.

Thanks for the reply dukuso...

[ovaltrade]

Against a recursive algorithm, solving a Sudoku is not a big feat... The recursive approach leads also to find (or count) all the possible solutions by finishing the full tree of possibilities.

Now, let's look at another angle of the problem: the algorithm itself.
How fast can it be, or should I say how good is it? That's the challenge.

By example, I tried the following with your solver:

9xx 8xx 7xx
x1x x2x x3x
xxx xxx xxx

6xx xxx 4xx
x4x xxx x6x
xxx xx5 xxx

3xx 2xx 1xx
x7x x8x x9x
xxx xxx xxx

This one has a big amount of easy solutions. Remove the timeout limitation and give me the count of possibilities along with a timing measurement. The question is how many, then how long will it take to find them all. This demonstrates how good an algo is to perform these tasks.

Also, for easier comparison about timing, try to use the number of CPU cycles instead of the clock on the wall. Altough not perfect, this allows to compare better among machines with different clock speeds:

_asm {
RDTSC // or 0x0F,0x31 if rejected by the compiler
mov dw0,eax
mov dw1,edx
}

... will provide you the current CPU Time Stamp Counter which is the amount of CPU cycles consumed since power up... Use this around the function to time and compute the absolute differential.

[angusj]

The question is how many, then how long will it take to find them all.

Too many and too long. (I gave up after counting over 5 million solutions.)

[ovaltrade]

Keep on trying angusj... it is in the 30 millions neighborhood...

So, yet another solver

[ovaltrade]

New improved (faster) version of my experimental solver still available at http://ovaltrade.com/sudoku/ovaltrade/sudoku.zip.

Note: VB6 runtime still required to execute the program.

[ovaltrade]

In the top 96 puzzles proposed by dukuso, the number 12 is currently the toughest puzzle my solver has encountered so far:

2X3 X8X XXX
8XX 7XX XXX
XXX XXX 1XX

X6X 5X7 XXX
4XX XXX X3X
XXX 1XX XXX

XXX XXX X82
X5X XXX 6XX
X1X XXX XXX

17 starting numbers, only 1 solution.
My solver consumed 4,766,536 cycles to find this solution and a grand total of 5,005,480 cycles to reach the conclusion there is only 1 solution.

I wonder if a tougher one does exist ...

[tbailey]

What is your definition of cycle? Is it how many times that your program loops through its main solving code?