Standardizing the Uniqueness descriptions...

Advanced methods and approaches for solving Sudoku puzzles

Standardizing the Uniqueness descriptions...

Postby MadOverlord » Fri Oct 21, 2005 11:20 pm

The new uniqueness patterns are pretty impressive, and I've been working to add them to the Sudoku Susser. Along the way, I've been a little bit confused about nomenclature, and I'd like to get that cleared up so I can use standard nomenclature in the app's descriptions.

Here's what I've come up with; corrections and expansions are much appreciated. I'll only go into the patterns that I've implemented in my current version of the Susser.

First of all, I've taken to calling these patterns Unique Rectangles, which I think is more descriptive, easier to write declaritively (ie: "A,B,C, and D form a unique rectangle on <12>"), and gives room for when similar patterns are found ("unique this, unique that, unique the-other")

So the Type-1 Unique Rectangle is:

Code: Select all
12|12A..
12|12

ie:
12|123
12|12


and permits the 12A... to be reduced to A... (A... stands for 1-n other possibilities)

The Type-2 Unique Rectangle is:

Code: Select all
12|123
12|123


and permits 3 to be removed from the common groups (houses) of the 123 squares. If I'm not mistaken, this variant:

Code: Select all
12 |12
123|123


is the Type-2B form (I haven't implemented it yet) and permits removal of 3 from the common group of the 123 squares (in this case, a row)

The Type-3 Unique Rectangle is:

Code: Select all
12|12AB...
12|12AB...

ie:
12|1234 (look for locked/hidden sets containing 34, such as 34, 346, etc.)
12|1234

12|12345 (look for locked/hidden sets containing 345)
12|12345


and permits you to consider the two 12AB... squares to be a single square of AB... (2 or more possibilities) for the purposes of finding locked and hidden sets in the common groups. I kind of think of these as "quantum" squares because they're kind of fuzzy, like quantum physics.

It has a Type-3B form as follows:

Code: Select all
12     |12
12AB...|12AB...

ie:

12  |12
1234|1234


As a side note, it occurred to me that possibly this pattern might also by a Type-3:

Code: Select all
12|12A...
12|12B...

ie:
12|123 (look for locked/hidden sets containing 34)
12|124


since in order to prevent the deadly pattern, at least one of A...B... (in the example, 3 or 4) has to be in those two squares. But the problem is, 2 of them could be in there... So I'm not sure.

One of the nice traditions in another hobby I'm into, Robotic Combat, is "Ultimate Guides", ie: "The Ultimate Guide to Pneumatics". It seems to me that we could all benefit from a series of these guides for each of the major solving techniques.

If you guys post corrections, expansions (forms I've missed, like the Type-4's that I don't quite suss yet), and most important, sample puzzles, I'll try and pull it all together into an Ultimate Guide to Unique Rectangles.
MadOverlord
 
Posts: 81
Joined: 10 June 2005

Postby PaulIQ164 » Fri Oct 21, 2005 11:45 pm

I can't think of any other versions you've missed. The problem is, of course, when you're actually solving puzzles, you don't think so precisely as you have to when programming a computer. But I reckon that's a pretty comprehensive guide.

Edit: I did find another thing I did with this technique a while ago:

12¦12ABC...
12¦12ABC...

If those 1s in the 12ABC... are the only possible 1s in the column, then you can eliminate the 2s. Might not let you place the cells, but it's a couple less possibilities at least.
PaulIQ164
 
Posts: 533
Joined: 16 July 2005

Re: Standardizing the Uniqueness descriptions...

Postby Lummox JR » Sat Oct 22, 2005 5:27 pm

MadOverlord wrote:First of all, I've taken to calling these patterns Unique Rectangles, which I think is more descriptive, easier to write declaritively (ie: "A,B,C, and D form a unique rectangle on <12>"), and gives room for when similar patterns are found ("unique this, unique that, unique the-other")

This is certainly an apt description for the 2x2 uniqueness tests. Technically you could extend the 4 tests all the way to 3x3, 4x4, and 6x6 forms by tweaking the logic, but nobody looks for those because to my knowledge no one has ever even encountered one.
So the Type-1 Unique Rectangle is:

Code: Select all
12|12A..
12|12

ie:
12|123
12|12


and permits the 12A... to be reduced to A... (A... stands for 1-n other possibilities)

Yep, that works.
The Type-2 Unique Rectangle is:

Code: Select all
12|123
12|123


and permits 3 to be removed from the common groups (houses) of the 123 squares. If I'm not mistaken, this variant:

Code: Select all
12 |12
123|123


is the Type-2B form (I haven't implemented it yet) and permits removal of 3 from the common group of the 123 squares (in this case, a row)

Yep, right on that again.
The Type-3 Unique Rectangle is:

Code: Select all
12|12AB...
12|12AB...

ie:
12|1234 (look for locked/hidden sets containing 34, such as 34, 346, etc.)
12|1234

12|12345 (look for locked/hidden sets containing 345)
12|12345


and permits you to consider the two 12AB... squares to be a single square of AB... (2 or more possibilities) for the purposes of finding locked and hidden sets in the common groups. I kind of think of these as "quantum" squares because they're kind of fuzzy, like quantum physics.

You can't look for hidden sets containing the 34, etc., only the naked (locked) ones. You can however look for hidden sets containing the 12. You'll find one or the other, since they're complementary. As I mentioned in a correction to my previous posts on the other thread, pretend c=34 and d=1234 and run them through a subset solver, but do no eliminations on d.
It has a Type-3B form as follows:

Code: Select all
12     |12
12AB...|12AB...

ie:

12  |12
1234|1234

Yep.
As a side note, it occurred to me that possibly this pattern might also by a Type-3:

Code: Select all
12|12A...
12|12B...

ie:
12|123 (look for locked/hidden sets containing 34)
12|124


since in order to prevent the deadly pattern, at least one of A...B... (in the example, 3 or 4) has to be in those two squares. But the problem is, 2 of them could be in there... So I'm not sure.

You were quite correct that this raises new possibilities. You'd still look for naked subsets with 34 the same way, though; pretend c=34 and d=1234. If you find another cell where only 34 exists, or two with 35 and 45, etc., etc., you'll know that only one of the c or d cells has 34 and the other must have 12. Likewise you may also discover a hidden subset with the 12's still.
If you guys post corrections, expansions (forms I've missed, like the Type-4's that I don't quite suss yet), and most important, sample puzzles, I'll try and pull it all together into an Ultimate Guide to Unique Rectangles.

Type 4 is the only one I know of that you're missing. I find this one quite valuable. It's more common than 3, and often 3 only appears as a special case of 4. If you're still trying to grok the logic of it, I've posted a more thorough explanation here for the benefit of noeldillabough who is also implementing uniqueness.

As I mentioned this can be expanded to higher-order tests that nobody bothers with. The logic would have to change slightly for some tests but they all apply. In 3x3 type 3 for example you'd pretend one of the target cells was 45, and the other two 12345, and run through a subset solver. In 3x3 type 4, candidates A and B would both have to be constrained the same way, and you'd eliminate candidate C. If you're ever interested in finding higher-order NxN forms, they all require the use of exactly N columns, N rows, and N boxes, where N*(N-1) of the cells have the same N candidates, and the cells with extra candidates are all either in the same box (A form) and/or line (B form). If N>3 it is no longer possible for the target cells to share both a box and a line in form A.
Lummox JR
 
Posts: 125
Joined: 22 September 2005

Re: Standardizing the Uniqueness descriptions...

Postby MadOverlord » Sat Oct 22, 2005 10:04 pm

Lummox JR wrote:You can't look for hidden sets containing the 34, etc., only the naked (locked) ones. You can however look for hidden sets containing the 12. You'll find one or the other, since they're complementary.


This is confusing to me. I need a more specific example. Why can't you do hidden set elimination on the 34 (as long as 3 or 4 isn't eliminated, of course)?

As mentioned in the other thread, my philosophy is to treat the 1234 cells as a single "quantum" cell 34, and then find the locked sets using it and the other 7 squares of the group.

As I mentioned in a correction to my previous posts on the other thread, pretend c=34 and d=1234 and run them through a subset solver, but do no eliminations on d.


Do you mean when finding hidden sets on 12? Isn't that equivalent to a quantum cell of 12, with the restriction of not messing with the cells in the quantum cell?

So, if you find

12|1234 125
12|1234

you can eliminate the 5?

But by the same token, if you find

12|1234 345
12|1234

seems to me you can also eliminate the 5.

You were quite correct that this raises new possibilities. You'd still look for naked subsets with 34 the same way, though; pretend c=34 and d=1234.


Isn't it just easier to think of this as a quantum square whose values are the union of the extra values in the square, ie:

12|123
12|1234

the quantum square is 34

12|123
12|1245

the quantum square is 345?

Type 4 is the only one I know of that you're missing. I find this one quite valuable. It's more common than 3, and often 3 only appears as a special case of 4. If you're still trying to grok the logic of it, I've posted a more thorough explanation here for the benefit of noeldillabough who is also implementing uniqueness.


If I read that correctly, Type-4 is what paul posted earlier in this thread. ie:

12|12ABC...
12|12ABC...

where the 2 12ABC... squares are a conjugate pair in one of their groups on 1 (the only 2 places in the group where the 1 can go). Since one of those squares MUST be 1, the other cannot be 2 because that would create the deadly pattern. And so you can zap 2 from the 12ABC... squares. And note: you should not do this before doing all the other reductions because it will destroy the Unique Rectangle pattern.

I think I've got that -- but I'm not 100% sure. Once again, explicit explanations with examples are much easier to wrap our poor programmer's heads around. Best of all are sample puzzles, because they not only let us work through the logic, but let us test our solvers!
MadOverlord
 
Posts: 81
Joined: 10 June 2005

Re: Standardizing the Uniqueness descriptions...

Postby Lummox JR » Sun Oct 23, 2005 4:12 am

MadOverlord wrote:
Lummox JR wrote:You can't look for hidden sets containing the 34, etc., only the naked (locked) ones. You can however look for hidden sets containing the 12. You'll find one or the other, since they're complementary.

This is confusing to me. I need a more specific example. Why can't you do hidden set elimination on the 34 (as long as 3 or 4 isn't eliminated, of course)?

Because you can't rule out the possibility that neither c nor d is 12. The uniqueness tests only say that they can't both be 12. I know this isn't immediately clear, which is why I thought it would work at first too. But either a regular hidden subset will eliminate 12 from both cells, or you'll find that you have more cells than candidates. If for example you can limit 3458 to four cells including c and d, that's just a regular hidden subset. If you have five cells where those four values appear, you can't treat them as four because uniqueness does not prove 12 must appear in either c or d; it proves it must not appear in both.

For a naked subset the exact opposite situation applies. If you can find three cells besides c and d which have only 3458 (or some portion thereof) as candidates, then you can make the following deduction: If c and d both had 34, you would have 5 cells which can only hold 4 candidates. Therefore in this case only one of the c or d cells can have 34 as candidates, so this "quantum cell" completes the naked subset.

Bottom line: 5 cells that can hold only 4 values is a contradiction, which is why the quantum cell appears. 4 values that can only appear in 5 places is not a contradiction.

Because of the way naked and hidden sets are complementary, you can find a hidden set including 12 just as you can find a naked set including 34. Consider a hidden 126, where there are only two other cells where 126 can appear. If both c and d are 34 and neither is 12, then you have 3 values which must fit into 2 cells, which is a contradiction. Therefore in this case at least one of the c or d cells is 12, which makes cd a quantum cell.

And in the last case, 126 as a naked subset, you can prove nothing because you don't know if c and d contain 1 or 2 at all. If you have 16 and 26 in two extra cells, you only have two cells with three candidates, which is not a contradiction because those candidates may or may not appear elsewhere. You can't eliminate 1 and 2 from other cells because you can't
rule out that 12 may not appear at all in cd.
As I mentioned in a correction to my previous posts on the other thread, pretend c=34 and d=1234 and run them through a subset solver, but do no eliminations on d.

Do you mean when finding hidden sets on 12? Isn't that equivalent to a quantum cell of 12, with the restriction of not messing with the cells in the quantum cell?

I thought so at first, which is why I first said you could treat c as 34 and d as 12. However this just doesn't work; it'll try to find naked subsets including 12, which isn't legal.
So, if you find

12|1234 125
12|1234

you can eliminate the 5?

Yes, if and only if 1 and 2 may appear in no other cells in that box. Then you have a partial hidden pair with 12, which is legal by the test. You know the lack of any other place to put the second 12 forces you to put it in c or d, and you know that 12 can't be in both c and d because of the uniqueness rule. Instead of having 3 cells where you can place 12, you only have 2; you just don't know what one of them is.
But by the same token, if you find

12|1234 345
12|1234

seems to me you can also eliminate the 5.

If 345 only occur in those three cells, you have a regular hidden subset and instead you'd just eliminate 12 from c and d. So uniqueness really doesn't come into play there.

If 34 only occur in those three cells, it is still possible for both c and d to contain 34. Two values in three cells does not a hidden subset make. Concrete example to follow at the end of the post.
You were quite correct that this raises new possibilities. You'd still look for naked subsets with 34 the same way, though; pretend c=34 and d=1234.

Isn't it just easier to think of this as a quantum square whose values are the union of the extra values in the square, ie:

12|123
12|1234

the quantum square is 34

12|123
12|1245

the quantum square is 345?

My investigations show that it's just not possible to find naked subsets in 12 or hidden in 345. So instead of treating c and d as a single quantum cell, it makes more sense to treat them as a pair of cells with a shared quantum uncertainty. One and only one of these candidate sets is possible:
Code: Select all
12|3     OR  12|123
12|1245      12|45

Because of the way those possibilities work, you can treat them as a quantum set like this:
Code: Select all
12|345    OR  12|12345
12|12345      12|345

Looking at it like that, then, you can see more clearly why naked sets with 12 don't work: Neither possibility exposes a naked 12. Hidden sets with 345 are the complement of that. If you don't have enough information for a standard hidden set to cut down 345, you still don't have enough for a partial because uniqueness does not restrict 345 to only one cell.
Type 4 is the only one I know of that you're missing. I find this one quite valuable. It's more common than 3, and often 3 only appears as a special case of 4. If you're still trying to grok the logic of it, I've posted a more thorough explanation here for the benefit of noeldillabough who is also implementing uniqueness.

If I read that correctly, Type-4 is what paul posted earlier in this thread. ie:

12|12ABC...
12|12ABC...

where the 2 12ABC... squares are a conjugate pair in one of their groups on 1 (the only 2 places in the group where the 1 can go). Since one of those squares MUST be 1, the other cannot be 2 because that would create the deadly pattern. And so you can zap 2 from the 12ABC... squares. And note: you should not do this before doing all the other reductions because it will destroy the Unique Rectangle pattern.

Actually I don't think that last part matters, because if you do this elimination it will cause the other cases to degenerate into something simpler. If you have uniqueness 1 and 4 coexisting, and do 4 first, you'll end up with a naked single. If you have 2 and 4, you'll get a naked pair and the same eliminations from 2 will still be made. If 3 and 4, this should degenerate into a case that standard subsets can handle. (In fact, 4 is often seen as a special case of 3, so I recommend always testing 4 first. It's also much easier to spot, and as we've observed, to comprehend.)

Paul first propsed uniqueness form 4 in this thread.
I think I've got that -- but I'm not 100% sure. Once again, explicit explanations with examples are much easier to wrap our poor programmer's heads around. Best of all are sample puzzles, because they not only let us work through the logic, but let us test our solvers!

Sample puzzles for most uniqueness tests are easy to find, but 3 is actually fairly uncommon. I can however give you an example of why you can't test for hidden subsets in the 345 example you showed me. Just to flesh out your example, consider this:
Code: Select all
12 |1234 345  1258
12 |1234 1258 .
.  |.    .    158

You asked why, if 3 and 4 can only appear in cells c, d, and a third cell, you can't use a partial hidden pair to eliminate the 5 from 345. Here's why:
Code: Select all
12 |3    5    128
12 |4    128  .
.  |.    .    18

That's a perfectly valid permutation, because it doesn't violate the uniqueness rule by putting both 1 and 2 in the cd cells.
Lummox JR
 
Posts: 125
Joined: 22 September 2005

Postby MadOverlord » Sun Oct 23, 2005 9:00 am

I would greatly appreciate several actual examples of puzzles where the 12 hidden set reduction is possible. Same goes for the Type-4 "get rid of 2 because 1 is a conjugate" puzzles.

Explanations are useful, but actual puzzles let me test that my solver is performing properly.

I have now, btw, implemented Type-1, Type-2, Type-2B, Type-3 and Type-3B (locked sets only) Unique Rectangles in the Susser.

Bedtime now; will update the main posting tomorrow.
MadOverlord
 
Posts: 81
Joined: 10 June 2005

Postby MadOverlord » Sun Oct 23, 2005 4:50 pm

Here is my first draft of "The Ultimate Guide to Unique Rectangles" for your comments and suggestions. This is largely based on my documentation of the heuristic in the Sudoku Susser manual.

This version covers Type-1, -2, -2B, -3 and -3B (locked sets only). When I get sample puzzles for -3 (hidden set) and -4, I will add them. Also, please specifically comment upon sub-variants that I have missed (such as when one of the digits forms a conjugate pair)

As this document evolves, I will post complete new versions of it into this thread.

The Ultimate Guide to Unique Rectangles - version 0.1

The Unique Rectangles pattern was first noticed by ??? and subsequently expanded upon by contributions from ???,??? and ????.

Unique Rectangles take advantage of the fact that Sudoku can only have 1 solution in order to make useful inferences. For example, consider the following puzzle:
Code: Select all
+----------------+----------------+----------------+
| 25   8    24   | 45   6    3    | 9    7    1    | (note: the four squares
| 357  37   1    | 58   2    9    | 6    4    358  |  in the unique rectangle
| 6    39   349  | 458  7    1    | 238  28   2358 |  are marked with *'s)
+----------------+----------------+----------------+
| 4   *25  *2356 | 7    9    8    | 1    26   23   |
| 27   1    26   | 3    4    5    | 278  268  9    |
| 379  379  8    | 6    1    2    | 37   5    4    |
+----------------+----------------+----------------+
| 8   *25  *25   | 1    3    7    | 4    9    6    |
| 39   4    39   | 2    8    6    | 5    1    7    |
| 1    6    7    | 9    5    4    | 28   3    28   |
+----------------+----------------+----------------+
(Graphic representation)

Note the squares R4C2, R4C3, R6C2 and R6C3; they form a group of 4 squares that share exactly 2 blocks, 2 rows and 2 columns. The important insight here is that if they also only share 2 possibilities, then the puzzle has more than one solution!

If you think about it, it is obvious: if in the above puzzle, the four squares had possibilities <25>, then two diagonally-opposite squares must be <2>, and the other two must be <5>. No matter which way you arrange them, the 2 rows, columns and blocks would have one 2 and one 5, and you could exchanges the 2’s and 5’s and the puzzle would still be valid -- the puzzle would have more than one solution. This configuration of 4 squares with the same 2 possibilities in two rows, two columns and two blocks is called the “deadly pattern.” Find it, and you know you’ve gone wrong. But the knowledge that that particular pattern cannot appear lets you make progress:

Here’s how: If you can find a rectangle such as the one shown above, with 4 squares sharing 2 rows, columns and blocks, 3 of which share the same two possibilities, and the 4th having the two possibilities plus one or more extra possibilities, then you can remove the original two possibilities from the 4th square. In this case, R4C3 can be reduced to <36>.

The proof is pretty straightforward once you get your head around the basic idea.

Assume R4C3 is 2. That forces R4C2 to be 5, R7C2 to be 2, and R7C3 to be 5. That’s the deadly pattern; you can swap the 2’s and 5’s and the puzzle still can be filled in. So if the Sudoku is valid, R4C3 cannot be 2.

The exact same logic applies if you assume R4C3 is 5. So R4C3 can’t be a 2, and can’t be a 5 -- it must be either 3 or 6.

This pattern is called a “Type-1 Unique Rectangle.” But it turns out there are several other interesting unique rectangle patterns, all of which depend on having to avoid the deadly pattern.

Consider this puzzle:
Code: Select all
+----------------------+----------------------+----------------------+
| 9      3      6      | 14     128    148    |-24     7      5      | (note: the squares that
| 8      7      5      | 49    -29     3      |*246   *246    1      |  can be reduced are
| 1      4      2      | 7      5      6      | 3      8      9      |  marked by -'s)
+----------------------+----------------------+----------------------+
| 236    26     7      | 134569 1369   149    | 8      1359   24     |
| 5      1      4      | 8      39     2      | 7      39     6      |
| 236    8      9      | 13456  7      14     | 15     135    24     |
+----------------------+----------------------+----------------------+
| 4      25     18     | 16     168    7      | 9      25     3      |
| 236    256    138    | 139    4      189    | 125    125    7      |
| 7      9      13     | 2      13     5      |*46    *46     8      |
+----------------------+----------------------+----------------------+
(Graphic representation)

Here we have a similar pattern, but this time, R2C7 and R2C8, the squares which share the same block have a single extra possibility - in this case, <2>.

To make subsequent discussion easier to follow, we will refer to the two squares that only have two possibilities as the floor squares (because they form the foundation of the Unique Rectangle); the other two squares, with extra possibilities shall be called the roof squares.

In this “Type-2 Unique Rectangle”, one of the blocks contains the floor squares, and the other contains the roof squares. In order to avoid the deadly pattern, 2 must appear in either R2C7 or R2C8 (the roof squares). Therefore, it can be removed from all other squares in the groups that contain both of the roof squares (in this case, row 2 and block 3).

Now that you’ve gotten your head around the basic unique rectangle concept, the proof should be pretty obvious:

If neither R2C7 or R2C8 contains a <2>, then they both become squares with possibilities <46>. This results in the deadly pattern - so one of those squares must be the <2>, and none of the other squares in the intersecting groups can contain the 2. So R1C7 and R2C5 can have <2> removed, immediately solving them.

There is a second variant of Type-2 Unique Rectangles:
Code: Select all
+----------------+----------------+----------------+
| 2    9    1678 | 3    4678 46   | 156  157  17   |
| 67   146  1467 | 5    2    9    | 136  8    137  |
| 3    5    678  | 68   678  1    | 4    9    2    |
+----------------+----------------+----------------+
| 1   *346 -2346 | 9   *346  5    | 8    247  47   |
| 8    7    456  | 46   1    2    | 59   3    49   |
| 9   *34   25   | 7   *34   8    | 125  125  6    |
+----------------+----------------+----------------+
| 4    2    9    | 1    5    3    | 7    6    8    |
| 5    8    136  | 2    469  7    | 139  14   1349 |
| 67   136  1367 | 468  4689 46   | 1239 124  5    |
+----------------+----------------+----------------+
(Graphic representation)

In this puzzle, we have the same pattern of 4 squares in 2 blocks, 2 rows and 2 columns. The floor squares are R6C2 and R6C5, and the roof squares are R4C2 and R4C5. However, in this Unique Rectangle, each of the blocks contains one floor and one roof square. This is perfectly fine, but it means that the only group that contains both of the roof squares is row 4, so that is the only group that you can attempt to reduce; in this case, R4C3 cannot contain a 6. This is called at “Type-2B Unique Rectangle.”

Unique Rectangles can also be used to find locked sets. Consider the following puzzle:
Code: Select all
+----------------------+----------------------+----------------------+
| 478    1      9      | 78     3      5      |*26    *26     47     | (note: the squares marked
| 3457   345    6      | 9      24     27     | 1      34     8      |  with +'s form part of the
| 3478   2      378    | 1      46     68     | 379    349    5      |  locked set)
+----------------------+----------------------+----------------------+
| 3589   35689  4      | 38     56     1      | 3589   7      2      |
| 27     358    1      | 4      9      27     | 358    358    6      |
| 235789 35689  2378   | 378    256    68     | 4      1      39     |
+----------------------+----------------------+----------------------+
| 1      7     -23     | 5      8      4      |*2369  *2369  +39     |
| 2489   489    5      | 6      7      3      | 28     248    1      |
| 6      348    38     | 2      1      9      |-3578  -3458   47     |
+----------------------+----------------------+----------------------+
(Graphic representation)

In this puzzle, the roof squares contain the same two extra possibilities. Squares R7C7 and R7C8 both have possibilities <2369>; the <26> matching the floor squares, plus extra possibilities <39>.

In order to preclude the deadly pattern, at least one of R7C7 and R7C8 has to be a 3 or a 9. We don’t know which square it’s in, or whether it is a 3 or a 9. It’s sort of fuzzy, which reminds me of quantum physics. But what we can do is treat the two squares as a single “quantum square” with possibilities <39>, and use this to find locked sets in their shared groups that permit reductions to be made.

For example, in the puzzle above, R7C7+R7C8 are the quantum square, and it plus R7C9 form a locked pair on 39 in both row 7 and block 9. We know there has to be a 3 or a 9 in R7C7 or R7C8 in order to prevent the deadly pattern; if it is a 3, then R7C9 must be a 9; if it is a 9, then R7C9 must be a 3. Either way, <39> can be excluded from other squares in their common groups. So R7C3, R9C7 and R9C8 can have <3> removed.

It is important to realize that these “Type-3 Unique Rectangles” are not limited to roof squares that share 2 possibilities. In fact, you can treat the roof squares as a single quantum-square containing all the possibilities that are not in the floor squares! Consider this puzzle:
Code: Select all
+----------------+----------------+----------------+
| 2    1    69   | 4    5    7    | 8    69   3    |
| 7    5689 689  |*16   3    289  | 4    269 *156  |
| 5689 4    3    |*16   29   289  | 2579 2679*1567 |
+----------------+----------------+----------------+
| 1    7    689  | 5    4    29   | 23   236  68   |
| 3    2    5    | 8    7    6    | 1    4    9    |
| 689  689  4    | 29   1    3    | 27   5   -678  |
+----------------+----------------+----------------+
| 589  3    2    | 79   89   4    | 6    1   +57   |
| 689  689  1    | 279  289  5    | 379  379  4    |
| 4    59   7    | 3    6    1    | 59   8    2    |
+----------------+----------------+----------------+
(Graphic representation)

Here, the roof squares (R2C9 and R3C9) contain extra possibilities <5> and <57> respectively. This means they form a quantum-square with possibilities <57>, which forms a locked pair with R7C9.

It is quite possible to find Type-3 Unique Rectangles that form locked triples or even quads. For example, if the quantum square was <57>, and you found two other squares <58> and <78>, you would have found a locked triple on <578>.

Finally, just as Type-2 Unique Rectangles have a -B variant, so do Type-3’s! And if you think about it, Type-1’s don’t have a -B variant because they actually are both at the same time, depending on which squares you consider to be the floor squares.

Also, a Type-2 is really a Type-3, but instead of a locked set, you’ve got a “locked single.”

Wrapping up our discussion of Type-3 Unique Rectangles, just as with Type-2's, there is a -B variant.
Code: Select all
+-------------+-------------+-------------+
| 2   1  *69  | 4   5   7   | 8  *69  3   |
| 7  -568*689 | 16  3  +28  | 4  *269 15  |
| 568 4   3   | 16  9   28  | 25  267 157 |
+-------------+-------------+-------------+
| 1   7   68  | 5   4   9   | 23  23  68  |
| 3   2   5   | 8   7   6   | 1   4   9   |
| 689 689 4   | 2   1   3   | 7   5   68  |
+-------------+-------------+-------------+
| 59  3   2   | 79  8   4   | 6   1   57  |
| 68  68  1   | 79  2   5   | 39  37  4   |
| 4   59  7   | 3   6   1   | 59  8   2   |
+-------------+-------------+-------------+
(Graphic representation)

As with Type-2B’s, since the roof squares are not in the same block, you can only look for reductions in row 2. In this case, the quantum square plus R2C6 form a locked set on <28>, and you can remove <8> from R2C2.

To be added here: Hidden Set Variants; Type-4 conjugate pair variants, etc...

Shorthand Representation of Unique Rectangles

A reasonably standard shorthand for representing Unique Rectangles has evolved, as follows:
Code: Select all
a|c            A unique rectangle; ab = floor squares, cd = roof squares.
b|d            The vertical bars represent the block boundary

a|b            A -B variant unique rectangle
c|d

12|12A...      A Type-1 unique rectangle.  12 are the common possibilities;
12|12          A.. represents 1 or more extra possibilities

12|12A         A Type-2 unique rectangle.  A is the extra
12|12A         common value.  Sometimes A is replaced by 3.

12 |12         A Type-2B unique rectangle
12A|12A

12|12A...      A Type-3 unique rectangle.  A... are the 1 or more extra possibilities
12|12B...      in one roof square; B... the extras in the other.  The
               quantum-square is the union of A... and B...
           
12    |12      A Type-3B unique rectangle.
12A...|12B...
MadOverlord
 
Posts: 81
Joined: 10 June 2005

Postby PaulIQ164 » Sun Oct 23, 2005 4:59 pm

Although it's obvious, it might be worth mentioning that the deadly pattern is not deadly if one of the cells in it is a clue.
PaulIQ164
 
Posts: 533
Joined: 16 July 2005

Postby MadOverlord » Sun Oct 23, 2005 6:47 pm

PaulIQ164 wrote:Although it's obvious, it might be worth mentioning that the deadly pattern is not deadly if one of the cells in it is a clue.


By this I think you mean that none of the squares can be solved, right? I think this is strongly implied by the definition and examples, but if you have alternate wording, please suggest it.
MadOverlord
 
Posts: 81
Joined: 10 June 2005

Postby MadOverlord » Sun Oct 23, 2005 10:24 pm

Here is my second draft of "The Ultimate Guide to Unique Rectangles" for your comments and suggestions. This is largely based on my documentation of the heuristic in the Sudoku Susser manual.

This version covers Type-1, -2, -2B, -3 and -3B (locked sets only), -4 and -4B variants. When I get sample puzzles for -3 (hidden set), I will add them. Also, please specifically comment upon sub-variants that I have missed (such as when one of the digits forms a conjugate pair)

As this document evolves, I will post complete new versions of it into this thread.

Changes in 0.2 : added Type-4 Unique Rectangles

The Ultimate Guide to Unique Rectangles - version 0.2

The Unique Rectangles pattern was first noticed by ??? and subsequently expanded upon by contributions from ???,??? and ????.

Unique Rectangles take advantage of the fact that Sudoku can only have 1 solution in order to make useful inferences. For example, consider the following puzzle:
Code: Select all
+----------------+----------------+----------------+
| 25   8    24   | 45   6    3    | 9    7    1    | (note: the four squares
| 357  37   1    | 58   2    9    | 6    4    358  |  in the unique rectangle
| 6    39   349  | 458  7    1    | 238  28   2358 |  are marked with *'s)
+----------------+----------------+----------------+
| 4   *25  *2356 | 7    9    8    | 1    26   23   |
| 27   1    26   | 3    4    5    | 278  268  9    |
| 379  379  8    | 6    1    2    | 37   5    4    |
+----------------+----------------+----------------+
| 8   *25  *25   | 1    3    7    | 4    9    6    |
| 39   4    39   | 2    8    6    | 5    1    7    |
| 1    6    7    | 9    5    4    | 28   3    28   |
+----------------+----------------+----------------+
(Graphic representation)

Note the squares R4C2, R4C3, R6C2 and R6C3; they form a group of 4 squares that share exactly 2 blocks, 2 rows and 2 columns. The important insight here is that if they also only share 2 possibilities, then the puzzle has more than one solution!

If you think about it, it is obvious: if in the above puzzle, the four squares had possibilities <25>, then two diagonally-opposite squares must be <2>, and the other two must be <5>. No matter which way you arrange them, the 2 rows, columns and blocks would have one 2 and one 5, and you could exchanges the 2’s and 5’s and the puzzle would still be valid -- the puzzle would have more than one solution. This configuration of 4 squares with the same 2 possibilities in two rows, two columns and two blocks is called the “deadly pattern.” Find it, and you know you’ve gone wrong. But the knowledge that that particular pattern cannot appear lets you make progress:

Here’s how: If you can find a rectangle such as the one shown above, with 4 squares sharing 2 rows, columns and blocks, 3 of which share the same two possibilities, and the 4th having the two possibilities plus one or more extra possibilities, then you can remove the original two possibilities from the 4th square. In this case, R4C3 can be reduced to <36>.

The proof is pretty straightforward once you get your head around the basic idea.

Assume R4C3 is 2. That forces R4C2 to be 5, R7C2 to be 2, and R7C3 to be 5. That’s the deadly pattern; you can swap the 2’s and 5’s and the puzzle still can be filled in. So if the Sudoku is valid, R4C3 cannot be 2.

The exact same logic applies if you assume R4C3 is 5. So R4C3 can’t be a 2, and can’t be a 5 -- it must be either 3 or 6.

This pattern is called a “Type-1 Unique Rectangle.” But it turns out there are several other interesting unique rectangle patterns, all of which depend on having to avoid the deadly pattern.

Consider this puzzle:
Code: Select all
+----------------------+----------------------+----------------------+
| 9      3      6      | 14     128    148    |-24     7      5      | (note: the squares that
| 8      7      5      | 49    -29     3      |*246   *246    1      |  can be reduced are
| 1      4      2      | 7      5      6      | 3      8      9      |  marked by -'s)
+----------------------+----------------------+----------------------+
| 236    26     7      | 134569 1369   149    | 8      1359   24     |
| 5      1      4      | 8      39     2      | 7      39     6      |
| 236    8      9      | 13456  7      14     | 15     135    24     |
+----------------------+----------------------+----------------------+
| 4      25     18     | 16     168    7      | 9      25     3      |
| 236    256    138    | 139    4      189    | 125    125    7      |
| 7      9      13     | 2      13     5      |*46    *46     8      |
+----------------------+----------------------+----------------------+
(Graphic representation)

Here we have a similar pattern, but this time, R2C7 and R2C8, the squares which share the same block have a single extra possibility - in this case, <2>.

To make subsequent discussion easier to follow, we will refer to the two squares that only have two possibilities as the floor squares (because they form the foundation of the Unique Rectangle); the other two squares, with extra possibilities shall be called the roof squares.

In this “Type-2 Unique Rectangle”, one of the blocks contains the floor squares, and the other contains the roof squares. In order to avoid the deadly pattern, 2 must appear in either R2C7 or R2C8 (the roof squares). Therefore, it can be removed from all other squares in the groups that contain both of the roof squares (in this case, row 2 and block 3).

Now that you’ve gotten your head around the basic unique rectangle concept, the proof should be pretty obvious:

If neither R2C7 or R2C8 contains a <2>, then they both become squares with possibilities <46>. This results in the deadly pattern - so one of those squares must be the <2>, and none of the other squares in the intersecting groups can contain the 2. So R1C7 and R2C5 can have <2> removed, immediately solving them.

There is a second variant of Type-2 Unique Rectangles:
Code: Select all
+----------------+----------------+----------------+
| 2    9    1678 | 3    4678 46   | 156  157  17   |
| 67   146  1467 | 5    2    9    | 136  8    137  |
| 3    5    678  | 68   678  1    | 4    9    2    |
+----------------+----------------+----------------+
| 1   *346 -2346 | 9   *346  5    | 8    247  47   |
| 8    7    456  | 46   1    2    | 59   3    49   |
| 9   *34   25   | 7   *34   8    | 125  125  6    |
+----------------+----------------+----------------+
| 4    2    9    | 1    5    3    | 7    6    8    |
| 5    8    136  | 2    469  7    | 139  14   1349 |
| 67   136  1367 | 468  4689 46   | 1239 124  5    |
+----------------+----------------+----------------+
(Graphic representation)

In this puzzle, we have the same pattern of 4 squares in 2 blocks, 2 rows and 2 columns. The floor squares are R6C2 and R6C5, and the roof squares are R4C2 and R4C5. However, in this Unique Rectangle, each of the blocks contains one floor and one roof square. This is perfectly fine, but it means that the only group that contains both of the roof squares is row 4, so that is the only group that you can attempt to reduce; in this case, R4C3 cannot contain a 6. This is called at “Type-2B Unique Rectangle.”

Unique Rectangles can also be used to find locked sets. Consider the following puzzle:
Code: Select all
+----------------------+----------------------+----------------------+
| 478    1      9      | 78     3      5      |*26    *26     47     | (note: the squares marked
| 3457   345    6      | 9      24     27     | 1      34     8      |  with +'s form part of the
| 3478   2      378    | 1      46     68     | 379    349    5      |  locked set)
+----------------------+----------------------+----------------------+
| 3589   35689  4      | 38     56     1      | 3589   7      2      |
| 27     358    1      | 4      9      27     | 358    358    6      |
| 235789 35689  2378   | 378    256    68     | 4      1      39     |
+----------------------+----------------------+----------------------+
| 1      7     -23     | 5      8      4      |*2369  *2369  +39     |
| 2489   489    5      | 6      7      3      | 28     248    1      |
| 6      348    38     | 2      1      9      |-3578  -3458   47     |
+----------------------+----------------------+----------------------+
(Graphic representation)

In this puzzle, the roof squares contain the same two extra possibilities. Squares R7C7 and R7C8 both have possibilities <2369>; the <26> matching the floor squares, plus extra possibilities <39>.

In order to preclude the deadly pattern, at least one of R7C7 and R7C8 has to be a 3 or a 9. We don’t know which square it’s in, or whether it is a 3 or a 9. It’s sort of fuzzy, which reminds me of quantum physics. But what we can do is treat the two squares as a single “quantum square” with possibilities <39>, and use this to find locked sets in their shared groups that permit reductions to be made.

For example, in the puzzle above, R7C7+R7C8 are the quantum square, and it plus R7C9 form a locked pair on 39 in both row 7 and block 9. We know there has to be a 3 or a 9 in R7C7 or R7C8 in order to prevent the deadly pattern; if it is a 3, then R7C9 must be a 9; if it is a 9, then R7C9 must be a 3. Either way, <39> can be excluded from other squares in their common groups. So R7C3, R9C7 and R9C8 can have <3> removed.

It is important to realize that these “Type-3 Unique Rectangles” are not limited to roof squares that share 2 possibilities. In fact, you can treat the roof squares as a single quantum-square containing all the possibilities that are not in the floor squares! Consider this puzzle:
Code: Select all
+----------------+----------------+----------------+
| 2    1    69   | 4    5    7    | 8    69   3    |
| 7    5689 689  |*16   3    289  | 4    269 *156  |
| 5689 4    3    |*16   29   289  | 2579 2679*1567 |
+----------------+----------------+----------------+
| 1    7    689  | 5    4    29   | 23   236  68   |
| 3    2    5    | 8    7    6    | 1    4    9    |
| 689  689  4    | 29   1    3    | 27   5   -678  |
+----------------+----------------+----------------+
| 589  3    2    | 79   89   4    | 6    1   +57   |
| 689  689  1    | 279  289  5    | 379  379  4    |
| 4    59   7    | 3    6    1    | 59   8    2    |
+----------------+----------------+----------------+
(Graphic representation)

Here, the roof squares (R2C9 and R3C9) contain extra possibilities <5> and <57> respectively. This means they form a quantum-square with possibilities <57>, which forms a locked pair with R7C9.

It is quite possible to find Type-3 Unique Rectangles that form locked triples or even quads. For example, if the quantum square was <57>, and you found two other squares <58> and <78>, you would have found a locked triple on <578>.

Finally, just as Type-2 Unique Rectangles have a -B variant, so do Type-3’s! And if you think about it, Type-1’s don’t have a -B variant because they actually are both at the same time, depending on which squares you consider to be the floor squares.

Also, a Type-2 is really a Type-3, but instead of a locked set, you’ve got a “locked single.”

Wrapping up our discussion of Type-3 Unique Rectangles, just as with Type-2's, there is a -B variant.
Code: Select all
+-------------+-------------+-------------+
| 2   1  *69  | 4   5   7   | 8  *69  3   |
| 7  -568*689 | 16  3  +28  | 4  *269 15  |
| 568 4   3   | 16  9   28  | 25  267 157 |
+-------------+-------------+-------------+
| 1   7   68  | 5   4   9   | 23  23  68  |
| 3   2   5   | 8   7   6   | 1   4   9   |
| 689 689 4   | 2   1   3   | 7   5   68  |
+-------------+-------------+-------------+
| 59  3   2   | 79  8   4   | 6   1   57  |
| 68  68  1   | 79  2   5   | 39  37  4   |
| 4   59  7   | 3   6   1   | 59  8   2   |
+-------------+-------------+-------------+
(Graphic representation)

As with Type-2B’s, since the roof squares are not in the same block, you can only look for reductions in row 2. In this case, the quantum square plus R2C6 form a locked set on <28>, and you can remove <8> from R2C2.

Cracking the Rectangle with Conjugate Pairs

An interesting observation is that it is sometimes possible to remove one of the original pair of possibilities from the roof squares. Consider the following
puzzle:
Code: Select all
+----------------+----------------+----------------+
| 12   9    17   | 8    3    6    | 57   4    25   |
| 5    8    6    | 7    2    4    | 3    1    9    |
| 27   4    3    |*59   1   *59   | 8    6    27   |
+----------------+----------------+----------------+
| 8    27   5    | 6    9    3    | 4    27   1    |
| 9    3    47   | 2    4578 1    | 57   578  6    |
| 6    127  147  | 45   4578 58   | 9    2578 3    |
+----------------+----------------+----------------+
| 147  17   2    |*459  458 *589  | 6    3    57   |
| 47   6    9    | 3    45   2    | 1    57   8    |
| 3    5    8    | 1    6    7    | 2    9    4    |
+----------------+----------------+----------------+
(Graphic representation)

Look closely at the roof squares, R7C4 and R7C6, but this time, don’t look at their extra possibilities; look at the possibilities they share with the floor squares.

If you look carefully, you’ll see that in block 8, the roof squares are the only squares that can contain an <9>. This means that, no matter what, one of those squares must be <9> -- and from this you can conclude that neither of the squares can contain a <5>, since this would create the “deadly pattern”! So you can remove <5> from R7C4 and R7C6.

Nomenclature: When two squares are the only two squares in a group that can have a particular value, they are referred to as a “conjugate pair” on that value.

This is an example of a “Type-4 Unique Rectangle”. As you have probably realized, since the roof squares are in the same block, you can search for conjugate pairs in both of their common groups (the row and the block, in this case).

And, as you might expect, there is a “Type-4B Unique Rectangle” variant, in which the floor squares are not in the same block, and you can only look for the conjugate pairs in their common row or column. For example:
Code: Select all
+----------------+----------------+----------------+
|*127  9    17   | 8    3    6    | 57   4   *257  |
| 5    8    6    | 7    2    4    | 3    1    9    |
|*27   4    3    | 59   1    59   | 8    6   *27   |
+----------------+----------------+----------------+
| 8    27   5    | 6    9    3    | 4    27   1    |
| 9    3    47   | 2    4578 1    | 57   578  6    |
| 6    127  147  | 45   4578 58   | 9    2578 3    |
+----------------+----------------+----------------+
| 147  17   2    | 459  458  589  | 6    3    57   |
| 47   6    9    | 3    45   2    | 1    57   8    |
| 3    5    8    | 1    6    7    | 2    9    4    |
+----------------+----------------+----------------+
(Graphic representation)

In this case, since <2> can only appear in row 1 in the roof squares, 7 can be removed from both of them.

If this puzzle looks familiar, it’s because once you find the Type-4B Unique Rectangle (in the first example), you immediately get the second example!

As Type-4 Unique Rectangle solutions "destroy" the Unique Rectangle, it is usually best to look for them only after you've done any other possible Unique Rectangle reductions.

To be added here: Hidden Set Variants; etc...

Shorthand Representation of Unique Rectangles

A reasonably standard shorthand for representing Unique Rectangles has evolved, as follows:
Code: Select all
a|c            A unique rectangle; ab = floor squares, cd = roof squares.
b|d            The vertical bars represent the block boundary

a|b            A -B variant unique rectangle
c|d

12|12A...      A Type-1 unique rectangle.  12 are the common possibilities;
12|12          A.. represents 1 or more extra possibilities

12|12A         A Type-2 unique rectangle.  A is the extra
12|12A         common value.  Sometimes A is replaced by 3.

12 |12         A Type-2B unique rectangle
12A|12A

12|12A...      A Type-3 unique rectangle.  A... are the 1 or more extra possibilities
12|12B...      in one roof square; B... the extras in the other.  The
               quantum-square is the union of A... and B...
           
12    |12      A Type-3B unique rectangle.
12A...|12B...
MadOverlord
 
Posts: 81
Joined: 10 June 2005

Postby Lummox JR » Tue Oct 25, 2005 12:24 am

I don't think describing the two cells as a single quantum cell is really kosher; it makes more sense to describe a quantum pair in which one cell has all possibilities, one has all but the initial pair.
Lummox JR
 
Posts: 125
Joined: 22 September 2005

Postby MadOverlord » Tue Oct 25, 2005 1:39 am

Lummox JR wrote:I don't think describing the two cells as a single quantum cell is really kosher; it makes more sense to describe a quantum pair in which one cell has all possibilities, one has all but the initial pair.


I chose that explanation because it made it easier for people to understand how to find the locked-set rectangles. In that instance, the only thing that's important are the extra possibilities, and it seemed to me to be simpler to describe them as a single square... then finding locked sets on a set of 8 squares instead of 9.

I recognize that your way of describing the squares may have some advantages when it comes to the hidden-set unique rectangles, and once I've got them sussed out, I will be open to amending the expanation to use a description that works for both -- or possibly coming up with a better description.

This is why I so desperately need some complete sample puzzles with the logic of the hidden-set reduction explained with reference to the actual puzzle.
MadOverlord
 
Posts: 81
Joined: 10 June 2005

Postby Lummox JR » Tue Oct 25, 2005 4:01 am

Here's a puzzle where uniqueness 3 with a hidden subset comes into play. It doesn't crack the puzzle, since after that my solver goes on to use coloring and supercoloring, but it at least is finding something. Here's the original puzzle:
Code: Select all
. . .|. . .|. . 2
4 . .|8 . .|. . .
2 . .|. 1 5|. 3 .
-----------------
. . 9|. . .|1 . 4
5 8 .|. 7 .|. . .
. 2 4|. . .|. . .
-----------------
. . .|. 8 .|9 . .
7 . .|. . .|4 . 1
. 9 .|6 . .|7 . .

And the candidate list where uniqueness 3 applies:
Code: Select all
+----------------+----------------+----------------+
| 9    1    8    | 37   36   367  | 5    4    2    |
| 4    35   35   | 8    29   29   | 6    1    7    |
| 2    6    7    | 4    1    5    | 8    3    9    |
+----------------+----------------+----------------+
| 36   7    9    | 23   236  8    | 1    5    4    |
| 5    8    13   | 13   7    4    | 2    9    6    |
| 16   2    4    | 159  569  169  | 3    7    8    |
+----------------+----------------+----------------+
| 13   4    2    | 1357 8    137  | 9    6    35   |
| 7    35   6    | 2359 2359 239  | 4    8    1    |
| 8    9    135  | 6    4    13   | 7    2    35   |
+----------------+----------------+----------------+

If you look at the 29's, you'll see in box 8 they align with 239 and 2359. Uniqueness 3 says that in either row 8 or box 8, or perhaps both, you may be able to find a partial naked subset with the 35's and a complementary partial hidden subset with the 29's. And indeed such a subset exists. You either have a partial naked quad with 1357, or a partial hidden pair 29.

As you can see, in box 8, 2 and 9 can only appear in the 3 cells in row 8. We know from the uniqueness criteria that the two cells occupied by 2 and 9 in the solution can't both be (5,8) and (6,8), because that would create the deadly pattern. Since there's only one other cell they can use, (4,8), only 2 or 9 can go there. The other digit goes in one of the two other cells.

You can also turn this around for the naked quad. We know that cells (4,7)=1357, (6,7)=137, and (6,9)=13. Since at least one of the cells (5,8) and (6,8) does not contain a 2 or a 9, they expose either a naked 3 or a naked 35. Since we don't know which, we consider only the union of the two, 35, and with that we get a naked quad from 1357, 137, 13, and 35.

From a quantum analysis this makes perfect sense. The union of the two unknown cells is 2359, yet we know at least one of them cannot have 29. Therefore the two cells work out to 35 and 2359 in a quantum state. Knowing this breakdown of their states, however, allows a subset solver to find naked or hidden subsets easily. I call it a partial subset because if it exists, it will include one (and only one) of the unknown cells, and we can do no eliminations within that set because of the uncertainty as to which is which.
Lummox JR
 
Posts: 125
Joined: 22 September 2005

Postby Lummox JR » Tue Oct 25, 2005 5:16 am

Here's a puzzle where uniqueness 3 with a hidden subset comes into play. It doesn't crack the puzzle, since after that my solver goes on to use coloring and supercoloring, but it at least is finding something. Here's the original puzzle:
Code: Select all
. . .|. . .|. . 2
4 . .|8 . .|. . .
2 . .|. 1 5|. 3 .
-----------------
. . 9|. . .|1 . 4
5 8 .|. 7 .|. . .
. 2 4|. . .|. . .
-----------------
. . .|. 8 .|9 . .
7 . .|. . .|4 . 1
. 9 .|6 . .|7 . .

And the candidate list:
Code: Select all
+----------------+----------------+----------------+
| 9    1    8    | 37   36   367  | 5    4    2    |
| 4    35   35   | 8    29   29   | 6    1    7    |
| 2    6    7    | 4    1    5    | 8    3    9    |
+----------------+----------------+----------------+
| 36   7    9    | 23   236  8    | 1    5    4    |
| 5    8    13   | 13   7    4    | 2    9    6    |
| 16   2    4    | 159  569  169  | 3    7    8    |
+----------------+----------------+----------------+
| 13   4    2    | 1357 8    137  | 9    6    35   |
| 7    35   6    | 2359 2359 239  | 4    8    1    |
| 8    9    135  | 6    4    13   | 7    2    35   |
+----------------+----------------+----------------+

If you look at the 29's, you'll see in box 8 they align with 239 and 2359. Uniqueness 3 says that in either row 8 or box 8, or perhaps both, you may be able to find a partial naked subset with the 35's and a complementary partial hidden subset with the 29's. And indeed such a subset exists. You either have a partial naked quad with 1357, or a partial hidden pair 29.

As you can see, in box 8, 2 and 9 can only appear in the 3 cells in row 8. We know from the uniqueness criteria that the two cells occupied by 2 and 9 in the solution can't both be (5,8) and (6,8), because that would create the deadly pattern. Since there's only one other cell they can use, (4,8), only 2 or 9 can go there. The other digit goes in one of the two other cells.

You can also turn this around for the naked quad. We know that cells (4,7)=1357, (6,7)=137, and (6,9)=13. Since at least one of the cells (5,8) and (6,8) does not contain a 2 or a 9, they expose either a naked 3 or a naked 35. Since we don't know which, we consider only the union of the two, 35, and with that we get a naked quad from 1357, 137, 13, and 35.

Here's another puzzle with a partial hidden subset. This one is easily solved by coloring, so the uniqueness test doesn't help much here, but it's still work noting:
Code: Select all
. 3 9|. . .|. . .
. . 2|. . .|. 7 4
. . .|. . .|. 1 .
-----------------
. . .|. . 8|. . .
. 6 .|5 . 2|. 8 .
7 . 1|. . 4|2 . .
-----------------
. . .|7 . .|. . 8
. 4 .|. 6 .|9 . 1
2 . .|. . 3|. 5 6

In this puzzle a partial naked 28 (with original candidates 17) eliminates an 8 that was already part of a swordfish. However it also nails a 2, and another 8 that was inside the swordfish pattern itself and wouldn't have been eliminated. Both the 2 and the 8 open up conjugate pairs that I believe are quite important for supercoloring to find a quick solution; otherwise it has to make a few other eliminations first.
Code: Select all
2 . .|. 4 .|6 . 5
. . .|. 7 .|3 . .
. 5 9|. . 6|. . .
-----------------
. 8 .|3 1 .|. . .
. 7 .|. . .|. . .
. . 6|. . 9|2 . 3
-----------------
6 2 .|. . 8|. 9 .
5 . .|. . .|4 . .
. . .|. . .|. . 6

In this puzzle you can find uniqueness 3 twice. Once here:
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  |
+----------------+----------------+----------------+

There the partial hidden pair is in column 9. Then after more eliminations you can find another one in box 1 (or column 1) here:
Code: Select all
+----------------+----------------+----------------+
| 457  9    3    | 57   2    1    | 6    457  8    |
| 157  8    2    | 57   4    6    | 159  579  3    |
| 1457 46   16   | 9    3    8    | 145  2457 25   |
+----------------+----------------+----------------+
| 2    3    16   | 8    9    7    | 45   45   16   |
| 48   46   9    | 1    5    2    | 78   3    67   |
| 18   7    5    | 4    6    3    | 2    89   19   |
+----------------+----------------+----------------+
| 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  |
+----------------+----------------+----------------+

This puzzle also has a partial hidden pair:
Code: Select all
1 2 .|. . .|. . 3
8 6 .|. 4 .|. . .
. . .|. 7 .|. . 1
-----------------
. 8 4|. . .|5 7 .
. . .|7 . .|. . .
. . .|5 . .|6 . 8
-----------------
. . .|4 8 .|. 2 .
. . .|. . 9|. . 6
6 9 .|. 2 .|. . .

Those were all generated by a 500-puzzle run of my solver. I don't think partial hidden sets are more common than partial naked ones, but they happened to come up a lot here.
Lummox JR
 
Posts: 125
Joined: 22 September 2005

Postby MadOverlord » Tue Oct 25, 2005 11:37 am

Okay, this makes things a lot more clear. I'm going to release Susser 2.0.4 without the hidden set uniqueness today, but I should be able to implement it over the next few days.

I now think I understand your reasoning for saying that something like:

12|123
12|124

can be thought of as

12|34
12|1234

If I am thinking along the right lines here, then important insight here is: to avoid the deadly pattern, if a candidate hidden set exists, all the 12's have to be concentrated on a single square. It is the hidden set itself that forces this restriction (otherwise we get n possibilities in n+1 squares).

So, if the hidden set containing 12 exists, then the possibilities are:

12|34
12|1234

or

12|1234
12|34

(not that we care at that point), but if we cannot find a hidden set, then we cannot make this inference.

From the standpoint of a solver, the 34:1234 assumption may be easier (to permit code-reuse), but I am wondering if, from the standpoint of a human solver looking for the pattern, just assuming a <12> quantum square might not be a simpler conceit. I shall think on this later; have to schlep the kids to the indoctrination center now.

Best,R
MadOverlord
 
Posts: 81
Joined: 10 June 2005

Next

Return to Advanced solving techniques

cron