The New Sudoku Players' Forum

[tso]

I'm amazed how common it is to find various uniqueness tactics, often which enable a much simpler solution to a puzzle. I've gone over several dozen puzzles that I *thought* required forcing chains and/or other advanced tactics that in some cases were reduced to easy puzzles by a unique rectangle that now seems so obvious. How did take until so recently to be for this concept to be exploited?

Below is one I found on Palmsudoku.com that includes a 6 cell unique loop.

Code: Select all

 *-----------*
 |3..|..5|...|
 |.2.|71.|...|
 |..9|.6.|.14|
 |---+---+---|
 |7..|.3.|9..|
 |6..|291|..8|
 |..5|.8.|..1|
 |---+---+---|
 |98.|.7.|1..|
 |...|.53|.2.|
 |...|1..|..6|
 *-----------*


At some point, I reach this point:

Code: Select all

 *-----------*
 |3.1|..5|...|
 |.2.|71.|...|
 |..9|36.|.14|
 |---+---+---|
 |718|53.|9.2|
 |6..|291|..8|
 |295|.87|..1|
 |---+---+---|
 |98.|.7.|1..|
 |1..|.53|.2.|
 |...|12.|..6|
 *-----------*


Code: Select all

 *--------------------------------------------------------------------*
 | 3      67     1      | 89     4      5      | 2678   678    79     |
 | 458    2      46     | 7      1      89     | 3568   35689  35     |
 | 58     57     9      | 3      6      28     | 2578   1      4      |
 |----------------------+----------------------+----------------------|
 | 7      1      8      | 5      3     +46     | 9     +46     2      |
 | 6      34     34     | 2      9      1      | 57     57     8      |
 | 2      9      5      |+46     8      7      | 346   +346    1      |
 |----------------------+----------------------+----------------------|
 | 9      8      24     |+46     7     +46     | 1      35     35     |
 | 1      46     467    | 89     5      3      | 478    2      79     |
 | 45     345    347    | 1      2      89     | 478    4789   6      |
 *--------------------------------------------------------------------*


The 6 cells marked with a plus sign form the swordfish shaped unique loop that allows placement of a 3 in r6c8 that leapfrogs having to find a couple of naked quads and an xyz-wing or a forcing chain, depending on the solvers preferences. Checking other Fiendish and Diabolicals on this site that are labeled as requiring forcing chains finds many (most?) can be solved, sometimes much more easily, with unique rectangles.

[MadOverlord]

I'm amazed how common it is to find various uniqueness tactics, often which enable a much simpler solution to a puzzle.

Yeah, it's looking like they are another "easy to see" pattern that is worth knowing about.

I'm strongly leaning towards adding a heuristic for them to the Susser, but want to hold off until Lummox and his Logic Posse weigh in on my definition of them and possibly find extensions.

It should be a relatively easy hack to extend Unique Rectangles to find these.

[bennys]

A set of cells U is twin uniqueness pattern(TUP) if for every unit in the sudoku the number of U members in it is 2 or 0.
A TUP is minimal if it does not include any nonempty TUP.
its obvious that every TUP is sum of minimal TUP's
So My question is:
Do we know up to equivalence how many minimal TUP's exist?
(I don't think there are that many but I could be wrong)

[Moschopulus]

I think your TUP's are the same as unavoidable sets.

An unavoidable set in a completed grid is any set of cells such that some permutation of the cells results in another valid completed grid.
Any puzzle made from that grid must have at least one clue from every unavoidable set. (hence the name)

An unavoidable set of size 4:
12.......
.........
.........
21.......
.........etc

These are the patterns you use for uniqueness. But you could use any unavoidable set. One of size 6 used above is

Code: Select all

.........
.........
.........
.....4.6.
.........
...6...4.
...4.6...
.........
.........


A general uniqueness rule could be stated for any unavoidable set.

It's not hard to classify unavoidable sets (TUPs) of size 4 and 6. All size 4 look like the above one.
Bigger than that and it gets complicated, but yes there are minimal ones of size 8, 10, 11, 12,....

[DanO]

Here are the possibilities on that Type-4 Unique Rectangle I posted earlier.

Menneske.no Super Hard #6753298

Code: Select all

+-------------------+-------------------+-------------------+
| 235   359   2359  | 7     14    59    | 8     14    6     |
| 57    6     8     | 3     14    59    | 149   2     17    |
| 4     79    1     | 8     6     2     | 39    379   5     |
+-------------------+-------------------+-------------------+
| 1235  1359  2359  | 6     7     8     | 12345 1345  123   |
| 13    4     6     | 5     2     13    | 7     8     9     |
| 8     1357  2357  | 4     9     13    | 6     135   123   |
+-------------------+-------------------+-------------------+
| 6     135   4     | 29    38    7     | 12359 1359  1238  |
| 9     2     357   | 1     38    4     | 35    6     378   |
| 137   8     37    | 29    5     6     | 1239  1379  4     |
+-------------------+-------------------+-------------------+

* Squares R7C5, R8C5, R7C9 and R8C9 form a Type-4 Unique Rectangle on <38>.

[bennys]

When we talk about twins it must be even number.
If we talk about triplets and above then we may get odd numbers.
My feeling is that are not more then 20 TUP patterns.
But it just a feeling.
For size 4 we have one
For size 6 I think we have two.
The maximal size is 14 I think.

[Lummox JR]

Yeah, it's looking like they are another "easy to see" pattern that is worth knowing about.

I'm strongly leaning towards adding a heuristic for them to the Susser, but want to hold off until Lummox and his Logic Posse weigh in on my definition of them and possibly find extensions.

Well, I don't have much to say about the loop form except that I'm not sure how easy it'll be to spot. I don't relish writing anything for it myself, for example.

As far as extensions go, the existing 4 tests should always be able to apply as long as both floor cells do share a common house. (Of course test 1 needn't check for this, since it has only one floor cell.) For tests 2-4 you'll still have the A format (same box and possibly also same line), and B (same line only). The logic is still the same: If the roof cells are 12, one of the floor cells cannot be 12 or the loop is an unavoidable set.

It should be a relatively easy hack to extend Unique Rectangles to find these.

I'm still scratching my head as to how I could do it. Running the tests with the two floor cells and knowing the roof pair is the easy part, since you can write a function to handle that. Finding the pattern with a loop would be the hard part.

[MadOverlord]

I'm still scratching my head as to how I could do it. Running the tests with the two floor cells and knowing the roof pair is the easy part, since you can write a function to handle that. Finding the pattern with a loop would be the hard part.

Elementary, my dear Lummox. While you are the Lord of Logic, I humbly take upon myself the mantle of Architect of Algorithms. I've been programming for so long (when I started, the bytes only had 6 bits) that I don't write functions anymore, I just remember them and type them in again.

The process is almost identical to finding Unique Rectangles. With Unique Rectangles, we look for a naked pair in a row or column. We then scan perpendicularly for candidate roof squares. If we find 2 roof squares, both in the same row/column, such that the 2 of our 4 squares are in one block and the other 2 are in another block, then we have a candidate to check.

For example, in this Type-2B unique rectangle:

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    |
+----------------+----------------+----------------+

We find a naked pair on 34 in R6. Since we found the naked pair in a row, we scan columns (C2 and C5) for candidate squares. We find candidates, they are in the same row, and they are 2 candidates in each of 2 blocks. So we can figure out what the roof squares are and check for reductions.

So far, so good.

Finding Unique Loops is only a tiny bit more difficult.

We proceed exactly as we did for Unique Rectangles, with a twist -- literally!

When we scan for candidate squares and find them, if they are not "next" to each other AND are the same as the floor squares, we simply record them as part of the loop, turn 90 degrees, and keep on looking. We will eventually either find the roof squares, or fail. Then, if all the blocks have either 2 candidate squares or 0, we have something we can check.

Consider the simple example previously posted:

Code: Select all

+-------------------+-------------------+-------------------+
| 5     189   89    | 69    1246  24    | 3     7     246   |
| 19    3     2     | 569   1456  7     | 456   456   8     |
|*46   *46    7     | 8     25    3     | 9     25    1     |
+-------------------+-------------------+-------------------+
| 28    5     38    | 4     9     6     | 7     1     23    |
| 29   *46    39    | 7     8     1     | 2456  246  *23456 |
|*46    7     1     | 2     3     5     | 8     9    *46    |
+-------------------+-------------------+-------------------+
| 3     12    4     | 56    7     9     | 1256  8     256   |
| 7     28    5     | 1     246   248   | 246   3     9     |
| 189   1289  6     | 3     245   248   | 1245  245   7     |
+-------------------+-------------------+-------------------+

We start off by finding the naked pair on 46 in R3. We set the candidate count of block 1 to 2, and look in C1 and C2. If we find candidate floor squares, then we may have found a loop (if we did, it would be a unique rectangle)

If not, instead of failing like we would for unique rectangles, we look for squares with exactly possibilities 46. We find them in R5(C2) and R6(C1). So we mark block 4 as having two possibilities, and head off along the columns looking for floor squares. We find them in R5C9 and R6C9, and have our unique loop.

Finally, consider the other sample configuration that was posted:

Code: Select all

+ - - - - - - - + - - - - - - - + - - - - - - - +
|   .   .   .   |   . c12   .   |   . c12x  .   |   
|   . a12   .   |   .   .   .   |   . b12   .   |   
|   . a12   .   |   . b12   .   |   .   .   .   |   
+ - - - - - - - + - - - - - - - + - - - - - - - +

We start off at the (a) squares, head over to the (b) squares, then up to the (c) squares. When we check, we find each block has 2 candidates, so we're OK.

For your amusement, consider the following (probably impossible for other reasons) loop.

Code: Select all

+ - - - - - - - + - - - - - - - + - - - - - - - +
|   .   . d12   |   .   . c12   |   .   .   .   |   
|   .   .   .   |   .   .   .   |   .   .   .   |   
| d12   .   .   |   . c12   .   |   .   .   .   |   
+ - - - - - - - + - - - - - - - + - - - - - - - +
|   .   .   .   |   .   .   .   |   .   .   .   |   
|   . a12   .   |   .   . b12   |   .   .   .   |   
|   . a12   .   |   . b12   .   |   .   .   .   |   
+ - - - - - - - + - - - - - - - + - - - - - - - +
|   .   .   .   |   .   .   .   |   .   .   .   |   
| e12   . e12x  |   .   .   .   |   .   .   .   |   
|   .   .   .   |   .   .   .   |   .   .   .   |   
+ - - - - - - - + - - - - - - - + - - - - - - - +

[Lummox JR]

Ah, a very interestng tack. That's very clever, and you don't have to worry about failing to find a naked roof pair because the nature of these loops demands that at least one pair is lined up. Probably to find the loops in a reasonable way you'd want to force the floor cells to be at the end of your search. E.g. if the floor cells are b12,c12, you'd want to start your roof cell search at c12,d12. Anything else will turn up either b12 or c12 with extra candidates (assuming this is not test 1) without lining the two up in a way that's convenient to recognize. Naturally it's crucial to look for all potential floors for a given starting roof pair.

[DanO]

Code: Select all

+-------------+-------------+-------------+
| .   .   .   | .   .   .   | .   .   .   |
| .   .   .   | 123 12  .   | .   .   .   |
| .   .   .   | .   .   .   | .   .   .   |
+-------------+-------------+-------------+
| .   .   .   | 123 .   .   | .   12  .   |
| 12  .   .   | .   12  .   | .   .   .   |
| 123 .   .   | 34  .   .   | .   123 .   |
+-------------+-------------+-------------+
| .   .   .   | .   .   .   | .   .   .   |
| .   .   .   | .   .   .   | .   .   .   |
| .   .   .   | .   .   .   | .   .   .   |
+-------------+-------------+-------------+

Good luck

[MadOverlord]

Probably to find the loops in a reasonable way you'd want to force the floor cells to be at the end of your search. E.g. if the floor cells are b12,c12, you'd want to start your roof cell search at c12,d12.

No, I disagree, it's much simpler to start with a floor candidate pair, then work your way to the roof. At each point, you either find a roof, find another two squares identical to the floor, or fail.

With complex loops, there are going to be several pairs that might be starting points, but only one of them is going to terminate at the roof, and thus be the real floor. The rest will quickly run into the roof and terminate.

You could get fancy in your loop detection, but the extra cost of doing that will be greater than the occasional (rare, since these patterns don't show up often) extra cost of trying the various starting points.

There is a famous programming puzzle that demonstrate why KISS is often the best way to go. You've got two arrays next to each other in memory like this:

123456ABCDEFGHIJKLMNOPQ

(where the digits are one array, the letters the other), and you have to exchange their order, to:

ABCDEFGHIJKLMNOPQ123456

Problem is, you don't have any extra memory, so you can't allocate a buffer. And you need it to be fast. And the arrays can be of any length, from a few bytes to megabytes.

One of the things I'm proudest about as a programmer was that the first time I was presented with this puzzle, I got the correct answer in under 10 seconds.

DanO, your example does not qualify as an Unique Loop; what are you trying to say?

[Nick67]

I think I've come up with a good way to explain how
to use type-3 unique rectangles to eliminate candidates.
So, I'd like to present alternative explanations for
2 examples presented earlier. I apologize in advance
if I am wrong and the explanations are redundant
or otherwise not useful.

Here's an example from an earlier post:

Code: Select all

+----------------+----------------+----------------+
| 39   4    1    | 2    6    5    | 389  378  379  |
| 5    7    6    | 3    9    8    | 4    1    2    |
| 2389 389  289  | 7    1    4    | 6    5    39   |
+----------------+----------------+----------------+
| 3478 6    478  | 5    2    9    | 1    378  347  |
| 1    39   279  | 4    8    6    | 239  237  5    |
| 2489 89   5    | 1    7    3    | 289  6    49   |
+----------------+----------------+----------------+
| 89   5    89   | 6    4    7    | 23   23   1    |
| 6    2    3    | 9    5    1    | 7    4    8    |
| 47   1    47   | 8    3    2    | 5    9    6    |
+----------------+----------------+----------------+


The floor cells are r9c1 and r9c3, and the roof cells
are r4c1 and r4c3. 4 and 7 are candidates in all of the
roof cells and floor cells. The extra candidates in the
roof cells are 3 and 8.

Assuming the puzzle has a unique solution, there
are 2 constraints on the roof cells:

1) At least 1 of the values 3 and 8 must go in 1 of the roof cells.

2) At least 1 of values 4 and 7 must go in a cell different than the roof cells, in each group that contains the roof cells.

Each of these constraints might lead to eliminating candidates.

Let's start with constraint 1, and combine it with other candidate information in box 4 to get the following:

- At least 1 of the values 3 and 8 must go in either r4c1 or r4c3
- 1 of the values 3 and 9 must go in r5c2
- 1 of the values 8 and 9 must go in r6c2

Combining this, the 3 values 3,8, and 9 must go
somewhere in the 4 cells r4c1, r4c3, r5c2, and r6c2.
So we can remove these 3 values as candidates from all
other cells in the box (we can remove an 8 and 9
from r6c1 and a 9 from r5c3).

The logic used is of course similar to that used
for a naked triple. But using that term in this
context might be confusing because 1) there
are 4 cells, and 2) some of the cells contain candidates
other than 3,8, and 9.

Let's reset the puzzle back to the candidates shown above, and
try to use constraint 2 instead of constraint 1.

Code: Select all

+----------------+----------------+----------------+
| 39   4    1    | 2    6    5    | 389  378  379  |
| 5    7    6    | 3    9    8    | 4    1    2    |
| 2389 389  289  | 7    1    4    | 6    5    39   |
+----------------+----------------+----------------+
| 3478 6    478  | 5    2    9    | 1    378  347  |
| 1    39   279  | 4    8    6    | 239  237  5    |
| 2489 89   5    | 1    7    3    | 289  6    49   |
+----------------+----------------+----------------+
| 89   5    89   | 6    4    7    | 23   23   1    |
| 6    2    3    | 9    5    1    | 7    4    8    |
| 47   1    47   | 8    3    2    | 5    9    6    |
+----------------+----------------+----------------+


The key is to look for all other cells (besides the
roof cells) that contain a 4 or 7 candidate. We find
cells r6c1 and r5c3.

By constraint 2, we know that at least 1 of the values 4 and 7 must
go into 1 of these 2 cells. By the listed candidates,
we see that a 2 must also go into 1 of these cells.
So, in the end, the two cells r6c1 and r5c3 are going
to contain a 2 and a 4 or 7, and we can eliminate
all other candidates from these 2 cells.

Using constraint 2 leads to the same result as using
constraint 1, in this case.

Here's one more example from this post:

Code: Select all

+----------------+----------------+----------------+
| 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  |
+----------------+----------------+----------------+


The cells that define the unique rectangle are marked with asterisks.
The floor cells are r7c2 and r9c2, and the roof cells
are r7c9 and r9c9. The extra candidates in the
roof cells are 7 and 9.

The 2 constraints on the roof cells are:

1) At least 1 of the values 7 and 9 must go in 1 of the roof cells.

2) At least 1 of the values 2 and 5 must go in a cell different
than the roof cells, in each group that
contains the roof cells.

Using constraint 1 and the listed candidates in column 9 we get:

- At least 1 of the values 7 and 9 must go in either r7c9 or r9c9
- 1 of the values 1,7, and 9 must go in r6c9
- 1 of the values 6,7, and 9 must go in r5c9
- 1 of the values 1 and 6 must go in r4c9

Combining this, the 4 values 1,6,7, and 9 must go
somewhere in the 5 cells listed above.
So we can remove these 4 values as candidates from all
other cells in column 9. (Here we can only remove
the 7 from r3c9).

Let's consider the same initial puzzle state again but this
time use constraint 2 instead.

Code: Select all

+----------------+----------------+----------------+
| 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  |
+----------------+----------------+----------------+


We look for all cells (besides the roof cells) containing
a 2 or 5 candidate. We find only r3c9. By constraint 2,
a 2 or a 5 must go into this cell in the end. So we can remove
7 as a candidate there.

Using constraint 2 again leads to the same result as using
constraint 1. (I'm not sure: will this always be true?)

[MadOverlord]

I think it is just easier to think about it this way:

In a Unique Rectangle such as:

12|1234
12|1256

We know to avoid the pattern, we can't have 12 in both of the roof squares. So what we really have is either

12|12
12|56

or

12|34
12|12

but we don't know which. So we treat them as a quantum pair of 12 and 3456.

Now if we can find a naked set containing 3456, or a hidden set containing 12 but not containing 3456, we can make reductions.

The one thing I'm still a bit fuzzy on (hey, Lummox!) is exactly why the

12|34
12|56

possibility never comes into play. Lummox has tried to explain it but it hasn't locked into my brain yet.

[PaulIQ164]

That's what I was wondering as well...

[Lummox JR]

I think you're about right, Nick, although it's a little hairy to follow. I believe though that you're mixing up the terms "roof" and "floor", since by my understanding the roof cells are the ones with just the naked pair.

We know to avoid the pattern, we can't have 12 in both of the roof squares. So what we really have is either

12|12
12|56

or

12|34
12|12

but we don't know which. So we treat them as a quantum pair of 12 and 3456.

Negatory! We treat them as a quantum pair of 123456 and 3456. It is important not to remove extra candidates from the 12 cell; at the very least the 12 cell must have one of the extras just to prevent a subset solver from finding a naked 12 that doesn't exist.

Now if we can find a naked set containing 3456, or a hidden set containing 12 but not containing 3456, we can make reductions.

It's for this reason that the 12 quantum cell needs at least one of the 3456 as another candidate. It won't be possible to find a naked subset with the 12 unless it already existed apart from the uniqueness test.

The one thing I'm still a bit fuzzy on (hey, Lummox!) is exactly why the

12|34
12|56

possibility never comes into play. Lummox has tried to explain it but it hasn't locked into my brain yet.

Well, it is tricky. The reason it doesn't come into play is that while we can't rule it out from the outset, it is of no use for finding partial subsets. The uniqueness logic lets us to remove 12 from just one cell, allowing a naked set of N+1 values in N non-floor cells with one of the floors to complete the set; if you could eliminate 12 from both you'd have N+1 values to fill N+2 cells, which doesn't work. If a naked set exists, it also gives us a complementary partial hidden set with M values in M-1 cells, where by uniqueness one and only one of the floor cells can be 12, completing the hidden set. If 12 can be eliminated from both, then you have M values that can only go in M-1 places, which doesn't work. So if a partial subset can be found, it's because one of the floor cells must contain 12 (the roof candidates). All that boiils down to a simple (but slippery to grasp) statement: If a partial subset exists when removing 12 from one floor cell, it proves 12 exists in the other.

The thing I think you've been trying to wrap your head around is: Why can't you have N+2 values in N non-floor cells for a partial naked set, or M values in M non-floor cells for a partial hidden set? The simple reason: Uniqueness doesn't give us enough information to remove 12 from both cells. It merely says it's a possibility. All we know for sure is that we can remove 12 from one floor cell, and if that gives us enough to work with, great--but in that case it'll also prove the 12 belongs in one of those cells. It is entirely possible in other cases that a partial subset exists if we remove 12 from both floor cells, but the existence of a potential partial subset doesn't prove anything. Just for clarity's sake let's call this a "fractional" subset.

Now if you have a potential partial subset, it does not prove that 12 must be eliminated from one cell. Rather, the uniqueness logic proves that, and that in turn reveals the partial subset. The potential partial subset does prove that you can't remove 12 from both cells, or else you'll have an invalid condition. On the other hand if you have a potential fractional subset, it does not prove that the 12 must be eliminated from both cells--and neither does the uniqueness logic, which says that's only one possibility. The partial fractional subset also does not prove that you can't eliminate 12 from only one cell--but if it could prove that, then the uniqueness test would reveal the fractional subset.

To put it in more straightforward logic terms:

A: 12 can be eliminated from only one floor cell
B: 12 can be eliminated from both floor cells
U: Uniqueness test
P: Partial subset exists
p: Partial subset may exist
F: Fractional subset exists
f: Fractional subset may exist

U->(A or B)
A<->!B, !A<->B
p,P->!B
p+A->P
f+B->F
F->!A

Further deductions:
U+p->A->P
U+f->(A or F)

Now note how that works. There is nothing to force B, so therefore you cannot force F.