View previous topic :: View next topic |
Author |
Message |
| gsf
| Joined: 18 Aug 2005 | Posts: 411 | : | Location: NJ USA | Items |
|
Posted: Thu Apr 24, 2008 12:19 am Post subject: |
|
|
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 |
|
|
| Lunatic
| Joined: 11 Mar 2007 | Posts: 166 | : | Location: Ghent - Belgium | Items |
|
Posted: Fri Apr 25, 2008 10:48 am Post subject: |
|
|
gsf wrote: | at this position there is a naked single 7 at r2c5 |
Isn't that not a hidden single ? _________________ Marc
~~~<><~~~<><~~~<><~~~<><~~~ |
|
Back to top |
|
|
| gsf
| Joined: 18 Aug 2005 | Posts: 411 | : | Location: NJ USA | Items |
|
Posted: Fri Apr 25, 2008 3:55 pm Post subject: |
|
|
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 |
|
|
| m_b_metcalf
| Joined: 13 Mar 2006 | Posts: 210 | : | Location: Berlin | Items |
|
Posted: Tue Apr 29, 2008 3:49 pm Post subject: |
|
|
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 |
|
|
| gsf
| Joined: 18 Aug 2005 | Posts: 411 | : | Location: NJ USA | Items |
|
Posted: Tue Apr 29, 2008 4:15 pm Post subject: |
|
|
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 |
|
|
| m_b_metcalf
| Joined: 13 Mar 2006 | Posts: 210 | : | Location: Berlin | Items |
|
Posted: Tue Apr 29, 2008 6:10 pm Post subject: |
|
|
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 |
|
|
|