Multiple Solutions

Programs which generate, solve, and analyze Sudoku puzzles

Postby stuartn » Wed Nov 09, 2005 11:31 am

Can anyone point at an algorithm that'll tell me how many solutions there are? - do Angusj's and simes's applications actually work each one out and count as they go?

stuartn
stuartn
 
Posts: 211
Joined: 18 June 2005

Postby Bigtone53 » Wed Nov 09, 2005 12:23 pm

The easiest way is to pop it into one of the programs


The solver on http://sudoku.sourceforge.net will tell you whether a puzzle has a unique solution, as well as telling you the next step
Bigtone53
 
Posts: 413
Joined: 19 September 2005

Postby CathyW » Wed Nov 09, 2005 12:58 pm

Simes' application counts the solutions and you can click a button to view all the solutions if you wish. Have no idea how it is achieved though.
CathyW
 
Posts: 316
Joined: 20 June 2005

Postby simes » Wed Nov 09, 2005 1:02 pm

stuartn wrote:Can anyone point at an algorithm that'll tell me how many solutions there are? - do Angusj's and simes's applications actually work each one out and count as they go?
I can't speak for Angusj's but that's exactly what mine does - works out each possible solution, and counts as it goes.

S
simes
 
Posts: 324
Joined: 11 March 2005
Location: UK

Postby rubylips » Thu Nov 10, 2005 11:07 am

There's no easy way for a human to evaluate whether a puzzle has multiple solutions. The procedure is straightforward for a computer, however. The solver knows that it will have to guess in order to find (potentially) all the solutions to a puzzle. The two key components of a guess algorithm are the ability to write the current grid state to a stack and the ability to recognize whether the current grid state has become illegal (presumably due to a faulty guess taken earlier) - at which point, the solver will retrieve the last known good position from the stack. The key idea of a Multiple Solutions Counter is that, when it finds it has solved a puzzle successfully, it increments the solution counter then declares the current position illegal. This forces the solver to retrace its steps to the last known good position, from where it will seek an alternative solution. In this way, the solver will iterate through all possible solutions to a puzzle.

Of course, you know that when you solve a puzzle by purely logical means that puzzle must have a unique solution.
rubylips
 
Posts: 149
Joined: 01 November 2005

Postby QBasicMac » Thu Nov 10, 2005 7:23 pm

stuartn wrote:Can anyone point at an algorithm that'll tell me how many solutions there are?


I wrote a simple one that runs fairly fast in QBasic. I won't bore you with the details, but the basic (no pun intended) algorithm is this

Let Puzzle$ be "-1-35-279--3....etc." 81 values
Call Solve1(Puzzle$)
Print count of solutions

That's it. The recursive Solve1 will do the rest.

Mac

Code: Select all
SUB Solve1(Puzzle$)
  Solve as much as possible using as many techniques as you know
  Case: Solved
    Add 1 to count of solutions and return
  Case: Impossible condition
    Just return
  Case: Stuck
    Let Temp$ = solution so far
    Pick a random cell, say 13, that has some pencilmarks, say 3 and 9.
    mid$(Temp$,13,1)="3": Call Solve1(Temp$)
    mid$(Temp$,13,1)="9": Call Solve1(Temp$)
    return
QBasicMac
 
Posts: 441
Joined: 13 July 2005

Postby rubylips » Thu Nov 10, 2005 8:40 pm

It's fine to use recursive calls if the number of solutions is known to be small (though I'm not sure how you'd know) but you'll almost certainly find it necessary to use an iterative technique to count large numbers of solutions in order to avoid stack overflows.
rubylips
 
Posts: 149
Joined: 01 November 2005

Postby cho » Fri Nov 11, 2005 9:50 am

rubylips wrote:It's fine to use recursive calls if the number of solutions is known to be small (though I'm not sure how you'd know) but you'll almost certainly find it necessary to use an iterative technique to count large numbers of solutions in order to avoid stack overflows.

He's using qbasic. There's no reason for a processor stack to be utilized to hold temp$ (or any other string). I'm not even sure a push command is available, but would have to be explicitly used if so.

cho
cho
 
Posts: 18
Joined: 07 August 2005


Return to Software

cron