what should a solver do when there is no unique solution?

Bob Hanson

What should a solver do when it discovers there is no unique solution?

Sudoku Assistant http://www.stolaf.edu/people/hansonr/sudoku

simply reports that it is "stuck" and that the puzzle probably does not have a unique solution. Is that the proper response?

This occurs when the hypothesis "X can be eliminated" cannot be proved for any remaining node. That makes sense, of course, because if there are ultimately two possible solutions, then for some cells you can never prove which of the two possible values can be eliminated.

It seems to me this could be valuable -- a solver that proves a puzzle is not unique. Yes? No? Should it just go on and solve it anyway?

What do other solvers do?

Test sample:

9.6.83..2
1.56.9...
..3..7.69
75439.62.
3...6..95
.69.5...4
59.83.2..
6...759.3
43.91....

Thanks.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

abik · Posted: Mon Nov 07, 2005 5:36 am Post subject:

Hi Bob,
We had a similar discussion in the nodes-per-second thread (see http://www.setbb.com/phpbb/viewtopic.php?t=222&mforum=sudoku). I think solvers should simply report the impurity together with the number of solutions, see output of my solver below. Solving for just one solution can substantially reduce search time, however.
Aart
http://www.aartbik.com/

dukuso · Posted: Mon Nov 07, 2005 7:52 am Post subject:

and if there are really many solutions, too many to count
them in reasonable time, then it would be nice if the
solver could give an estimate of the number of solutions !

(using Monte Carlo tries or such)

Ruud · Site Admin

I've implemented it this way:

When a puzzle is loaded/pasted or manually entered, a fast backtracking solver using Knuth's dancing links algorithm first validates the puzzle. This routine can report the state of the puzzle:

1. Valid (only one solution)
2. Invalid (no solution)
3. Invalid (more than one solution)

I've limited this routine, so that it will not search for solutions forever. At this moment it stops at 100,000 solutions found. (this takes less than a second)

When a puzzle is invalid, the human-style solver will not be called, and the state is reported by the program.

Validating the puzzle is important if you want to implement techniques like uniqueness tests and magic cells.

The solver could be configured in such a way thay it can find all possible solutions, but that is more a feature for a math program, not for a puzzler's assistant. I think the average puzzler may want to know if it's a 2 solution or a 4 solution puzzle, but when these numbers get really big, who cares...

Ruud.

soduko · Posted: Mon Nov 07, 2005 10:37 pm Post subject:

I would like that it reports.
all possible solutions superinposed in one grid.

I do not think imake my self clear
Embarassed

better give an example
I would like the output to be something like:

Ruud · Site Admin

Bob Hanson · Posted: Mon Nov 07, 2005 11:26 pm Post subject:

OK, in that case, just go to Sudoku Assistant, and when it gets stuck, click on "Table". It will give you that picture. Clues will be in red.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

Lummox JR · Posted: Tue Nov 08, 2005 5:03 am Post subject:

I don't think there's much need to report the full number of solutions unless that's in demand by someone. Just run the sucker through dancing links and have it bail out at solution #2. After all, 2 solutions or 1900, you're still dealing with an invalid sudoku.

soduko · Posted: Tue Nov 08, 2005 10:00 am Post subject:

Bob Hanson · Posted: Tue Nov 08, 2005 10:03 pm Post subject:

oh, I see. OK. Nevermind!
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr