New(?) Uniqueness Test

Asteron · Posted: Wed Jan 25, 2006 4:29 pm Post subject: New(?) Uniqueness Test

In my solver I came up with a uniqueness test that involves just running my deterministic backtracking solver twice.

Basically assume you have two versions of a backtracking solver with identical deterministic reduction logic and identical logic to pick a square to guess on which is left with multiple candidates. The high-guessing-solver (HGS) always guesses from the high candidate values down and the low-guessing-solver (LGS) guesses from the low values up. If the HGS and LGS come up with the same solution that solution is unique.

PROOF:
Let S be the set of all solutions to a sudoku and Q be the set of squares that have multiple values in S. The LGS and HGS both run until they guess on a square, call it t. If t is not in Q then by virtue of backtracking both the LGS and HGS will conclude/assume the same value for t and move on.

If Q is not empty than eventually (after deducing an identical set of squares not in Q) both the LGS and HGS must guess on a square q in Q (this is because no squares of Q can be fixed by any logic on squares not in Q).

Since q is in Q it has multiple possible values in S and so the LGS will find a solution (call it LS) in S with the least value of q and the HGS will find a solution (call it HS) with the largest value of q. Since LS and HS differ in q they are distinct solutions.

Thus if multiple solutions exist than the LGS and HGS will find different solutions. The converse (inverse?) then must be true. If the LGS and HGS find identical solutions, than that solution is unique.

Really understanding the proof is harder than the implementation. It is the same logic as a person who always bears right in a maze and a person who always bears left will find different exits if and only if multiple exits exist.

I don't know if this is obvious or not but is very easy to code assuming any general deterministic backtracking algorithm (I guess you also have to assume no memory of path).

-Ast

Ruud · Site Admin

Hi,

First, a little synchronization. A uniqueness test as known in the Sudoku community no longer refers to testing the uniqueness of the solution, but to a solving method that depends on the uniqueness of the solution. There are 4 different uniqueness tests involving a uniqueness rectangle (the 4 corner cells to be precise), and numerous tests based on the BUG pattern.
The principle of all uniqueness tests is the same. Any action that would cause the BUG or 'deadly pattern' to appear is considered invalid, and the opposite of that action is chosen.

And now, something completely different: "How to recognize a unique sudoku from quite a long distance away"

Any backtracking solver can be used to search for multiple solutions. When there are multiple solutions, it is likely that they will manifest with only partial backtracking required. The solver can stop when the second solution is found.

Your high and low solvers have to move through all failed paths below and above the unique solution to find it. The path that leads to the unique solution itself must be traversed twice. This is slower than searching only once.

When multiple solutions are present, they are often found in an area where most of the placements are the same. There is no need to compare any digits, just a counter being incremented a second time and you're finished.

As a programming exercise, it can be interesting, but do not expect to gain performance with it.

Ruud.
_________________
Meet me at sudocue.net

md68 · Posted: Thu Jan 26, 2006 8:31 am Post subject:

I find this uniqueness thing very interesting because some puzzles wouldn't be solved without them.

Is this still considered human solving technique?

Ruud · Site Admin