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

8 posts
• Page **1** of **1**

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

I can't speak for Angusj's but that's exactly what mine does - works out each possible solution, and counts as it goes.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?

S

SadMan Software

http://www.sadmansoftware.com/sudoku/

http://www.sadmansoftware.com/sudoku/

- 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.

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

8 posts
• Page **1** of **1**