The New Sudoku Players' Forum

[stivo]

I'm wondering how fast your solver is? This is the benchmark puzzle I use with my solver:

500000009020100070008000300040600000000050000000207010003000800060004020900000005

My 2GHz Intel Core 2 Duo MacBook can solve it in .093 seconds. The solver is written in C and compiled with optimizations. How fast is yours? I am interested in seeing other people's code as well.

-
STiVo

[champagne]

Hi

This is metcalf puzzle, one of the hardest. (top in JPF's list)

It took my solver 79 milliseconds to check unicity, which seems comparable to what you call "solving".

It took the computer (a PC) about 17 seconds to really solve it.
I am using c+ language under windows.

It happens that I am publishing the solution.

The draft is already visible at that point,

http://pagesperso-orange.fr/gpenet/UX/Sample5metc/metc_fichiers/V1_00.htm

Normally, to-day the first half should be clean.

A very interesting puzzle for those who want to crack a very hard puzzle without help of a computer.

[Draco]

My solver is written in C# and requires .Net v2. It uses an optimized recursive (aka back-tracking) search to find a solution.

Averaging out 100 runs after a garbage collection, it takes about 6 milliseconds to find a solution to the puzzle. For some reason I do not understand, the same run with a DEBUG build under the debugger (Visual Studio) takes 2 - 4ms per run. Got to love that .Net runtime!

Cheers...

- drac

[gsf]

I'm wondering how fast your solver is? This is the benchmark puzzle I use with my solver:

500000009020100070008000300040600000000050000000207010003000800060004020900000005

My 2GHz Intel Core 2 Duo MacBook can solve it in .093 seconds. The solver is written in C and compiled with optimizations. How fast is yours? I am interested in seeing other people's code as well.

that's ~5 puz/sec/Ghz, but you should run the test on say 1000 copies of the same puzzle
and divide the results by 1000 to normalize
my general solver limited to singles and backtracking solves 1000 copies at ~335 puz/sec/Ghz
another 150 line backtracking solver comes in at ~746 puz/sec/Ghz
and a dlx solver just posted on the programmer's forum (not mine) gets ~1190 puz/sec/Ghz

performance varies on input, the new dlx solver does well with smaller number of clues
mine does better with more, e.g., on ruud's top50000

[Papy]

In fact you have two ways to solve a grid using a logical solver or a 'Brute Force' Solver

The logical solder is the faster when it finds!
Brutal solver always find and the times doesn't depends of the difficulty only the clues reparttition.

A test with just a grid is bad. 1000 times also
On my 2,4 Ghz Core 2 I solve the a grid 5000 times in a second but I need two MINUTES with anopther.

Programmer know this problem. You have solutions( sort the grid) but You also needs time to do it.

So to compare your result what kind of solver do you write.


Papy

[cardinal]

try this one :(no solution)
000760000000400071800000000000000000007000900600300120070000040000006000000970000

some backtracks clogged

[udosuk]

try this one :(no solution)
000760000
000400071
800000000
000000000
007000900
600300120
070000040
000006000
000970000

some backtracks clogged

That's interesting. Any (smart) solver should immediately recognise that you can't place a 7 on c1. Yet some of them actually struggle to prove it using brute-force. Makes you think about how dumb (some) programs really are.

[cardinal]

i admit it, when I firstly wrote my solver, got caught in this one it was only pure brute force.

after that, I introduced some logic. naked and hidden singles/pairs, line/box interactions.

[zhouyundong_2012]

My Speed: 0.777 ms UniqAnswer (1.46G CPU)

[JasonLion]

On the original puzzle, my backtracking solver does it in 0.000209 seconds, or about 1,800 puzzles/second/GHz on a Core 2 Duo.

The invalid puzzle runs at over 300,000 puzzles/second/GHz.

A discussion of my solver, with source code, is available over on the programmers forum, http://www.setbb.com/phpbb/viewtopic.php?mforum=sudoku&p=11913. I tried fairly hard to make the code readable, but some of the speed optimizations are fairly obscure.

[zhouyundong_2012]

your solver is too fast! I should improve it again.