| View previous topic :: View next topic |
| Author |
Message |
| Seaplusplus
| | Joined: 23 Mar 2008 | | Posts: 12 | | : | |
Items |
|
 Posted: Mon Apr 21, 2008 2:50 pm Post subject: Need to test my solver |
 |
|
Hey guys, i made a brute force solver and am looking to check something. With regards to the following puzzle, how many solutions does it have?
000|004|500
000|800|000
702|003|900
-----------
508|000|060
300|000|007
090|000|201
-----------
001|600|308
000|005|000
004|290|000
(Please say 7)
Thanks  |
|
| Back to top |
|
 |
| m_b_metcalf
| | Joined: 13 Mar 2006 | | Posts: 210 | | : | | Location: Berlin |
Items |
|
| Posted: Mon Apr 21, 2008 3:21 pm Post subject: Re: Need to test my solver |
|
|
| Seaplusplus wrote: |
(Please say 7)
|
Your luck is in: | Code: |
brute found 7 solution(s). Last was:
1 8 3 9 6 4 5 7 2
9 6 5 8 7 2 1 4 3
7 4 2 1 5 3 9 8 6
5 2 8 7 3 1 4 6 9
3 1 6 4 2 9 8 5 7
4 9 7 5 8 6 2 3 1
2 5 1 6 4 7 3 9 8
8 7 9 3 1 5 6 2 4
6 3 4 2 9 8 7 1 5
|
Regards,
Mike Metcalf |
|
| Back to top |
|
|
| Seaplusplus
| | Joined: 23 Mar 2008 | | Posts: 12 | | : | |
Items |
|
| Posted: Mon Apr 21, 2008 3:26 pm Post subject: |
|
|
I could kiss you right now
 |
|
| Back to top |
|
|
| Seaplusplus
| | Joined: 23 Mar 2008 | | Posts: 12 | | : | |
Items |
|
| Posted: Wed Apr 23, 2008 12:04 am Post subject: |
|
|
Just out of interest, does anybody know some sort of benchmarking site.
My solver seems to be fairly slow xD, then again its a not a very intelligent brute forcer. |
|
| Back to top |
|
|
| jmelloy
| | Joined: 21 Apr 2008 | | Posts: 2 | | : | |
Items |
|
| Posted: Wed Apr 23, 2008 1:16 am Post subject: |
|
|
Mine solves your 7 board puzzles in about a 50 milliseconds. I generally try to do an apples-to-apples comparison, though, so I found another solver written in Python and tried my speed comparable to his. It solves most puzzles in under a quarter of a second.
If you're trying to make it faster, break it into pieces and see what's slow. My first iteration took 2 seconds or so for the tough puzzles, and now on the same puzzle it's at about a quarter of a second. |
|
| Back to top |
|
|
| Adak
| | Joined: 27 Feb 2008 | | Posts: 87 | | : | |
Items |
|
| Posted: Wed Apr 23, 2008 1:16 am Post subject: |
|
|
| Seaplusplus wrote: | Just out of interest, does anybody know some sort of benchmarking site.
My solver seems to be fairly slow xD, then again its a not a very intelligent brute forcer. |
I don't know of any, but here's what I use. I take the first 100 puzzle grids from Gordon Royle's website, and have my solver run through all 100 of them, in batch mode. It's not so large that it takes hours to run through, and it's not so trivial that it's done in 0.0 seconds, (by my solver, at least not yet!).
The result is VERY dependent on your hardware as well as your solver's algorithm/implementation.
This is my tester:
| Code: |
000000010400000000020000000000050407008000300001090000300400200050100000000806000
000000010400000000020000000000050604008000300001090000300400200050100000000807000
000000012000035000000600070700000300000400800100000000000120000080000040050000600
000000012003600000000007000410020000000500300700000600280000040000300500000000000
000000012008030000000000040120500000000004700060000000507000300000620000000100000
000000012040050000000009000070600400000100000000000050000087500601000300200000000
000000012050400000000000030700600400001000000000080000920000800000510700000003000
000000012300000060000040000900000500000001070020000000000350400001400800060000000
000000012400090000000000050070200000600000400000108000018000000000030700502000000
000000012500008000000700000600120000700000450000030000030000800000500700020000000
000000012700060000000000050080200000600000400000109000019000000000030800502000000
000000012800040000000000060090200000700000400000501000015000000000030900602000000
000000013000500070000802000000400900107000000000000200890000050040000600000010000
000000013000700060000508000000400800106000000000000200740000050020000400000010000
000000013000700060000509000000400900106000000000000200740000050080000400000010000
000000013000800070000502000000400900107000000000000200890000050040000600000010000
000000013020500000000000000103000070000802000004000000000340500670000200000010000
000000013040000080200060000609000400000800000000300000030100500000040706000000000
000000013040000080200060000906000400000800000000300000030100500000040706000000000
000000013040000090200070000607000400000300000000900000030100500000060807000000000
000000013040000090200070000706000400000300000000900000030100500000060807000000000
000000013200800000300000070000200600001000000040000000000401500680000200000070000
000000013400800000200000070000400900001000000060000000000501600380000200000070000
000000014000000203800050000000207000031000000000000650600000700000140000000300000
000000014000020000500000000010804000700000500000100000000050730004200000030000600
000000014008005000020000000000020705100000000000000800070000530600140000000200000
000000014008005000020000000000020805100000000000000700070000530600140000000200000
000000014008009000020000000000020805100000000000000700070000930600140000000200000
000000014700000000000500000090014000050000720000600000000900805600000900100000000
000000014790000000000200000000003605001000000000000200060000730200140000000800000
000000014970000000000200000000003605001000000000000200060000730200140000000800000
000000015000400070300060000800000200000104000400500000000023600010000000070000000
000000015000400070400000000609000300000100800000700000500030200000060040010000000
000000015000800070300000000408000300000100400000700000500040200000090060010000000
000000015000800070400000000609000300000100800000700000500030200000060040010000000
000000015000830000000000200023000800000001000080000000105040000000600720900000000
000000015000830000000000200026000800000001000080000000105040000000300720900000000
000000015000900070400000000608000300000100800000700000500030200000060040010000000
000000015000900070400000000609000300000100800000700000500030200000060040010000000
000000015000900080300000000704000300000100400000800000500040200000070060010000000
000000015000900080400000000704000300000100900000800000500030200000070060010000000
000000015020060000000000408003000900000100000000008000150400000000070300800000060
000000015040080000000000300000040260500107000900000000300500000080000400000900000
000000015300600000000000080600050200000001000000000040010200700000760300008000000
000000015790000000000200000000008706001000000000000900070000830400150000000300000
000000016000500040300070000900000200000408000700600000000023700040000000010000000
000000016000708000000000050501200000300000800600000000040000200000053000080010000
000000016000900080500000000405000300000100500000800000600040200000030070010000000
000000016040005000000020000000600430200010000300000500000003700100800000002000000
000000016070000040050200000400060300000005200000041000000900780100000000000000000
000000016070000040050200000400060300000008200000041000000500790100000000000000000
000000016200000000000300000601700002000900500400000000030000800000060040050040000
000000016200080000009000000000420500010000000000000200000106030500000780000900000
000000017090600000000000030400500200001000000000080000720000600000410500000003000
000000017090600000000000050200000803000050400000001000600200300041070000000000000
000000017090800000000000040007060300050000200000001000600300800401000000000050000
000000017600020000000000000153000000000080200007000000400301500020000600000700000
000000018020500000000000000040000700600000500000041000000700260108300000400000000
000000018050600000000000030400500200001000000000090000820000600000410700000003000
000000018200400000000000070000008003000500200010000000502000600000040300000017000
000000018700040000000000030420000700000001000000300000500070200601800000040000000
000000019000250000000000000091000030000400700030000000400000208200060500000001000
000000019030050000000000020109000000000400700000870000000102000060000800500000300
000000019030050000000000020109000000000400800000870000000102000060000700500000300
000000019070000030200800000050600200001000000000200000000019500600000400000030000
000000019300600000000000000600080500040000300000010000480000070000200400010900000
000000019500600000000000000600080500040000300000010000380000040000200700010900000
000000019500600000000000000600080500040000300000010000480000070000200400010900000
000000019500800000000000000300070500040000300000010000470000060000200400010900000
000000019800500000000000000300070500040000300000010000470000060000200400010900000
000000021000030070040080000100207000050000400000000003200100000000040500000600000
000000021000083000000040000500200070080000400030900000000060800100500000200000000
000000021000083000000040000500200070080000400030900000000060800100700000200000000
000000021000306000000800000400010600000700300200000000000090040530000000086000000
000000021000407000000008000031060000000000750020000000500210000400000800000300000
000000021000500030400600000000021000800000007500000600000400800010070000030000000
000000021004090000070000030100203000500800000006000000200000600000060400030000000
000000021005080000600000000000670300120000500400000000000201040003000000080000000
000000021006800000000000070070021000020000400000005000500430600100000000000600000
000000021030400000700000000100082000000000540000000000000560300290000000004700000
000000021030600000000080000201000050500400000000370000700002000080000300000000600
000000021040500000700000000100082000000000650000000000000610400320000000005700000
000000021040500000800000000700092000000000650000000000000610400320000000005800000
000000021040600000000000000201000050500800000000400300700020000060000800000300400
000000021050030000000800000102000070700300000000540000600002000030000400000000500
000000021060300000000708000100050040070000300000020000200040000000600800500000000
000000021060500000000090000400002000070000300000600000102400000000030640800000000
000000021060700000000000000402000000000600300500000700000340050080000600100002000
000000021070030000000040000100205040030000800000100000200600000000070300600000000
000000021070030000000090000100205040030000800000100000200600000000070300600000000
000000021070300000000000000402000000000700300600000800000540060090000500100002000
000000021070300000000408000100060050030000400000020000200050000000700800600000000
000000021080300000000409000100060050030000400000020000200070000000800900500000000
000000021090300000000000000402000000000700300600000700000540060080000500100002000
000000021090300000000060000201000050500400000000970000600002000080000300000000900
000000021090700000000000000000514000630000000000002000000600930001040000200000800
000000021300050000000000000500630000010000080000000500704000600600200000000108000
000000021300050000000000000500630000010000080000000900704000600600200000000108000
000000021300050000000000000500830000010000090000000500704000600600200000000109000
|
If the above isn't just right, the full list of 45k+ can be had from Gordon's website. URL is easily found on the Sudoku Players Forum.
What logic do you use for your brute force solver? If you can describe it in some detail, I'm sure you'll get a lot of hints and recommendations.
Congrats on the program, Seaplusplus! |
|
| Back to top |
|
|
| Seaplusplus
| | Joined: 23 Mar 2008 | | Posts: 12 | | : | |
Items |
|
| Posted: Wed Apr 23, 2008 2:41 am Post subject: |
|
|
My program takes 0.125 seconds to find those 7 solutions. It uses a simple method which I found on wikipedia. I tried a more fancy method with lists and logic, however whilst i thought it would have been quicker, turns out it wasn't.
From wikipedia
| Code: | //"Briefly, a brute force program would solve a puzzle by placing the
//digit "1" in the first cell and checking if it is allowed to be there.
//If there are no violations (checking row, column, and box constraints)
//then the algorithm advances to the next cell, and places a "1" in that cell.
//When checking for violations, it is discovered that the "1" is not allowed,
//so the value is advanced to a "2". If a cell is discovered where none of
//the 9 digits is allowed, then the algorithm leaves that cell blank and moves
//back to the previous cell. The value in that cell is then incremented by one.
//The algorithm is repeated until the allowed value in the 81st cell is
//discovered." |
Infact I made my code much simpler with this method, got rid of a few functions and managed to solve a puzzle in 0.013 seconds which took over a minute before. It's strange though, I can solve what wiki describes as an almost worst case sudoku for brute force
| Code: | 000|000|000
000|003|085
001|020|000
-----------
000|507|000
004|000|100
090|000|000
-----------
500|000|073
002|010|000
000|040|009 |
In just a little over 2 minutes. It says it can take up to 45 minutes so I'm pretty happy. I might benchmark with the batches later though I think i will take a break from coding now
Thanks for the help guys |
|
| Back to top |
|
|
| daj95376
| | Joined: 05 Feb 2006 | | Posts: 349 | | : | |
Items |
|
| Posted: Wed Apr 23, 2008 3:19 am Post subject: |
|
|
| gsf posted the C source code to a brute force backtracking solver in this forum quite awhile back. I ran your last puzzle through it and the entire process -- including loading a DOS Window, executing the program, writing the output, and exiting the program and DOS Window -- went easily in under a second on my Pentium III 450 MHz computer. |
|
| Back to top |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
| Posted: Wed Apr 23, 2008 4:39 am Post subject: |
|
|
| daj95376 wrote: | | gsf posted the C source code to a brute force backtracking solver in this forum quite awhile back. I ran your last puzzle through it and the entire process -- including loading a DOS Window, executing the program, writing the output, and exiting the program and DOS Window -- went easily in under a second on my Pentium III 450 MHz computer. |
thanks Danny
I'll address all of the related posts here
first, to normalize for cpu speed just divide the puzzles solved per second by the cpu Ghz
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
these are all C -- I would be surprised if interpreted languages like perl/python/java came
under an order of magnitude of these numbers
in general, be wary of algorithms, and articles about algorithms, that fall into worst case
behavior on input that exploits ordering (as in always checking positions from 0..80 and
values from 1..9) -- usually ordering deficiencies can be handled with a few code optimizations
(this is the case for the algorithms I posted) |
|
| Back to top |
|
|
| m_b_metcalf
| | Joined: 13 Mar 2006 | | Posts: 210 | | : | | Location: Berlin |
Items |
|
| Posted: Wed Apr 23, 2008 7:12 pm Post subject: |
|
|
| gsf wrote: |
my solver with option -qFN (singles and backtracking with forward checking) solves ~7000 puz/sec/Ghz |
Glenn, Sorry to have the temerity to question you again for the second time this week, but when I looked into my solver, I discoverd that the puzzle was being completely solved by singles so that the backtracking was never even entered. Might that also be the case with yours? In any case, it just goes to prove your point:
| gsf wrote: |
in general, be wary |
Regards,
Mike Metcalf |
|
| Back to top |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
| Posted: Wed Apr 23, 2008 7:50 pm Post subject: |
|
|
| m_b_metcalf wrote: | | gsf wrote: |
my solver with option -qFN (singles and backtracking with forward checking) solves ~7000 puz/sec/Ghz |
Glenn, Sorry to have the temerity to question you again for the second time this week, but when I looked into my solver, I discoverd that the puzzle was being completely solved by singles so that the backtracking was never even entered. Might that also be the case with yours? In any case, it just goes to prove your point:
| gsf wrote: |
in general, be wary |
|
the question that got you into trouble was to g.r.emlin -- I'm out of the loop there
well right you are
the simplest solver sudocoo does backtrack, the other two, sudoku and sudocoup, do
not backtrack because of the singles cascade
there is a knee where backtracking will outperform constraints, somwhere between
locked candidates and n-tuples
thanks |
|
| Back to top |
|
|
| Seaplusplus
| | Joined: 23 Mar 2008 | | Posts: 12 | | : | |
Items |
|
| Posted: Wed Apr 23, 2008 9:53 pm Post subject: |
|
|
Just a quick note.
If I dont disable my initial logic checks (my solver tries logic then goes brute force). For the 'worst case' brute force puzzle it fills in 20 squares before going brute force.
It finishes the puzzle using brute force in 78 miliseconds |
|
| Back to top |
|
|
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
| Posted: Wed Apr 23, 2008 10:34 pm Post subject: |
|
|
| Seaplusplus wrote: | Just a quick note.
If I dont disable my initial logic checks (my solver tries logic then goes brute force). For the 'worst case' brute force puzzle it fills in 20 squares before going brute force.
It finishes the puzzle using brute force in 78 miliseconds |
as m_b_metcalf noted, the wiki worst case example solves with naked and hidden singles
it may be time to debug your singles code
can you post the pencimark grid at the point where it goes to brute force? |
|
| Back to top |
|
|
| Seaplusplus
| | Joined: 23 Mar 2008 | | Posts: 12 | | : | |
Items |
|
| Posted: Wed Apr 23, 2008 11:28 pm Post subject: |
|
|
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 |
|
| Back to top |
|
|
| Adak
| | Joined: 27 Feb 2008 | | Posts: 87 | | : | |
Items |
|
| Posted: Thu Apr 24, 2008 12:06 am Post subject: |
|
|
| He means your grid that has the list of every possible candidate number remaining, for every cell. Like the pencil marks you might make to keep track of the possibles, when you do a puzzle by hand. |
|
| Back to top |
|
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
