The New Sudoku Players' Forum

[stuartn]

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

[Bigtone53]

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

[CathyW]

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.

[simes]

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

[rubylips]

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.

[QBasicMac]

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


[rubylips]

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.

[cho]

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