The New Sudoku Players' Forum

[Myth Jellies]

Mike Mepham's list of bifurcation candidates number 5 works out really nice for this technique. The initial puzzle is:

Code: Select all

0 0 0 7 0 0 3 0 0
0 6 0 0 0 0 5 7 0
0 7 3 8 0 0 4 1 0
0 0 9 2 8 0 0 0 0
5 0 0 0 0 0 0 0 9
0 0 0 0 9 3 6 0 0
0 9 8 0 0 7 1 5 0
0 5 4 0 0 0 0 6 0
0 0 1 0 0 9 0 0 0


Without performing anything fancy, such as xy-wings, this reduces to:

Code: Select all

 148  48   5    | 7    14   2    | 3    9    6     
 14   6    2    | 9    3    14   | 5    7    8     
 9    7    3    | 8    6    5    | 4    1    2   
----------------+----------------+----------------
 3    1    9    | 2    8    6    | 7    4    5   
 5   <28>  6    | 14   7    14   |<28>  3    9   
 48  <248> 7    | 5    9    3    | 6   <28>  1     
----------------+----------------+----------------
 26   9    8    | 346  24   7    | 1    5    34   
 27   5    4    | 13   12   8    | 9    6    37   
 76   3    1    | 46   5    9    |<28> <28>  47   


Noting the "28" that appears in cells r5c2, r6c2, r5c7, r6c8, r9c7, and r9c8; uniqueness requires that cell r6c2 = 4. Applying this and avoiding advanced methods again gets us to

Code: Select all

 14   8    5    | 7    14   2    | 3    9    6     
 14   6    2    | 9    3    14   | 5    7    8     
 9    7    3    | 8    6    5    | 4    1    2   
----------------+----------------+----------------
 3    1    9    | 2    8    6    | 7    4    5   
 5    2    6    | 14   7    14   | 8    3    9   
 8    4    7    | 5    9    3    | 6    2    1     
----------------+----------------+----------------
 26   9    8    |<346> 24   7    | 1    5    34   
 27   5    4    | 13   12   8    | 9    6    37   
 76   3    1    | 46   5    9    | 2    8    47   


At this point, only the 346 in cell r7c4 prevents every row and column from attaining their lowest two-candidate cell states. It is easy to observe that a 36 in that cell would transform row 7 and column 4 into irreducible non-unique binary naked quads. Since we have a unique solution, this cannot be, so cell r7c4=4 and the rest falls out quite simply.

This appears to be a very powerful and quick method for those puzzles that reduce down to a large set of two-candidate cells with a sprinkling of multi-candidate cells thrown in.

[Nick67]

Hi Myth Jellies,

Nice example!

At this point, only the 346 in cell r7c4 prevents every row and column from attaining their lowest two-candidate cell states. It is easy to observe that a 36 in that cell would transform row 7 and column 4 into irreducible non-unique binary naked quads. Since we have a unique solution, this cannot be, so cell r7c4=4 and the rest falls out quite simply.

I see that a 36 in r7c4 would result in irreducible naked quads in row 7
and column 4. Could you please explain further how that result would contradict
the fact that there is a unique solution? Thanks!

[Myth Jellies]

The postulate, which is based on Jeff's response to this thread, along with several people's contributions in the Uniqueness thread (notably tso and Lummox JR); is that if you reduce the unknown parts of a grid to two-candidate cells, and if all the boxes, rows, and columns form interlaced naked sets from which no further simple reductions are possible; then you have created an intermeshed setup that has multiple solutions. Since that result is untenable with a single solution puzzle, it can be eliminated as a possibility.

As far as I know, it is only a postulate with no formal proof at this time.

Personally, I would prefer something like the bivalue universal death/duplicity theory. Avoid BUD at all costs.

[rubylips]

Here's an alternative argument:

Code: Select all

Consider the cell r7c5.
When it contains the value 2, the value 6 in Row 7 must appear in the cell r7c1.
When it contains the value 4, the value 6 in Box 8 must appear in the cell r9c4.
Whichever value it contains, the cell r7c4 cannot contain the value 6.
- The move r7c4:=6 has been eliminated.
The cell r7c1 is the only candidate for the value 6 in Row 7.


[Lummox JR]

I don't think you can extend this beyond a postulate, MJ, because you can't prove the sets with the 36 would be irreducible. Other factors influence them and so it's entirely possible (nay, likely) that with the 36 you still have a single solution. A simple way to test that is to remove the 4 candidate and run it through a solver. If the solver says the grid is now invalid, then they may indeed have been irreducible. (Removing the candidate will not however tip your puzzle into multiple solutions. Only adding candidates can do that. Instead you will have voided the only solution.)

The reason the original uniqueness test works is that it eliminates the possibility of any other outside force constraining the digits within. Your crossing subsets don't do that. Hence, you can't prove nothing can reduce them.

[Myth Jellies]

Take a look at a slightly modified version of tso's contribution to the Uniqueness thread.

Code: Select all

  .  . 12  |  . 23  .  |  . 13  .
  .  .  .  |  .  .  .  |  .  .  .
  .  .  .  |  .  .  .  |  .  .  .
  ---------+-----------+---------
  .  . 12  |  . 23  .  |  . 13  .
  .  .  .  |  .  .  .  |  .  .  .
  .  .  .  |  .  .  .  |  .  .  .
  ---------+-----------+---------
  .  .  .  |  .  .  .  |  .  .  .
  .  .  .  |  .  .  .  |  .  .  .
  .  .  .  |  .  .  .  |  .  .  .


  .  . 12  |  . 23  .  |  . 13  .
  .  .  .  |  .  .  .  |  .  .  .
  .  .  .  |  .  .  .  |  .  .  .
  ---------+-----------+---------
  .  . 23  |  . 13  .  |  . 12  .
  .  .  .  |  .  .  .  |  .  .  .
  .  .  .  |  .  .  .  |  .  .  .
  ---------+-----------+---------
  .  . 13  |  . 12  .  |  . 23  .
  .  .  .  |  .  .  .  |  .  .  .
  .  .  .  |  .  .  .  |  .  .  .

You add a candidate X on any one of these cells, and uniqueness implies that that cell must be X. These multiple-solution things can grow into a ton of combinations which no one wants to enumerate. They do appear to have something in common, though. They look like bivalue naked sets which interlace nicely.

The following BUD form also consists of bivalue naked sets which interlace nicely

Code: Select all

 14   8    5    | 7    14   2    | 3    9    6     
 14   6    2    | 9    3    14   | 5    7    8     
 9    7    3    | 8    6    5    | 4    1    2   
----------------+----------------+----------------
 3    1    9    | 2    8    6    | 7    4    5   
 5    2    6    | 14   7    14   | 8    3    9   
 8    4    7    | 5    9    3    | 6    2    1     
----------------+----------------+----------------
 26   9    8    |<36>  24   7    | 1    5    34   
 27   5    4    | 13   12   8    | 9    6    37   
 76   3    1    | 46   5    9    | 2    8    47   


Thus we can postulate that if this setup had no conflicts, it would have multiple solutions. Since we know the puzzle only has one solution and this setup covers the entire unknown part of the puzzle, we also know that this setup must lead to a conflict. Thus if one of these cells allowed for another candidate (say a 4 in r7c4), we can assume that option is valid just like other uniqueness forms.

Think of BUD as just another multi-solution setup to be avoided.

Of course if anyone can find a nicely interlaced BUD setup that does reduce to a single solution, then that would demand a revision of the postulate.

[Nick67]

Take a look at a slightly modified version of tso's contribution to the Uniqueness thread.

Code: Select all


  .  . 12  |  . 23  .  |  . 13  .
  .  .  .  |  .  .  .  |  .  .  .
  .  .  .  |  .  .  .  |  .  .  .
  ---------+-----------+---------
  .  . 12  |  . 23  .  |  . 13  .
  .  .  .  |  .  .  .  |  .  .  .
  .  .  .  |  .  .  .  |  .  .  .
  ---------+-----------+---------
  .  .  .  |  .  .  .  |  .  .  .
  .  .  .  |  .  .  .  |  .  .  .
  .  .  .  |  .  .  .  |  .  .  .


  .  . 12  |  . 23  .  |  . 13  .
  .  .  .  |  .  .  .  |  .  .  .
  .  .  .  |  .  .  .  |  .  .  .
  ---------+-----------+---------
  .  . 23  |  . 13  .  |  . 12  .
  .  .  .  |  .  .  .  |  .  .  .
  .  .  .  |  .  .  .  |  .  .  .
  ---------+-----------+---------
  .  . 13  |  . 12  .  |  . 23  .
  .  .  .  |  .  .  .  |  .  .  .
  .  .  .  |  .  .  .  |  .  .  .



You add a candidate X on any one of these cells, and uniqueness implies that that cell must be X.

I'm not sure that this is true. I say this because, for both of these
patterns, there is just one pattern cell per box. So you can't make the
usual argument that, given one solution to one of the above puzzles,
you could swap values, and come up with a second solution.
(If you start with one solution, and move a number out of a box, and
move a different number into the same box ... the result is not
a new solution.) So, for these 2 puzzles ... I'm not sure that you
can use the uniqueness logic to eliminate candidates.

I'm also not sure if this observation affects your overall argument.
You seem to be on to something ... I hope it works out.

[Myth Jellies]

Code: Select all

  .  .  .  |  .  .  .  |  .  .  .
  .  12 23 |  34 41 .  |  .  .  .
  .  34 41 |  12 23 .  |  .  .  .
  ---------+-----------+---------
  .  23 34 |  41 12 .  |  .  .  .
  .  41 12 |  23 34 .  |  .  .  .
  .  .  .  |  .  .  .  |  .  .  .
  ---------+-----------+---------
  .  .  .  |  .  .  .  |  .  .  .
  .  .  .  |  .  .  .  |  .  .  .
  .  .  .  |  .  .  .  |  .  .  .


Here is a simple one using interleaved quads. You can easily see that two possible solutions are possible, one using the first number of the cell pair, and one using the second number of the cell pair.

[Lummox JR]

I think I missed tso's post and its significance when her first posted it. It's definitely not a uniqueness pattern because it's too sparse. The number of boxes exceeds the number of digits, columns, and rows. All three should be equal.

The example you just posted, MJ, is indeed a uniqueness pattern because it's recognizable as a 4x4. It has four digits, four columns, four rows, four boxes. However this is unrelated to the puzzle you posted, which matches no uniqueness pattern except the loop you found with the 28's.

[Nick67]

Yes, thank you for this. Nice pattern (assuming
this candidate configuration is possible).

I didn't mean to sidetrack you ... I hope you
continue to find good results.

[r.e.s.]

Take a look at a slightly modified version of tso's contribution to the Uniqueness thread.

Code: Select all

  .  . 12  |  . 23  .  |  . 13  .
  .  .  .  |  .  .  .  |  .  .  .
  .  .  .  |  .  .  .  |  .  .  .
  ---------+-----------+---------
  .  . 12  |  . 23  .  |  . 13  .
  .  .  .  |  .  .  .  |  .  .  .
  .  .  .  |  .  .  .  |  .  .  .
  ---------+-----------+---------
  .  .  .  |  .  .  .  |  .  .  .
  .  .  .  |  .  .  .  |  .  .  .
  .  .  .  |  .  .  .  |  .  .  .

You add a candidate X on any one of these cells, and uniqueness implies that that cell must be X.

That doesn't seem to be true. Here's a counter-example I cooked up:

Code: Select all

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

with the following candidate grid:

Code: Select all

  6    8   <12>  | 7   <23>  5    | 9   <134> 24   
  3    2    9    | 6    4    1    | 5    8    27   
  4    7    5    | 9    8    3    | 123  6    2   
 ----------------+----------------+--------------
  7    9   <12>  | 4   <23>  6    | 8   <13>  5   
  8    12   4    | 2    5    9    | 13   7    6   
  5    3    6    | 8    1    7    | 4    2    9   
 ----------------+----------------+--------------
  2    4    7    | 3    9    8    | 6    5    1   
  1    6    3    | 5    7    4    | 2    9    8   
  9    5    8    | 1    6    2    | 7    4    3   


This puzzle has a unique solution, and the <134> cell reduces to 3 (not 4).

[Myth Jellies]

Nick67,

Doh! I see what you are saying about applying uniqueness to tso's patterns. Reduced to their most basic, you put 12's in four different boxes in a rectangular pattern. I think we have shown that that is insufficient for applying uniqueness.

Now on the other hand, perhaps if you had these...

Code: Select all

  .  . 12  |  . 23  .  |  . 31  .
  . 21  .  | 32  .  .  | 13  .  .
  .  .  .  |  .  .  .  |  .  .  .
  ---------+-----------+---------
  .  . 21  |  . 32  .  |  . 13  .
  . 12  .  | 23  .  .  | 31  .  .
  .  .  .  |  .  .  .  |  .  .  .
  ---------+-----------+---------
  .  .  .  |  .  .  .  |  .  .  .
  .  .  .  |  .  .  .  |  .  .  .
  .  .  .  |  .  .  .  |  .  .  .


  .  . 12  |  . 23  .  |  . 31  .
  . 21  .  | 32  .  .  | 13  .  .
  .  .  .  |  .  .  .  |  .  .  .
  ---------+-----------+---------
  .  . 23  |  . 31  .  |  . 12  .
  . 32  .  | 13  .  .  | 21  .  .
  .  .  .  |  .  .  .  |  .  .  .
  ---------+-----------+---------
  .  . 31  |  . 12  .  |  . 23  .
  . 13  .  | 21  .  .  | 32  .  .
  .  .  .  |  .  .  .  |  .  .  .


Fortunately, tso's post served as more an example of how intermeshed naked sets result in a consistant structures that allow multiple solutions. Whether or not they could be used as uniqueness patterns on their own is a moot point.

[Myth Jellies]

r.e.s.

You got your post in while I was composing an answer to Nick. Your grid may show that tso's patterns do not qualify as uniqueness patterns, which I would agree with. Your grid does not qualify for the BUD test because all of the unknowns in the rows, columns, and boxes do not form bivalue naked sets. Specifically, you cannot have a house that has a single bivalued cell. Note that a house may contain multiple naked sets, so long as they have been reduced (no digits in common).

[Myth Jellies]

Lummox JR

...this is unrelated to the puzzle you posted, which matches no uniqueness pattern except the loop you found with the 28's.

There is no way it could match any known uniqueness pattern, because it must contain an internal conflict.

BUD patterns follow the postulated rules for possessing multiple solutions.

If it did not contain an internal conflict, then the puzzle's BUD pattern would be valid which would result in multiple solutions for the puzzle.

Uniqueness patterns follow the postulated rules for possessing multiple solutions. If a BUD pattern was also a recognized uniqueness pattern, then the puzzle would have multiple solutions, because we know that uniqueness patterns contain no internal conflicts.

[Nick67]

Now on the other hand, perhaps if you had these...

Code: Select all


  .  . 12  |  . 23  .  |  . 31  .
  . 21  .  | 32  .  .  | 13  .  .
  .  .  .  |  .  .  .  |  .  .  .
  ---------+-----------+---------
  .  . 21  |  . 32  .  |  . 13  .
  . 12  .  | 23  .  .  | 31  .  .
  .  .  .  |  .  .  .  |  .  .  .
  ---------+-----------+---------
  .  .  .  |  .  .  .  |  .  .  .
  .  .  .  |  .  .  .  |  .  .  .
  .  .  .  |  .  .  .  |  .  .  .


  .  . 12  |  . 23  .  |  . 31  .
  . 21  .  | 32  .  .  | 13  .  .
  .  .  .  |  .  .  .  |  .  .  .
  ---------+-----------+---------
  .  . 23  |  . 31  .  |  . 12  .
  . 32  .  | 13  .  .  | 21  .  .
  .  .  .  |  .  .  .  |  .  .  .
  ---------+-----------+---------
  .  . 31  |  . 12  .  |  . 23  .
  . 13  .  | 21  .  .  | 32  .  .
  .  .  .  |  .  .  .  |  .  .  .


These are great! The 2nd example is maybe the most elaborate
"uniqueness pattern" proposed so far? (A tip of the hat to tso, too,
for inspiring these examples.)
(As an aside, I wonder if these patterns can occur? Could we
place some numbers as final values into a puzzle,
such that the puzzle actually has one of the above candidate configurations?
But .... that is a side topic, and I'd like to let you steer
this thread back to BUD.)