FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Nodes per second Goto page Previous  1, 2, 3, 4, 5  Next          Sudoku Programmers Forum Index -> Programming sudoku View previous topic :: View next topic   Author Message MontagFTB Joined: 12 Sep 2005 Posts: 14 : Items Posted: Wed Sep 14, 2005 10:27 pm    Post subject: Something interesting and my times abik's 'underspecified' sudoku (from top of this thread): Code: 536.2.9....8...............6..285..9...9.3...8..761..4...........4......2.1.....7 UK solution multiple-solution snafu (from http://www.setbb.com/phpbb/viewtopic.php?t=86&highlight=1905&mforum=sudoku): Code: 5.6.2.9.3..8...5...........6..285..9...9.3...8..761..4...........4...3..2.1.5.6.7 side by side: Code: 536.2.9....8...............6..285..9...9.3...8..761..4...........4......2.1.....7 5.6.2.9.3..8...5...........6..285..9...9.3...8..761..4...........4...3..2.1.5.6.7 Just thought it was interesting... anyhow: I can find the 957,263 solutions to abik's puzzle in 4345.7 milliseconds (4.3457 sec). I can solve top95 in 93.909 miliseconds (0.093909 seconds) (stopping after the first solution for each puzzle). I'm improving... changes still need to be made, though... Blessings, Foster EDIT : I'm on a Powerbook G4 1.67GHz EDIT 2: I can solve 1101 in 596.489 miliseconds (0.596489 seconds) (stopping after the first solution for each puzzle). Back to top abik Joined: 10 Sep 2005 Posts: 18 : Location: Santa Clara Items Posted: Wed Sep 14, 2005 11:44 pm    Post subject: As for the similarity: no coincidence . I tested the 1905-solution puzzle first and then simply left out some more numbers to get an even higher multi-solution puzzle. Back to top MontagFTB Joined: 12 Sep 2005 Posts: 14 : Items Posted: Thu Sep 15, 2005 12:36 am    Post subject: similarity abik wrote: As for the similarity: no coincidence :D. I tested the 1905-solution puzzle first and then simply left out some more numbers to get an even higher multi-solution puzzle. :D Given the astronomical odds, it had to be something like that... Back to top gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Thu Sep 15, 2005 8:35 am    Post subject: Re: Something interesting and my times MontagFTB wrote: EDIT 2: I can solve 1101 in 596.489 miliseconds (0.596489 seconds) (stopping after the first solution for each puzzle). Where are the 1101 puzzles posted? List search turned up empty. thanks Back to top dukuso Joined: 14 Jul 2005 Posts: 424 : Location: germany Items Posted: Thu Sep 15, 2005 11:31 am    Post subject: the 1011 are at http://magictour.free.fr/msk_009 the 95 hard ones are at : http://magictour.free.fr/top95 I also uploaded an old, larger list of hard puzzles: http://magictour.free.fr/subig20 Back to top gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Thu Sep 15, 2005 5:46 pm    Post subject: dukuso wrote: the 1011 are at http://magictour.free.fr/msk_009 thanks So 1011, msk_009, and contest all refer to the same puzzles? Back to top dukuso Joined: 14 Jul 2005 Posts: 424 : Location: germany Items Posted: Thu Sep 15, 2005 10:07 pm    Post subject: yes Back to top gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Wed Sep 21, 2005 3:56 pm    Post subject: Here are some minimal puzzles for your timing pleasure: http://www.research.att.com/~gsf/sudoku/FNBTXZ-2-constrained.dat.gz My best timings on a 2.8GHz P4 are Code: puzzles=1453 guesses=17010 iterations=66205 seconds=0.163975 where guesses counts the backtrack nodes and iterations counts the number of times the constraints (forced cell, box claim, xwing etc.) were applied. Back to top abik Joined: 10 Sep 2005 Posts: 18 : Location: Santa Clara Items Posted: Wed Sep 21, 2005 6:20 pm    Post subject: timings On a 3.4GHz P4, my solver scores as follows (full search for all solutions vs. search for single solution only): Code: [C:/cmplr/PS/SUDO] sudoku FNBTXZ-2-constrained.dat #PUZZLES=1453 #SOLUTIONS=1453 nodes=2119450 clocks=630673607 secs=0.1870 cpn=297.0 Knps=11334.0 [C:/cmplr/PS/SUDO] sudoku -q FNBTXZ-2-constrained.dat #PUZZLES=1453 #SOLUTIONS=1453 nodes=1036167 clocks=305872219 secs=0.0930 cpn=295.0 Knps=11141.6 Back to top dukuso Joined: 14 Jul 2005 Posts: 424 : Location: germany Items Posted: Wed Sep 21, 2005 9:42 pm    Post subject: 0.8 sec. with 2.6GHz for the 1453 0.5 sec with a more optimized version 0.33 sec for finding the solution only exact-cover solver without dancing links, marking used rows and columns instead. Propagation for naked single, hidden single only. Here are some 16*16: http://magictour.free.fr/su16 these take me about 10 seconds, which varies 6sec-20sec. depending on the random initialization. Randomized choice of next column when there are columns of same size. Back to top xyzzy Joined: 24 Aug 2005 Posts: 80 : Items Posted: Wed Oct 19, 2005 4:38 am    Post subject: gsf has appears to have taken the FNBTXZ-2-constrained.dat.gz file off his web page, so I can't benchmark it. For dukuso's 16x16 problems, I can solve them all in 1.188 seconds on a P2-400MHz. So for 16x16 my solver is about 60 times faster. For 9x9, an updated list of benchmarks: top95: xyzzy 0.08373 sec @ P2-400MHz = 33.5 Mcycles (1899 cycles/node) gsf 0.039993 sec @ P4-2.8GHz = 112 Mcycles abik 0.1250 sec @ P4-3.4GHz = 425 Mcycles (340 cycles/node) nick70 0.10 sec @ P4-2.4GHz = 240 Mcycles dukuso 0.15 sec @ P4-2.6GHz = 390 Mcycles MontagFTB 0.0939 @ G4-1.67GHz = 157 Mcycles contest: xyzzy 0.253391 sec @ P2-400MHz = 101 Mcycles (934 c/n) gsf 0.05999 sec @ P4-2.8GHz = 168 Mcycles abik .0460 sec @ P4-3.4GHz = 156 Mcycles (348 c/n) Nick70 0.21 sec @ P4-2.4GHz = 504 Mcycles dukuso 0.30 sec @ P4-2.6GHz = 780 Mcycles (6842 c/n) MontagFTB 0.5965 @ G4-1.67GHz = 996 Mcycles Last edited by xyzzy on Wed Oct 19, 2005 8:08 am; edited 1 time in total Back to top dukuso Joined: 14 Jul 2005 Posts: 424 : Location: germany Items Posted: Wed Oct 19, 2005 5:44 am    Post subject: can you also do QWH-problems, sudokus without the blocks-constraint, which are used as benchmarks in math-research ? That would be interesting to compare, they have problems upto 70*70 ! what's "cycles/node" ? OK, thinking about it, probably your solver relies on sudoku-techniques so QWHs are not possible. But you should be able to generate some hard 16*16s or larger ?! This is so slow on my computer. What's your hardest 16*16 ? Or what's the fewest clues for 16*16 ? I had searched for hours , best was 84 AFAIR. Back to top gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Wed Oct 19, 2005 7:20 am    Post subject: xyzzy wrote: gsf has appears to have taken the FNBTXZ-2-constrained.dat.gz file off his web page, so I can't benchmark it. sorry, reposted here's a collection with 100K puzzles to make the p4's work for more than 1 sec http://www.research.att.com/~gsf/sudoku/FNBTXYW-1-con.dat.gz p4-2.8Mhz gets puzzles=100000 guesses=418455 iterations=2322071 seconds=5.065236 Back to top gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Wed Oct 19, 2005 7:31 am    Post subject: xyzzy wrote: For 9x9, an updated list of benchmarks: please add these timings top95: puzzles=95 guesses=2231 iterations=8626 seconds=0.039993 contest: puzzles=1011 guesses=5608 iterations=29045 seconds=0.059990 for the solver at http://www.research.att.com/~gsf/sudoku/ run on linux P4-2.8GHz, where guesses == backtrack nodes, iterations == constraint propagation iterations thanks Back to top xyzzy Joined: 24 Aug 2005 Posts: 80 : Items Posted: Wed Oct 19, 2005 8:21 am    Post subject: dukuso wrote: can you also do QWH-problems, sudokus without the blocks-constraint, which are used as benchmarks in math-research ? what's "cycles/node" ? I'd have to modify it to remove all the code relating to the blocks constraint, which is rather a lot of the code. I count nodes as every placement of a number in cell, via initial given, 'logic', or guessing. Cycles/node is the the number of cpu cycle used for each node visited. I have only written a sudoku solver, not a generator, validity checker, or a solver for sudoku like puzzles with multiple solutions. So, I have not found any new 16x16s. gsf wrote: contest: puzzles=1011 guesses=5608 iterations=29045 seconds=0.059990 for the solver at http://www.research.att.com/~gsf/sudoku/ run on linux P4-2.8GHz, where guesses == backtrack nodes, iterations == constraint propagation iterations thanks Ok, I edited my post to add in your times. How do you solve the contest list with only 29045 constraint propagations when there are more than 29045 empty cells to fill? Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> Programming sudoku All times are GMT Goto page Previous  1, 2, 3, 4, 5  Next Page 3 of 5   Jump to: Select a forum Sudoku----------------Solving sudokuSetting sudokuProgramming sudokuThe mathematics of sudokuExotic sudoku Library----------------PuzzlesSoftwareSudoku elsewhere Not sudoku----------------Random thoughtsForum feedback  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   Powered by phpBB © 2001, 2005 phpBB Group Igloo Theme Version 1.0 :: Created By: Andrew Charron