Uniqueness test: A new twist

Lummox JR · Posted: Fri Sep 23, 2005 1:39 am Post subject: Uniqueness test: A new twist

I posted today about how I implemented the uniqueness test in my solver. It's a great little test, but the cool thing is I just discovered a puzzle that brings up a new way of using it.

For those who haven't seen it before, basically it operates on the assumption that the puzzle you're solving is a valid one with a unique solution. It requires you to have two cells with the same 2 candidates (no others) which are aligned in the same column or row, and share a box. You need two other cells to form a rectangle, one of which has only those same 2 candidates, and another which has those 2 candidates plus at least one more.

Lummox JR · Posted: Fri Sep 23, 2005 3:17 am Post subject:

Doh. Once again I've discovered this is not a new discovery. If I'd read the very end of the original thread fully, I'd've seen that this variation was already known.

Well, at least I can update my solver for it.

Lummox JR · Posted: Sat Sep 24, 2005 10:17 pm Post subject:

I believe I actually have, now, discovered something new to the uniqueness test. There is yet another flavor involving subsets of values. Consider this portion of a puzzle, from the lower left corner:

Moschopulus · Posted: Sun Sep 25, 2005 12:34 pm Post subject:

If you use this uniqueness trick in your solver, then your solver doesn't prove that a puzzle has a unique solution. (At least any time it uses this fact to solve.)

Some people don't use the fact that a puzzle has a unique solution to solve it, because when you find a solution you haven't proved that its the only solution. If you solve by purely "logical" deduction techniques then you can not only deduce the solution, you've also proved that its the only solution.

It's a matter of personal taste. But there is a logical distinction between the conclusions. There was a thread on this somewhere......can't find it.
--------------------------

I also want to mention positions like
a..b.....
.........
.........
b..a.....
.........etc
in a completed grid. Any set of cells in a completed grid is called an "unavoidable set" if the digits in those cells can be permuted so that you still end up with a valid completed grid. Since a and b can be interchanged in this example, this is an unavoidable set with 4 cells.
The name comes from the fact that if you were setting a puzzle from this grid, you have to use a clue from any unavoidable set if you want a unique solution, so they are unavoidable.

This trick using the unique solution would work for any unavoidable set. Here is another unavoidable set:
1.2......
.........
.........
21.......
.........
.........
.21......
.........
.........
so you can never have 6 cells in that arrangement with the same 2 candidates for each cell.

Lummox JR · Posted: Sun Sep 25, 2005 8:39 pm Post subject:

Ruud · Site Admin

I find these unavoidable sets very interesting. They might be the key to finding a 16 clue puzzle. I've been thinking about modifying the DLX routine to add a "no unavoidable sets allowed" constraint, and see whether it can then produce a 16.

About Moschopulus' argument: You're right that it does not PROVE that there is only one solution, but when the premisis is that there IS only one solution, this technique is as valid as any other.

Moschopulus · Posted: Mon Sep 26, 2005 9:17 am Post subject: Re: Unavoidable Sets

Ruud · Site Admin

Here's another interesting twist:

When you generate a puzzle using a solver that incorporates uniqueness tests, will it always generate a valid puzzle?

There's a chicken & egg thing to it, I guess.

I like to see your thoughts on this.

Lummox JR · Posted: Sat Oct 01, 2005 4:25 am Post subject:

You would never want to use a human-style solver to generate a puzzle. For that you'd definitely want a backtracking algorithm such as dancing links. The point to including human techniques is merely to assess difficulty, and if creating a full-featured program, to provide hints.

Ruud · Site Admin

I see no reason why not to use a human-type solver to generate a puzzle. Seems to work fine for me. When you enable-disable the techniques in the solver according to the difficulty settings, it can very quickly generate a valid puzzle with the desired difficulty level.

However, that was not my question.

In the meantime, I found out that this uniqueness test must be handled with care. When enabled in the solver, it can indeed generate puzzles which, validated without the uniqueness test, have multiple solutions. So now I disable uniqueness tests when generating puzzles.

Also, when loading (or manually entering) puzzles, the uniqueness test must be delayed until all clues have been entered, otherwise it can jump to conclusions later contradicted by additional clues.

Of course, this can only occur when the program uses "on the fly" solving, and does not wait for a "go" signal from the user.

Lummox JR · Posted: Mon Oct 03, 2005 4:21 am Post subject:

Agent Allen · Posted: Wed Oct 05, 2005 10:08 pm Post subject: A wee bit confused

Ruud,

I think Lummox JR is right.
You setter works like a bit like mine but mind the pit-falls!!

1. If you use deductions that don't rely on uniqueness and the deduct the solution absolutely, then the solution found (if any) is unique.

2. If you use methods that rely on uniqueness and find a solution, it might not be the only one.

3. There may be methods that rely on uniqueness and fail to find any solution when there is in fact one or more than one.

I haven't looked but this is a possible consequence of a false premise.

4. If you employ trial and error, make sure you go back and look for more solutions on all the other "trials" before declaring uniqueness.
_________________
Agent A

Lummox JR · Posted: Thu Oct 06, 2005 12:06 am Post subject:

Trial and error can be used in a way that doesn't eliminate multiple solutions; in fact it's the only safe kind to use. There are only a few methods that work:

1) Placing a digit causes a contradiction. That placement must be false.
2) All digits that can go in a cell, or all placements for a digit within a house, show that a particular cell cannot have a particular value. That placement must be false.
3) All digits that can go in a cell, or all placements for a digit within a house, show that a particular cell must have a particular value. That placement must be true.

gaby · Posted: Sat Oct 15, 2005 10:55 pm Post subject:

I get the feeling that the Unqiueness test feels like a swordfish-style variant. In my mind there are two approaches usually used, looking for cells with two candidates in, or looking for rows/cols/blocks where a candidate appears twice. The various techniques then revolve around maniupulating sets of these.

The uniqueness test looks very much like Y-Wing, looking at a very small forcing chain, which results in the final 'corner' of the box having either the candidates removed (Y-wing) or being set to the value (Uniqueness).

Is the uniqueness test constrained to having two of each of the numbers in the same block? Can it not work across rows/cols alone? This is again starting to sound very much like a Y wing, but with more restrictive removal policy.

Does this algorithm sound reasonable:

1. Find a cell with two numbers in it.

2. Find a cell in the same (row/column) with at least the same two numbers in it, and optionally some more numbers.

3. Find a cell in the same (column/row) with at least the same two numbers in it, and optionally some more numbers.

4. Find a cell that intersects the two cells from steps 2 and 3, that contains at least the same two numbers in it, and optionally some more numbers.

5. Only continue if the cells appear in two different blocks only, with two cells in each block.

6. We now assume that cells 1 and 2 are in b1, and cells 3 and 4 are in b2. The arrangement can be different, but we'll assume that this is the case. There are four uniqueness tests avaialble to us:

6.1 Test 1, cells 1, 2, and 3 only have two numbers in, cell 4 has 1 extra number in. Cell 4 must be the extra number, so remove the two numbers from that cell.

6.2 Test 2, cells 1, 2, and 3 only have two numbers in, cell 4 has several extra numbers in. Cell 4 can only contain the extra numbers, so remove the two numbers from that cell, leaving the two extra numbers

6.3 Test 3, the cells in one block have only two numbers in, the cells in the other block both have one extra number. We can remove that extra number from all the other cells in that block. If they're in a row, then we can also remove from the other cells in that row, and likewise for a column.

6.4 Test 4, the cells in one block have only two numbers in, the cells in the other block both have N extra numbers, and they are the same N extra numbers. If we find N-1 other cells in the same block that only the extra numbers in them, then we can remove those extra numbers from all the other cells in that block.
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/

Lummox JR · Posted: Sun Oct 16, 2005 1:05 am Post subject: