How to show a sodoku solution is unique_问答_开发者

Given a unsolved sodoku, how can one show that it has a unique sol开发者_开发百科ution?

Try to find two solutions.

The simplest algorithm is a brute force recursive algorithm with backtracking. Once you have found the first solution, backtrack and look for a second. This is slow but (unlike algorithms that rely on logic alone) it is guaranteed to be able to find all the solutions eventually. Therefore if this algorithm terminates having found only one solution then that solution must be unique.

This will work for easy problems but could take hours or days for harder problems. There are many optimizations you can use if you need more speed.

A simple optimization is to keep track of a candidate list for each square. At each step find the square with the fewest candidates. If there is only one candidate, choose that number, update the grid and the candidates for the other squares, then continue. If there are ever zero candidates you know that a guess you made previously was wrong so you should backtrack.

More advanced optimizations involve looking for patterns which allow you to deduce numbers without making guesses. Here are some examples:

Techniques For Solving Sudoku
- Single Position
- Single Candidate
- Candidate Lines
- etc...

There are certain configurations that will ultimately result in a non-unique solution, such as:

* *  *  | * * * | * * *
* *  *  | * * * | * * *
* 12 12 | * * * | * * *
--------+-------+------
* *  *  | * * * | * * *
* *  *  | * * * | * * *
* 12 12 | * * * | * * *
--------+-------+------
* *  *  | * * * | * * *
* *  *  | * * * | * * *
* *  *  | * * * | * * *

where the *s can be any number, and 12 are the sole possibilities in those cells. In this case, there is definitely going to be at least two possible solutions:

* * * | * * * | * * *    * * * | * * * | * * *
* * * | * * * | * * *    * * * | * * * | * * *
* 1 2 | * * * | * * *    * 2 1 | * * * | * * *
------+-------+------    ------+-------+------
* * * | * * * | * * *    * * * | * * * | * * *
* * * | * * * | * * *    * * * | * * * | * * *
* 2 1 | * * * | * * *    * 1 2 | * * * | * * *
------+-------+------    ------+-------+------
* * * | * * * | * * *    * * * | * * * | * * *
* * * | * * * | * * *    * * * | * * * | * * *
* * * | * * * | * * *    * * * | * * * | * * *

without calculating the rest of the board, you can determine that this Sudoku's solution is not unique. However, even if it is possible in certain cases to prove that a puzzle's solution is not unique; the only way to prove that a puzzle's solution is unique is to use brute force to calculate that the set of possible solutions contain only 1 solution.

There are some shortcuts than pure brute force, however you need to take extra care when writing a hybrid solver. Most Sudoku solving techniques allows you to find multiple solutions if they exist but some advanced Sudoku solving techniques rely on the fact that proper Sudoku has unique solution, and may cause you to not be able to find the second solution.

Soduko is a CSP to 81 variables, one for each box. Using variable names from A1 to A9 for the top row (left to right), to I1-I9 for the bottom line. The blank boxes have the domain {1,2,3,4,5,6,7,8,9} and that they have already filled a domain consisting of a single value. There are also 27 different constraints "all different", one for each row, column and box 9 boxes.

You can use the AC-3 algorithm for simple patterns or PC-2 for the more difficult ones, but this has more computational cost.

In my opinion the only way is to solve it. If you will be able to solve it (without guessing - only with 100% 'moves') then it means that it has exactly one solution. If you won't be able to solve it, then the only way I see is to use bruteforce algorithm and check how many actual solutions you will be able to find.

As mentioned above one may use a brute force recursive algorithm with backtracking. I would like to suggest just by applying two times the algorithm once upward; meaning the candidate values increase incrementally while searching, and then employing the algorithm downward, meaning the candidate values are examined in a descending order from maximum possible number to 1, then at least two solutions can be detected. If the results from ascending and descending approaches remain the same, then one can say that the puzzle has a unique solution.

Using backtracking technique to exhaust all possible solutions. If you get a solution. Solution counter +1. If counter increase more than 1, you can declare this puzzle have more than 1 solution and exit the program. Otherwise, you have to wait until it finish. If counter = 1, you confirm it has one solution. If counter = 0, there is no solution.