## Multiple Solutions

Programs which generate, solve, and analyze Sudoku puzzles
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

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

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

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

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

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

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

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