Comparison of 5 fast solvers

briturner · Posted: Tue Nov 04, 2008 6:20 pm Post subject: Comparison of 5 fast solvers

Greetings,

I have compiled at tested 5 solvers which had source code available to test how quickly they could solve a bunch of puzzles.

Here what I found

m_b_metcalf · Posted: Thu Nov 06, 2008 10:27 am Post subject:

Brian,
Your timings are very impressive, but I see a discrepency between some of your values and those given by gsf here:

Lunatic · Posted: Thu Nov 06, 2008 11:29 am Post subject:

briturner · Posted: Thu Nov 06, 2008 12:32 pm Post subject:

Greetings,

As to discrepancy in timings, I did notice that timings for Sudocoo is very dependent on the puzzles it is solving. So I am not surprised that when running a different set of data (like the first 10000 of the Top 50000), that the times would be different. Others have also noticed that Sudocoo has troubles when there are only a few givens.

Also, these times were based off a single compiler, and a particular computer. Different compilers and different PC will give you different times (that is one reason I did not include the puzzles/sec/ghz, since it varies so much from computer to computer, I got from 6560 to 15,350 puzzles/sec/ghz when running the same program on different computers).

I did provide links to each solvers source code so others could compile and run there own test.

I plan on posting a linux friendly version of my code, with some of the nice displays disabled. The other sources are gcc friendly, but not visual c friendly. I ran the BB_Sudoku under linux last night and it was 10% faster. I am guessing all the solvers will have better times.

brit

zhouyundong · Posted: Sat Nov 22, 2008 11:20 am Post subject:

http://bbs.sudokuchina.com/viewthread.php?tid=1082&extra=page%3D1
I will test too.
can you give me your test data.
Top 50000 Top 1465 Sudoku 17
Sudocoo 2.656 0.578 123.609
fast_solv_9r2 5.000 0.421 4.593
Sudocoup 4.281 0.406 2.953
zerodoku 2.719 0.406 3.234
BB_Sudoku v0.1 1.982 0.224 1.856

All times in seconds

briturner · Posted: Sat Nov 22, 2008 9:02 pm Post subject:

Greetings:

Here are the latest timings, including a new puzzle set:

ChPicard · Posted: Sat Jun 13, 2009 4:08 pm Post subject: Re: Comparison of 5 fast solvers

willem · Posted: Sat Sep 26, 2009 8:33 am Post subject: solver

how are these solvers mad excell, php or otherwise

Adak · Posted: Sun Sep 27, 2009 1:23 am Post subject:

The very fastest one's have been written either in C or C++.

wapati · Posted: Sun Sep 27, 2009 4:16 am Post subject:

sudoking · Posted: Tue Oct 20, 2009 10:57 am Post subject: sudocoo, fast_solv_9r2: improved

This topic should be of interest to anyone wishing to increase the performance of their code.

I recently did some testing on sudocoo and fast_solv_9r2, to see which is fastest. Cut a long story short, I'm writing a diabolical generator, and I needed a fast solver. The generator works by reducing various patters recursively, and passing each solvable iteration off to a semi-solver. The semi-solver will solve most, but not all puzzles. Theory is, if a puzzle fits the pattern, then it's a bloody hard puzzle. If the semi-solver can't solve it, then it's a ridiculously hard puzzle.

Anyway, down to business. When I looked at these 2 algorithms, I noticed an opportunity for improvement in both. Essentially, it centres around the use of array and indexes Vs pointers. There were several cases where pointers could be used instead of indexed arrays.

See below for an example.

sudoking · Posted: Tue Oct 20, 2009 10:58 am Post subject:

This is post 2

sudoking · Posted: Tue Oct 20, 2009 10:58 am Post subject:

This is post 3

sudoking · Posted: Tue Oct 20, 2009 10:58 am Post subject:

This is post 4

sudoking · Posted: Tue Oct 20, 2009 10:59 am Post subject:

This is post 5