The New Sudoku Players' Forum

[PaulIQ164]

You know, I don't understand this version of the Uniqueness test at all. Not one little bit.

[bennys]

r3c9 = 7 make r4c9,r5c9 and r6c9 locked on 169 and so r9c9 can't be 9

[bennys]

Code: Select all

It looks to me that many of the different rules can be seen in the following way
(lets look at the column but we can look at the box the same way)
Lets add dummy cell to the column and give it as candidates all the candidates other the uniqueness numbers in the uniqueness cells.
This will influence only the cells that are not in the  uniqueness cells and see what are the conclusion's.

for example

+----------------+----------------+----------------+
|                |                |                |
|                |                |                |
|                |                |                |
+----------------+----------------+----------------+
|                |                |                |
|                |                |                |
|                |                |                |
+----------------+----------------+----------------+
|                |     *25        |          *25   |
|                |                |                |
|                |     *25        |          *259  |
+----------------+----------------+----------+-----+
|                                            |  9  |
+--------------------------------------------+-----+ 
Here the only candidate for the dummy cell is 9 and we can eliminate 9 from all cells in the column
(which make R9C9 = 9)



+----------------+----------------+----------------+
|                |                |                |
|                |                |                |
|                |                |                |
+----------------+----------------+----------------+
|                |                |                |
|                |                |                |
|                |                |                |
+----------------+----------------+----------------+
|                |     *25        |          *259  |
|                |                |                |
|                |     *25        |          *259  |
+----------------+----------------+----------+-----+
|                                            |  9  |
+--------------------------------------------+-----+
Same thing


+----------------+----------------+----------------+
|                |                |                |
|                |                |                |
|                |                |                |
+----------------+----------------+----------------+
|                |                |                |
|                |                |                |
|                |                |            39  |
+----------------+----------------+----------------+
|                |     *25        |          *253  |
|                |                |                |
|                |     *25        |          *259  |
+----------------+----------------+----------+-----+
|                                            | 39  |
+--------------------------------------------+-----+
Can eliminate 39 from the rest of the cells

The example from the last post
+----------------+----------------+----------------+
| 457  39   39   | 57   2    1    | 6    457  8    |
| 157  8    2    | 57   4    6    | 1579 579  3    |
| 1457 467  16   | 9    3    8    | 1457 2457-257  |
+----------------+----------------+----------------+
| 2    346  136  | 8    9    7    | 45   45   16   |
| 478  4679 69   | 1    5    2    | 789  3    679  |
| 178  79   5    | 4    6    3    | 2    789  179  |
+----------------+----------------+----------------+
| 3   *25   4    | 6    8    9    | 57   1   *257  |
| 9    1    8    | 2    7    5    | 3    6    4    |
| 6   *25   7    | 3    1    4    | 589  2589*259  |
+----------------+----------------+----------+-----+
|                                            | 79  |
+--------------------------------------------+-----+
                   
 Here the Dummy and R4C9,R5C9,R6C9 are locked on 1679 and we can eliminate them from the other cells








                                             
                   


[MCC]

...Here the Dummy and R4C9,R5C9,R6C9 are locked on 1679 and we can eliminate them from the other cells

bennys, can you explain the above?

What are you removing? And from which cells are you removing them from?

[bennys]

Its 7 from R3C9

[gaby]

Whilst trying to find puzzles that let me test uniqueness, I found this example:

Code: Select all

. . .|. . 1|. . 8
. 8 2|. . .|. . .
. . .|9 3 .|. . .
-----------------
. . .|8 9 7|. . .
. . .|1 . .|. 3 .
. . 5|. . .|2 . .
-----------------
3 . .|6 . .|. 1 .
9 . .|2 . .|. . 4
6 . 7|3 . .|. . .

+----------------+----------------+----------------+
| 457  39   39   | 57   2    1    | 6    457  8    |
| 157  8    2    | 57   4    6    | 1579 579  3    |
| 1457 467  16   | 9    3    8    | 1457 2457 257  |
+----------------+----------------+----------------+
| 2    346  136  | 8    9    7    | 45   45   16   |
| 478  4679 69   | 1    5    2    | 789  3    679  |
| 178  79   5    | 4    6    3    | 2    789  179  |
+----------------+----------------+----------------+
| 3    25   4    | 6    8    9    | 57   1    257  |
| 9    1    8    | 2    7    5    | 3    6    4    |
| 6    25   7    | 3    1    4    | 589  2589 259  |
+----------------+----------------+----------------+

My solver, starting from the puzzle above, can ALMOST get to that point, I just can't get rid of the candidate 1 in [r4,c7], or the 5 in [r4,c9]. Can you post the backtrace of how your solver made it to that point? I get thus far:

Code: Select all

4 -> [r6,c4] One number possible in cell
6 -> [r6,c5] One number possible in cell
3 -> [r6,c6] One number possible in cell
3 -> [r2,c9] Candidate appears once in c9
3 -> [r8,c7] Candidate appears once in c7
6 -> [r2,c6] Candidate appears once in r2
8 -> [r3,c6] Candidate appears once in r3
5 -> [r8,c6] One number possible in cell
2 -> [r5,c6] One number possible in cell
1 -> [r8,c2] One number possible in cell
8 -> [r8,c3] One number possible in cell
7 -> [r8,c5] One number possible in cell
6 -> [r8,c8] One number possible in cell
5 -> [r5,c5] One number possible in cell
4 -> [r7,c3] One number possible in cell
8 -> [r7,c5] One number possible in cell
9 -> [r7,c6] One number possible in cell
4 -> [r9,c6] One number possible in cell
4 -> [r2,c5] One number possible in cell
1 -> [r9,c5] One number possible in cell
2 -> [r1,c5] One number possible in cell
2 -> [r4,c1] Candidate appears once in c1
9 <- [r1,c8] b1 only has 9 in r1
5 <- [r1,c2] b7 only has 5 in c2
5 <- [r3,c2] b7 only has 5 in c2
4 <- [r1,c2] Hidden Pair in r1 {3,9}, in {[r1,c2],[r1,c3]}
7 <- [r1,c2] Hidden Pair in r1 {3,9}, in {[r1,c2],[r1,c3]}

[Sue De Coq]

The candidates grid is shown after 23 moves. To remove the candidates you request:

Code: Select all

24. Consider the chain r2c7-1-r2c1~1~r6c1-1-r4c3~1~r4c7.
When the cell r4c7 contains the value 1, so does the cell r2c7 - a contradiction.
Therefore, the cell r4c7 cannot contain the value 1.
- The move r4c7:=1 has been eliminated.
The value 1 in Box 3 must lie in Column 7.
- The move r3c9:=1 has been eliminated.
The values 1, 3 and 6 occupy the cells r4c2, r4c3 and r4c9 in some order.
- The moves r4c2:=4 and r4c9:=5 have been eliminated.

To advance the puzzle from there to the point where it becomes straightforward requires the following logic:

Code: Select all

The value 4 in Box 6 must lie in Row 4.
- The move r5c7:=4 has been eliminated.
Consider the chain r3c2-6-r3c3-1-r4c3-1-r4c9-6-r5c9-6-r4c9-1-r4c3-3-r1c3-3-r4c3-3-r4c2.
When the cell r4c2 contains the value 6, some other value must occupy the cell r3c2, which means that the value 3 must occupy the cell r4c2 - a contradiction.
Therefore, the cell r4c2 cannot contain the value 6.
- The move r4c2:=6 has been eliminated.
The value 3 is the only candidate for the cell r4c2.


[Lummox JR]

But this leads to an invalid puzzle! After some thought, I added in the restriction that the hidden set cannot contain any of the other possibilities in the floor squares (ie: in the above example, <127> are excluded, which eliminates both candidate hidden sets)

Indeed, I discovered this early on but did not include it in my description of the technique because it actually works out on its own. If you're looking for naked sets of the extras, or hidden sets of the originals, you actually won't be able to find one that includes the others if you set the "quantum values" of the two cells to extras and original+extras. In the example with the 45's, you get 127 and 12457. If a naked/hidden set exists which includes a cross-sample of the two candidate groups, it will have existed under ordinary subset rules without using the uniqueness test. This is borne out by the fact that my solver, which doesn't do any additional checking for a mix of the candidates, never finds false eliminations.

The reason Susser hit a snag is this:

(R3C7|R3C8)<45>

But you left out the other candidates, which are still possibilities, so <12457> was actually correct. And one of those cells must still be a naked choice (R3C7|R3C8)<127>, which is a direct consequence of the uniqueness rule.

The full analysis is: (R3C7<127>,R3C8<12457> or R3C7<12457>,R3C8<127>)

A nice way of putting it might be:

Q = R3C7 and R3C8 in some order
Q1<127>,Q2<12457>

But with this restriction, whenever there is a hidden set, there is a naked set that permits the same reduction. Are there ever any hidden set reductions that do not have a complementary naked set reduction? Or am I still missing something?

Just as with regular subset rules, where a naked subset exists, so does a hidden subset. My solver just goes with whichever's smaller.

As you noticed, the hidden pair in the puzzle you were using, with roof 25 in column 2 and the floor in column 9, also has a complementary naked quad. The hidden pair of course is 25, because 25 can occur in only 3 cells in that column, and two of them are part of a unique rectangle, meaning 25 can only occur in two cells in column 9 after all. Since either R7C9=7 or R9C9=9 (ugh), you also get the naked quad <79>,<179>,<679>,<16>.

[MadOverlord]

Just as with regular subset rules, where a naked subset exists, so does a hidden subset. My solver just goes with whichever's smaller.

Okay, to make it absolutely clear, since for any naked subset, there is a complimentary hidden subset that permits the same eliminations, you can look for either (and as you say, simply report whichever one is smaller). Furthermore, the hidden subset will not contain any members of the naked subset, so my method of finding them is fine (actually a bit more efficient since many possible hidden subsets can immediately be excluded).

Assuming that is settled, then there is one more possible reduction I'd like to discuss, as follows:

As we know, the core of the unique rectangle reduction is the knowledge that in

12|12a (a = 0-n digits)
12|12b (b = 1-n digits)

we cannot reduce to

12|12
12|12

My question then becomes, in the particular case of

12|12a (a = 1-n digits)
12|12b (b = 1-n digits)

ie:

12|1234
12|1256

is it possible to sometimes prove whether or not the configuration reduces to:

12|a
12|b

ie:

12|34
12|56

As a potential method of finding it, how about this:

Take the extra squares (3456) in this case. Find a completely reduced locked set (ie: one that permits no further reductions - it may require that no other squares in the group can contain the values in the set) that contains at least 2 of the values (may need to be all of them) and n-2 other squares, where n = number of items in the locked set. Then remove all possibilities not in the locked set from both squares.

examples: we find 2 other squares 345 and 456, forming a locked set 3456, and remove the 12's; we find 1 other square 456, and can eliminate 123.

I've got a hunch there is a reduction in here, but is it useful?

Also, if there is, then there might be a way to assemble n-2 locked sets and perform other reductions with them.

Comments, oh mighty lummox, master of logic?

[Lummox JR]

Heh.

Unfortunately the uniqueness test doesn't tell us whether 12 will appear in neither of the floor cells, which is a possibility. It only tells us that it cannot appear in both. The analysis from uniqueness 3 allows us to play around a bit by eliminating 12 from one cell only, and filling it with the leftover "garbage" from both cells.

One way to understand all uniqueness tests is to consider the rule which unifies them all: The roof candidates ultimately can be eliminated from at least one of the floor cells. Consider, then, all the tests in light of that rule:

Uniqueness 1: One of the floor cells has only the roof candidates. If you eliminated the roof candidates from it, it would have none at all. Therefore you can eliminate them from the other floor cell.

Uniqueness 2: Both floor cells have the same extra candidate. Whichever cell you eliminate the roof candidates from, you'll leave behind a naked single. That single digit can be eliminated from the intersection of the floor cells.

Uniqueness 3: Eliminating the roof candidates from either floor cell will result in a naked subset of some size. Both naked subsets are part of a potentially larger subset. Eliminations may be done elsewhere in the house, except in the floor cells.

Uniqueness 4: Candidate A can only go in the floor cells within their common house. Eliminating the roof candidates from either floor cell forces candidate A to be a hidden single in the other floor cell, so candidate B cannot also go there. In both scenarios, candidate B cannot be placed anywhere in the floor cells, so it can be eliminated from both.

Sadly the logic which tells us the roof candidates can be eliminated from one floor cell (even though we don't know yet which cell) does not tell us if they can be eliminated from both. In fact you'll note that all of the above scenarios end up leaving at least one of the roof candidates in at least one of the floor cells, and that makes sense because it always forces us to conclude something about the other cell; it's that squeeze between possibilities that makes our deductions possible. It suggests that uniqueness tests may only work in those cases.

[MadOverlord]

Sadly the logic which tells us the roof candidates can be eliminated from one floor cell (even though we don't know yet which cell) does not tell us if they can be eliminated from both.

Exactly. I am wondering if there is some extra thing we can do that will enable us to make that deduction. Just as we need to find a conjugate pair in order to execute a Type-4 reduction, I am wondering if there is a way to leverage our information one step further.

For example, if we have

12|123
12|124

and the only other square in one of the floor pair's groups that contains (say) 345 is a 345, then that forms a hidden set on 345 -- but, of course, we'd have found that hidden set normally.

I am wondering if there is some way to leverage our knowledge about 12 through some logical loop that permits us to eliminate the 12 completely. It would have to be some interaction with the 12 possibilities in the other squares in a floor group and the non-12 possibilities in that same group that feeds back.

Or, going the other way, I checked a bunch of unique rectangle puzzles and have not been able to find an example where one of the floor squares wasn't one of the roof possibilities. Does anyone have such a puzzle?

If such a puzzle does exist, then we may be able to look at it and draw some inferences. If such a puzzle cannot exist, then we may be able to draw different inferences.

For example, if it can be proved that we never have a case where

12|1234
12|1234

reduces to

12|34
12|34

(in other words, one of the roof squares must always have one of the floor square possibilities)

then we might be able to look for locked sets on the floor possibilities (at least, under certain circumstances)

[DanO]

Menneske.no Super Hard #5218332

Code: Select all

+-------+-------+-------+
| 1 . . | . . 4 | 9 . . |
| . . . | . . . | . 6 5 |
| 2 3 . | . . . | . 7 . |
+-------+-------+-------+
| 4 . . | . . 7 | . . 9 |
| . 2 3 | . . . | 6 5 8 |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . 2 6 | 4 . . |
| . . . | . . 3 | . . . |
| . . 6 | 9 7 . | . . 3 |
+-------+-------+-------+


This pattern emerges which allows the 1's in R2C6 and R3C6 to be removed

Code: Select all

+ - - - - - - - +
|   .   .   .   |   
|   .   .  1x   |   
|   .   .  1y   |   
+ - - - - - - - +
|   .   .   .   |   
|  14  149 19   |   
|   .   .   .   |   
+ - - - - - - - +
|   .   .   .   |   
|  148 148  .   |   
|   .   .  18   |   
+ - - - - - - - +


[Lummox JR]

This pattern emerges which allows the 1's in R2C6 and R3C6 to be removed

Code: Select all

+ - - - - - - - +
|   .   .   .   |   
|   .   .  1x   |   
|   .   .  1y   |   
+ - - - - - - - +
|   .   .   .   |   
|  14  149 19   |   
|   .   .   .   |   
+ - - - - - - - +
|   .   .   .   |   
|  148 148  .   |   
|   .   .  18   |   
+ - - - - - - - +


I'm not sure I follow. How does this fit among the uniqueness tests? There's no naked pair to work with. Unless this is another form of unavoidable set, it's unrelated to uniqueness at all. But I also don't see how you can make that deduction, because this is a perfectly valid possibility:

Code: Select all

+ - - - - - - - +
|   .   .   .   |   
|   .   .  1x   |   
|   .   .  1y   |   
+ - - - - - - - +
|   .   .   .   |   
|   4   1   9   |   
|   .   .   .   |   
+ - - - - - - - +
|   .   .   .   |   
|   1   4   .   |   
|   .   .   8   |   
+ - - - - - - - +

[edit]
Gads, I can't believe I missed this one--on this thread in particular. That's the deadly pattern there. It only shows up if you think of the problem in terms of forcing chains, though, or perhaps by applying a form of bifurcating chains logic. DanO's right, although an explanation as to why would've saved me some grief.

[Lummox JR]

Sadly the logic which tells us the roof candidates can be eliminated from one floor cell (even though we don't know yet which cell) does not tell us if they can be eliminated from both.

Exactly. I am wondering if there is some extra thing we can do that will enable us to make that deduction. Just as we need to find a conjugate pair in order to execute a Type-4 reduction, I am wondering if there is a way to leverage our information one step further.

For example, if we have

12|123
12|124

and the only other square in one of the floor pair's groups that contains (say) 345 is a 345, then that forms a hidden set on 345 -- but, of course, we'd have found that hidden set normally.

Exactly what I mean. If it's possible to eliminate both roof candidates from the floor cells, it's by a different test. The uniqueness logic tells us we can eliminate from only one of those cells, but doesn't necessarily tell us which one.

I am wondering if there is some way to leverage our knowledge about 12 through some logical loop that permits us to eliminate the 12 completely. It would have to be some interaction with the 12 possibilities in the other squares in a floor group and the non-12 possibilities in that same group that feeds back.

I don't think there is. The existing uniqueness tests all operate by using the elimination of 12 in one unknown cell to find eliminations for either 2 total candidates within the floor cells, or any number of candidates within other cells touching both floors. Where elimination happens inside the floor cells, it either takes two candidates from one cell or one from both. In all known uniqueness tests, an elimination can only be found if and only if one of the floor cells must contain one of the roof candidates (see my analysis above).

Or, going the other way, I checked a bunch of unique rectangle puzzles and have not been able to find an example where one of the floor squares wasn't one of the roof possibilities. Does anyone have such a puzzle?

You won't find one by the four known tests. All of them rely on one of those roof candidates being present in one of the floor cells in the solution. Uniqueness 1 guarantees it because one of the floor cells has only the roof candidates. Uniqueness 2 guarantees it because the extra candidate can only appear in one of the floor cells. Uniqueness 3 guarantees it because a partial subset can only be found in situations where one of the cells has the roof candidates, making it part of the full hidden set which complements the full naked set. Uniqueness 4 guarantees it because one of the roof candidates is already known to occur only within the two floor cells.

Note that in each case, there is some logic which says the roof possibilities must be somewhere in the floor, and it's the uniqueness logic which eliminates them from one floor cell that allows us to find any eliminations. Our choices are squeezed between "one of those must go there" and "they can't go in both". The fact that this is a common facet of all four known uniqueness tests suggests that any other potential uniqueness tests also rely on that same "squeeze" logic.

If such a puzzle does exist, then we may be able to look at it and draw some inferences. If such a puzzle cannot exist, then we may be able to draw different inferences.

For example, if it can be proved that we never have a case where

12|1234
12|1234

reduces to

12|34
12|34

(in other words, one of the roof squares must always have one of the floor square possibilities)

then we might be able to look for locked sets on the floor possibilities (at least, under certain circumstances)

We can't prove that we never have such a case. (Pop a naked 12 into two other positions in that column, and there you go.) Rather, the uniqueness logic cannot prove such to be the case when using the 12's as the roof cells.

It strikes me that you'd be looking for situations that almost qualify for uniqueness 3 but don't quite because they're missing one more cell in the naked set. Unfortunately uniqueness doesn't provide us enough information to expose more than one of the floor cells as naked, and standard subsets will also fall short in that situation.

[bennys]

To me it looks prefecly good argument.
The last code in Lummox answer is not perfectly valid possibility.