```Date: Wed, 24 May 2006 11:21:12 -0400 Reply-To: Talbot Michael Katz Sender: "SAS(r) Discussion" From: Talbot Michael Katz Subject: Re: SUDOKU Solver Informal Comparisons Oops, I gave a worst case scenario -- the LARGEST number of possible combinations occurs when the 18 filled cells have 2 of each number filled in. The SMALLEST number of possible combinations would occur if the 18 filled cells consisted of all 9 instances of just 2 numbers. Ignoring the fact that such a Sudoku puzzle could not have a unique solution, the number of combinations to check is only 63!/(9!)**7 ~ 2*10**48, not nearly as bleak a situation as the one I described previously -- you'd need only about a billion parallel universes to reach a conclusion. *Whew!* Of course, all the solvers we've seen require far fewer steps to finish, because they use the structure of the puzzle to eliminate many possibilities. -- TMK -- "The Macro Klutz" On Tue, 23 May 2006 14:26:32 -0400, Talbot Michael Katz wrote: >So, you want to try all the combinations, eh? > >Okay, suppose you have 18 out of 81 cells filled. That leaves you with 63 >cells to fill. The number of possible combinations depends on which 63 >numbers you have left, but the smallest possible number of combinations >would be if you had filled in 2 of each and had 7 of each left. In that >case, you'd have 63!/(7!)**9 ~ 9*10**53. The fastest computers can do >around 10**12 operations per second. Suppose you had a computer a million >times faster, and you could evaluate 10**18 combinations per second. The >universe is considered around 15 billion years old, but let's suppose it's >a bit older, 10**20 seconds (more than a trillion years). So, if you'd >run this super duper computer starting at the Big Bang up until today, >you'd have gotten through at most 10**38 Sudoku combinations. So you'd >need to have had another quadrillion universes in parallel working on this >to have finished by exhaustive search. > >Let's just say it's not the most efficient way to Sudoku. > >-- TMK -- >"The Macro Klutz" > > >On Tue, 23 May 2006 10:05:13 -0400, T J wrote: > >>I thought it will take forever to loop through all possible values for >each >>empty cell to find the solution. Can someone give an estimate how >>many "step"s it would take to try out all possible/eligible numbers, given >>that there are 18 numbers are already fixed? >> >>Thanks, >> >>-TJ >> >> >> >>On Mon, 22 May 2006 18:24:48 -0400, Talbot Michael Katz >>wrote: >> >>>Hi. >>> >>>In case anyone out there hasn't gotten totally fed up with the Sudoku >>>threads, I thought I'd compare some of the solvers we've seen on a few >>>different puzzles. I used DeVenezia's slickly packaged data step solver, >>>and the PROC CLP, and PROC LP solvers. I apologize to Hoyle and TJ for >>>not running their solvers (which are already known not to solve every >>>uniquely solvable Sudoku puzzle); Gerlach didn't show us his code, so I >>>couldn't try it. I didn't notice anyone else posting a solution. >>> >>>Here are results for three different puzzles. This is a totally >>>unscientific benchmark, I didn't get precise timing for DeVenezia's >solver >>>because I just ran his code as is, without extracting the solver from the >>>SCL wrapper. >>> >>>1. Hoyle's Example >>> >>> ......... >>> .4.1.6.9. >>> .7.3.9.8. >>> .13...75. >>> 7..5.1..8 >>> 5.......6 >>> 6.......1 >>> .52...84. >>> 3..9.2..5 >>> >>> DeVenezia: (real time is totally skewed by the use of the >>>interface) >>> Done in step=24362 >>> NOTE: DATA statement used (Total process time): >>> real time 6.04 seconds >>> cpu time 0.19 seconds >>> >>> PROC CLP: >>> NOTE: PROCEDURE CLP used (Total process time): >>> real time 0.11 seconds >>> cpu time 0.03 seconds >>> >>> PROC LP: >>> NOTE: PROCEDURE LP used (Total process time): >>> real time 0.58 seconds >>> cpu time 0.44 seconds >>> >>> >>>2. Bourdages' example: >>> >>> .......7. >>> .197..... >>> 83....... >>> .....6.5. >>> ....4.7.3 >>> 4..38.... >>> 64...8... >>> ...2...4. >>> ..8..1369 >>> >>> DeVenezia: (real time is totally skewed by the use of the >>>interface) >>> Done in step=140417 >>> NOTE: DATA statement used (Total process time): >>> real time 5.58 seconds >>> cpu time 0.59 seconds >>> >>> PROC CLP: >>> NOTE: PROCEDURE CLP used (Total process time): >>> real time 0.23 seconds >>> cpu time 0.23 seconds >>> >>> PROC LP: >>> NOTE: PROCEDURE LP used (Total process time): >>> real time 0.42 seconds >>> cpu time 0.40 seconds >>> >>> >>>3. 17 cell puzzle from >>>(http://www.csse.uwa.edu.au/~gordon/sudokumin.php): >>> >>> .......1. >>> 4........ >>> .2....... >>> ....5.4.7 >>> ..8...3.. >>> ..1.9.... >>> 3..4..2.. >>> .5.1..... >>> ...8.6... >>> >>> DeVenezia: (real time reasonably accurate) >>> Done in step=62062362 >>> NOTE: DATA statement used (Total process time): >>> real time 3:29.16 >>> cpu time 3:22.98 >>> >>> PROC CLP: >>> NOTE: PROCEDURE CLP used (Total process time): >>> real time 1:16.51 >>> cpu time 1:16.38 >>> >>> PROC LP: >>> NOTE: PROCEDURE LP used (Total process time): >>> real time 0.39 seconds >>> cpu time 0.39 seconds >>> >>> >>> >>>So, it's a mixed bag. For easy puzzles, all three solvers >>>are "instantaneous," well under one second. When the problems get >harder, >>>both the data step solver and PROC CLP begin to degrade. The PROC LP >>>solver may not always be the fastest, but it appears to be the most >>>reliable under any situation. I tried another of the 17 cell puzzles >with >>>the PROC CLP and PROC LP solvers: >>> .......12 >>> ....35... >>> ...6...7. >>> 7.....3.. >>> ...4..8.. >>> 1........ >>> ...12.... >>> .8.....4. >>> .5....6.. >>> >>>I didn't try the data step solver on it because the PROC CLP solver took >a >>>half-hour(!), and I didn't want to wait for another long time (although >it >>>might not have taken a long time, I don't know because I didn't try). >But >>>the PROC LP solver got it in a half-second. >>> >>> >>> >>>-- TMK -- >>>"The Macro Klutz" ```

Back to: Top of message | Previous page | Main SAS-L page