Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Comparison of 5 fast solvers
Goto page 1, 2  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
briturner

Joined: 14 Oct 2008
Posts: 75
:

Items
PostPosted: Tue Nov 04, 2008 6:20 pm    Post subject: Comparison of 5 fast solvers Reply with quote

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
Code:
                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



All were compiled with Visual C 6.0, Win32 Release configuration for full optimization, run on an Intel T5600 processor. Results may vary with different compilers / processors.

Sudocoo by Glenn Fowler http://www.research.att.com/~gsf/

fast_solv_9r2 by Ignacio Zelaya http://www.setbb.com/sudoku/viewtopic.php?mforum=sudoku&t=1586&postdays=0&postorder=asc&start=15&mforum=sudoku

Sudocoup by Glenn Fowler http://www.research.att.com/~gsf/

zerodoku by Jim Schirle http://tinyurl.com/5jjpl4

BB_Sudoku by Brian Turner http://www.setbb.com/sudoku/viewtopic.php?t=1663&mforum=sudoku
Back to top
View user's profile Send private message
m_b_metcalf

Joined: 13 Mar 2006
Posts: 210
:
Location: Berlin

Items
PostPosted: Thu Nov 06, 2008 10:27 am    Post subject: Reply with quote

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

so for the first 10000 of the top50000
sudocoo (brute force solver posted here) ~5600 puz/sec/Ghz
sudocoup (slightly more aggressive forward checking) ~1700 puz/sec/Ghz
sudoku (my solver with -qFN -f- (no output)) ~2200 puz/sec/Ghz

where there's a factor 3.3 between sudocoo and sudocoup for top50000, whereas you get 1.6.

Have I misunderstood something?

Thanks,

Mike Metcalf
Back to top
View user's profile Send private message
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Thu Nov 06, 2008 11:29 am    Post subject: Reply with quote

m_b_metcalf wrote:
Brian,
Your timings are very impressive, ...


Indeed Brian, nice approach of combining brute force with simple logic through the whole solving process.
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~


Last edited by Lunatic on Fri Nov 07, 2008 11:03 pm; edited 1 time in total
Back to top
View user's profile Send private message Send e-mail Visit poster's website
briturner

Joined: 14 Oct 2008
Posts: 75
:

Items
PostPosted: Thu Nov 06, 2008 12:32 pm    Post subject: Reply with quote

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
Back to top
View user's profile Send private message
zhouyundong

Joined: 22 Nov 2008
Posts: 43
:

Items
PostPosted: Sat Nov 22, 2008 11:20 am    Post subject: Reply with quote

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
Back to top
View user's profile Send private message Send e-mail
briturner

Joined: 14 Oct 2008
Posts: 75
:

Items
PostPosted: Sat Nov 22, 2008 9:02 pm    Post subject: Reply with quote

Greetings:

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

Code:

                Top 50000    Top 1465    Sudoku 17    Gen 500,000
Sudocoo           2.656        0.578      123.609         dnf
fast_solv_9r2     5.000        0.421        4.593        28.921
Sudocoup          4.281        0.406        2.953        57.032
zerodoku v2       2.515        0.375        2.703       677.187
BB_Sudoku v0.1    1.982        0.224        1.856       528.890
BB_Sudoku v0.5    1.432        0.075        0.903         3.275

All times in seconds


All were compiled with Visual C 6.0, Win32 Release configuration for full optimization, run on an Intel T5600 processor. Results may vary with different compilers / processors.

Because this is a comparison of algorithms, I did preform some tweaking as follows:
- changed argument handling to compile (<unistd> and getopt are not supported in Visual C)
- removed printf's to make timing more accurate
- recompiled as needed to either stop at 1 solution, or verify uniqueness (stop at 2)
- increased backtracking buffer size if needed for Gen 500,000

If no internal timing is provided, NTimer is used to time the solver.


PUZZLE COLLECTIONS USED:
------------------------

Top 50000 - http://www.sudokuvault.com/top50000.zip
A collection by Ruud of 50,000 hardish puzzles

Top 1465 - http://magictour.free.fr/top1465
A collection of very hard puzzles, especially for backtracking

Sudoku 17 - http://people.csse.uwa.edu.au/gordon/sudoku17
All known 17 clue sudoku (not including rotations, etc)

Gen 500,000 - http://www.enjoysudoku.com/gen_puzzles.zip
Computer generated random Sudoku from JasonLion, only 763 with unique solutions
This set is run to verify uniqueness (-S2 for some solvers)


SOLVERS TESTED:
---------------

Sudocoo by Glenn Fowler http://www.research.att.com/~gsf/
coded for simplicity over speed, under 150 lines not including comments

fast_solv_9r2 by Ignacio Zelaya http://www.setbb.com/sudoku/viewtopic.php?mforum=sudoku&t=1586&start=19
implementation of the DLX algorithm

Sudocoup by Glenn Fowler http://www.research.att.com/~gsf/
a more complete solver / generator from the same author as Sudocoo

zerodoku v2 by Jim Schirle - http://tinyurl.com/6krpwl
a fast brute force solver

BB_Sudoku by Brian Turner - http://tttarabians.com/sudoku/BB_Sudoku_v05.zip
a bit based solver which does some solving, then relies on brute force for completion


For those interested, here are the 3 hardest puzzles for my current solver:
Code:

1.......2.3.4...5...6...7...5...8......36.......9.1.4.2.....6...4...3.9...7.....1 - Solved        Time =   711.82 usec
6.......2.9.4...5...1...7...5.9.3......56........82.4...7...6...3...9.8.2.......1 - Solved        Time =   786.13 usec
.......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7..... - Solved        Time =   813.79 usec

brit
Back to top
View user's profile Send private message
ChPicard

Joined: 12 Mar 2008
Posts: 82
:
Location: Montreal, Canada

Items
PostPosted: Sat Jun 13, 2009 4:08 pm    Post subject: Re: Comparison of 5 fast solvers Reply with quote

briturner wrote:
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
Code:
                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






Here
http://www.setbb.com/phpbb/viewtopic.php?t=1267&mforum=sudoku
you can find many fast solvers using Dancing links method.

Quote:
Source code for DLX implementations

Sudoku programs by Dukuso
D. Knuth source code (can be converted to C)
Dancing Links solver in Python
Dancing Links implementation in Java
Dancing Links generator and solver in C by Antony
Dancing Links implementation in C++
Dancing Links implementation in PHP 5 by Ruud
Solver with dlx implementation in C# by humble programmer


Does anybody test yet their speed against BBSolver?
Back to top
View user's profile Send private message
willem

Joined: 26 Sep 2009
Posts: 3
:

Items
PostPosted: Sat Sep 26, 2009 8:33 am    Post subject: solver Reply with quote

how are these solvers mad excell, php or otherwise
Back to top
View user's profile Send private message
Adak

Joined: 27 Feb 2008
Posts: 87
:

Items
PostPosted: Sun Sep 27, 2009 1:23 am    Post subject: Reply with quote

The very fastest one's have been written either in C or C++.
Back to top
View user's profile Send private message
wapati

Joined: 12 Jun 2007
Posts: 622
:
Location: Canada

Items
PostPosted: Sun Sep 27, 2009 4:16 am    Post subject: Reply with quote

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


I saw one written in turtle-logo. It will be finished stepping through soon.

One can write durn bad stuff that finishes quick, these days.
Back to top
View user's profile Send private message
sudoking

Joined: 20 Oct 2009
Posts: 40
:

Items
PostPosted: Tue Oct 20, 2009 10:57 am    Post subject: sudocoo, fast_solv_9r2: improved Reply with quote

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.
Back to top
View user's profile Send private message
sudoking

Joined: 20 Oct 2009
Posts: 40
:

Items
PostPosted: Tue Oct 20, 2009 10:58 am    Post subject: Reply with quote

This is post 2
Back to top
View user's profile Send private message
sudoking

Joined: 20 Oct 2009
Posts: 40
:

Items
PostPosted: Tue Oct 20, 2009 10:58 am    Post subject: Reply with quote

This is post 3
Back to top
View user's profile Send private message
sudoking

Joined: 20 Oct 2009
Posts: 40
:

Items
PostPosted: Tue Oct 20, 2009 10:58 am    Post subject: Reply with quote

This is post 4
Back to top
View user's profile Send private message
sudoking

Joined: 20 Oct 2009
Posts: 40
:

Items
PostPosted: Tue Oct 20, 2009 10:59 am    Post subject: Reply with quote

This is post 5
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku All times are GMT
Goto page 1, 2  Next
Page 1 of 2

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron