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   

Need to test my solver
Goto page Previous  1, 2
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Thu Apr 24, 2008 12:19 am    Post subject: Reply with quote

Seaplusplus wrote:
Code:
000|050|021
000|103|085
051|020|000
-----------
100|507|000
004|000|150
095|401|030
-----------
519|000|473
002|019|568
000|045|219


before it goes brute force

at this position there is a hidden single 7 at r2c5 (edited to change naked to hidden, thanks lunatic)

also, post puzzle grids inside [ code ] ... [ /code ] tags
I've done that in this reply


Last edited by gsf on Fri Apr 25, 2008 3:57 pm; edited 1 time in total
Back to top
View user's profile Send private message Visit poster's website
Lunatic

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

Items
PostPosted: Fri Apr 25, 2008 10:48 am    Post subject: Reply with quote

gsf wrote:
at this position there is a naked single 7 at r2c5


Isn't that not a hidden single ?
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~
Back to top
View user's profile Send private message Send e-mail Visit poster's website
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Fri Apr 25, 2008 3:55 pm    Post subject: Reply with quote

Lunatic wrote:
gsf wrote:
at this position there is a naked single 7 at r2c5


Isn't that not a hidden single ?

yes it is -- thanks and sorry

now waiting for my 3rd strike on this thread
Back to top
View user's profile Send private message Visit poster's website
m_b_metcalf

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

Items
PostPosted: Tue Apr 29, 2008 3:49 pm    Post subject: Reply with quote

gsf wrote:

for an input file consisting of 10,000 copies of the wiki worst case (actually, the wiki article is a worst case)
sudocoo.c (the code danny mentioned) solves ~600 puzzles/second/Ghz
my solver with option -qFN (singles and backtracking with forward checking) solves ~7000 puz/sec/Ghz
and sudocoup (backtracking with integrated singles forward checking on each placement) solves ~10000 puz/sec/Ghz


Glenn,
Clearly a more realistic test would be, say, of the first 10,000 puzzles in top50000, none of which can be solved only by singles. Do you have ratings for that? I'm currently running at about 500 puzzles/s/GHz on that sample using singles and backtracking, and would appreciate knowing how many orders of magnitude I've still to achieve.

Thanks,

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

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Tue Apr 29, 2008 4:15 pm    Post subject: Reply with quote

m_b_metcalf wrote:
gsf wrote:

for an input file consisting of 10,000 copies of the wiki worst case (actually, the wiki article is a worst case)
sudocoo.c (the code danny mentioned) solves ~600 puzzles/second/Ghz
my solver with option -qFN (singles and backtracking with forward checking) solves ~7000 puz/sec/Ghz
and sudocoup (backtracking with integrated singles forward checking on each placement) solves ~10000 puz/sec/Ghz


Clearly a more realistic test would be, say, of the first 10,000 puzzles in top50000, none of which can be solved only by singles. Do you have ratings for that? I'm currently running at about 500 puzzles/s/GHz on that sample using singles and backtracking, and would appreciate knowing how many orders of magnitude I've still to achieve.

right
I wanted to emphasize that
(1) timing one puzzle will probably be in the noise
(2) divide by Ghz to normalize across cpu clocks
(3) the wiki worst case is a bad example based on bad assumptions
but in doing that did not come up with a good general test

the top50000 will certainly exercize backtracking for singles only solvers

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

sudocoo has lightweight state per backtrack ply
sudocoup is heavyweight
and sudoku is in between
Back to top
View user's profile Send private message Visit poster's website
m_b_metcalf

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

Items
PostPosted: Tue Apr 29, 2008 6:10 pm    Post subject: Reply with quote

gsf wrote:
m_b_metcalf wrote:

Clearly a more realistic test would be, say, of the first 10,000 puzzles in top50000, none of which can be solved only by singles. Do you have ratings for that? I'm currently running at about 500 puzzles/s/GHz on that sample using singles and backtracking, and would appreciate knowing how many orders of magnitude I've still to achieve.

sudoku (my solver with -qFN -f- (no output)) ~2200 puz/sec/Ghz


Well, that's encouraging. I think your sudoku is the nearest comparison, and I'm off only by a factor of 4 to 5.

Thanks,

Mike Metcalf
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 Previous  1, 2
Page 2 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