The New Sudoku Players' Forum

[jovi_al01]

This topic might already exist, and if it does, I apologize.

I stumbled into a 60-cell 2-solution BUG a few months ago:

Code: Select all

.------------.------------.------------.
| 59  68  47 | 38  36  47 | 59  1   2  |
| 67  59  28 | 16  17  28 | 59  3   4  |
| 34  23  1  | 29  49  5  | 78  78  6  |
:------------+------------+------------:
| 49  29  5  | 38  37  6  | 1   24  78 |
| 16  7   34 | 15  2   89 | 46  89  35 |
| 8   16  23 | 4   15  79 | 26  79  35 |
:------------+------------+------------:
| 57  58  6  | 29  49  1  | 3   24  78 |
| 13  4   79 | 56  8   23 | 27  56  19 |
| 2   13  89 | 7   56  34 | 48  56  19 |
'------------'------------'------------'

and was curious as to if any larger were possible.

Today, I found a 62-cell 2-solution BUG and thought it would be nice to share here:

Code: Select all

.------------.------------.------------.
| 89  23  56 | 17  37  69 | 48  12  45 |
| 56  79  1  | 46  48  2  | 58  79  3  |
| 23  4   78 | 13  5   89 | 27  6   19 |
:------------+------------+------------:
| 17  13  46 | 89  27  58 | 49  23  56 |
| 68  89  2  | 59  14  3  | 56  14  7  |
| 37  5   49 | 27  6   14 | 23  8   19 |
:------------+------------+------------:
| 49  27  59 | 48  23  56 | 1   37  68 |
| 45  18  3  | 56  18  7  | 69  49  2  |
| 12  6   78 | 23  9   14 | 37  5   48 |
'------------'------------'------------'

I am curious as to if any larger could possibly exist

[Serg]

Hi, jovi_al01!
The entities you found are called strongly minimal unavoidable sets with valency 2 of order 60 (U60) and 62 (U62). See the thread Minimal Unavoidable Set with 49 permutations. It was Ocean who discovered another large U60 UA set in 2006 (see his post in the thread Greatest divergance possible in dual solution puzzle?). It seems the record belongs to Mladen Dobrichev. He found U62 UA set (i.e. UA set consisting from 62 cells).

Serg

[Hajime]

I created this Sukaku/Sudoku with 81 bivalue cells.
I think it has an unique solution. Please verify.
Is this a 2-solution BUG ??

Code: Select all

+----------+----------+----------+
| 13 23 19 | 34 89 56 | 45 67 78 |
| 56 67 78 | 45 19 23 | 89 12 34 |
| 89 45 34 | 67 78 12 | 19 56 23 |
+----------+----------+----------+
| 19 34 12 | 89 67 78 | 56 23 45 |
| 45 56 67 | 23 12 34 | 78 19 89 |
| 23 78 89 | 56 45 19 | 12 34 67 |
+----------+----------+----------+
| 34 19 56 | 78 23 89 | 67 45 12 |
| 67 89 23 | 12 56 45 | 34 78 19 |
| 78 12 45 | 19 34 67 | 23 89 56 |
+----------+----------+----------+
In 729 char line:
13.......23.......91.......34.......89.......56.......45.......67.......78.......56.......67.......78.......45.......91.......23.......89.......12.......34.......89.......45.......34.......67.......78.......12.......91.......56.......23.......91.......34.......12.......89.......67.......78.......56.......23.......45.......45.......56.......67.......23.......12.......34.......78.......91.......89.......23.......78.......89.......56.......45.......91.......12.......34.......67.......34.......91.......56.......78.......23.......89.......67.......45.......12.......67.......89.......23.......12.......56.......45.......34.......78.......91.......78.......12.......45.......91.......34.......67.......23.......89.......56.......


[Serg]

Hi, Hajime!

I created this Sukaku/Sudoku with 81 bivalue cells.
I think it has an unique solution. Please verify.
Is this a 2-solution BUG ??

Code: Select all

+----------+----------+----------+
| 13 23 19 | 34 89 56 | 45 67 78 |
| 56 67 78 | 45 19 23 | 89 12 34 |
| 89 45 34 | 67 78 12 | 19 56 23 |
+----------+----------+----------+
| 19 34 12 | 89 67 78 | 56 23 45 |
| 45 56 67 | 23 12 34 | 78 19 89 |
| 23 78 89 | 56 45 19 | 12 34 67 |
+----------+----------+----------+
| 34 19 56 | 78 23 89 | 67 45 12 |
| 67 89 23 | 12 56 45 | 34 78 19 |
| 78 12 45 | 19 34 67 | 23 89 56 |
+----------+----------+----------+
In 729 char line:
13.......23.......91.......34.......89.......56.......45.......67.......78.......56.......67.......78.......45.......91.......23.......89.......12.......34.......89.......45.......34.......67.......78.......12.......91.......56.......23.......91.......34.......12.......89.......67.......78.......56.......23.......45.......45.......56.......67.......23.......12.......34.......78.......91.......89.......23.......78.......89.......56.......45.......91.......12.......34.......67.......34.......91.......56.......78.......23.......89.......67.......45.......12.......67.......89.......23.......12.......56.......45.......34.......78.......91.......78.......12.......45.......91.......34.......67.......23.......89.......56.......


At least, box B1 of your example isn't correct. r1c1 contains bivalue 1/3, but r1c2 contains bivalue 2/3. Hence location of digit "3" in the box B1 is limited to cells r1c1 and r1c2 in all cases. But r3c3 contains 3/4. Contradiction.

Serg

[Hajime]

The 3 must go in r3c3.
This is the only possible solution (I think):

Code: Select all

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


But you hit the weak spot. the construction of r1c1 is different than all others.

What I did:
- start with any full solved puzzle (here above), with r1c1=1 deliberate
- all clues become (left) candidates
- add an extra candidate (right) with value (left_candidate + 1); so 4 becomes 45 and 7 becomes 78 and 9 becomes 91 (wrap).
- the puzzle has now 2 solutions: the left candidates and the right candidates.
- disable the right candidate group by putting the clue "1" to r1c1; now we have 1 clue-cell and 80 bi-value cells
- the left and right candidates groups can not be mingled (maybe later some proof with induction)
- keep right candidate group disabled by putting 13 into r1c1

Now the conclusion/question: Is this method valid

The puzzle solves with "singles only" starting with r1c2=2 because it is the only single 2 in row 1 or box 1.
And all houses have exactly 2 candidates of each value (except the 3 for r1c1), so the next hidden single is easily found.

[mith]

Yeah, these shouldn't be hard to make with some algorithm like you're suggesting. Or even just combining two arbitrary disjoint solution grids, as long as you avoid creating any loops smaller than 81 cells.

Here's an example of an 81-cell BUG made in a completely different way: https://f-puzzles.com/?id=y93w9q9e

This is from the two solutions to a nonconsecutive killer sudoku:

Code: Select all

+-------+-------+-------+
| . . . | A A . | . . . |
| . . B | B . C | C . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| D . . | . . . | . . E |
| D . . | . . . | . . E |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . F | F . G | G . . |
| . . . | . H H | . . . |
+-------+-------+-------+
...AA......BB.CC...........D.......ED.......E....................FF.GG......HH...  nonconsecutive
A = 9; B = 11; C = 9; D = 8; E = 7; F = 9; G = 10; H = 9

[coloin]

Hmmmm
I guess if there was a 64C UA it would have to come from an 18C puzzle …
I don’t think many have looked specifically for it

[Serg]

Hi, mith!
Thank you for interesting example! It turns out, 81-cell BUGs do exist. Here it is (copied from the site https://f-puzzles.com/?id=y93w9q9e).

Code: Select all

23 59 57  13 68 46  79 12 48
49 26 34  78 15 37  26 89 15
67 18 18  45 29 29  34 56 37

13 67 18  29 29 45  78 34 56
57 23 59  68 46 18  34 79 12
48 49 26  15 37 37  15 26 89

12 78 49  37 13 56  89 45 26
56 13 37  26 45 89  12 78 49
89 45 26  49 78 12  56 13 37

I checked manually - 2/3 digit choice in r1c1 really produces 2 solutions:

Code: Select all

The first solution

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

The second solution

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

Solutions are essentially different grids with repeating triples of digits in minirows/minicolumns of each band/stack. It is minimal, i.e. it doesn't contain smaller BUG loops. I think that it is not easy to construct such an example, although I am sure that there exist many similar examples.

But this 81-cell BUG isn't 81-cell UA set. It is artificially created, and cannot be encountered when solving a Sudoku puzzle. So, when we are speaking about any BUG, the right answer is "81-cell BUG is the largest". But if we are speaking about BUGs which can be found in Sudoku puzzles, the right answer will be "62-cell BUG is largest at the moment", I think.

Serg

[Edited. I came to the conclusion that this 81-cell BUG is minimal.]

[mith]

Yes, for classic sudoku, 62 is the best known currently (and 64 is the theoretical max, though I'd be very surprised if that existed).

[Sojourner9]

Hi Hijime,

I know it has been almost two years since you asked the question so you have likely understand why this doesn't work and have moved on the many other things.

What you describe is just a relabeling of the symbols on the same grid using the cycle (1 2 3 4 5 6 7 8 9). This is the same grid either way.

Looking at a two choice puzzle example given by Serg there are two circuits/cycles in B1, (2 6 7 5 9 4 3) (1 8). Either or both could be reversed.
If I pick 2 for r1c1 it forced 4 into r2c. Then if I pick 8 for r3c2 it forces an 8 in r4c3 which forces 4 in r6c1 which is a conflict.
So instead I reverse (1 8) and pick 1 for r3c2 and the rest of the puzzle just falls out by elimination.

It might have been better, after setting the first cycle in B1, to solve column 1 which would then fix the second cycle in B1.
Column 1 has (1 2 3)(4 8 9)(5 6 7) as its S9 permutation.
If i reverse the first cycle in B1 and then fill in column 1, I see that the second cycle in B1 is reversed and the rest falls out by elimination.
I think there is a deep truth in both cycles reversing. Otherwise some cells would be the same between both solutions.

If you did like you said and shifted each symbol by 1 and displayed that way, without putting the two symbols in numeric order,
then the first column would be one solution and the second column would be the second solution to the same grid.

The same thing could be done on the puzzle presented by Serg.
Pick the first solution and reverse pairs that have wrong symbol in the first column and when you are done the second solution is in the second column.
proving that no symbols is the same in the same cell in both solution.

I haven't tried starting with another box.

It was fun solving the Sudoku in the GUI Serg linked to is had all the elimination work without much Sudoku solving.

Regards,

Wade

[Hajime]

I know it has been almost two years since you asked the question so you have likely understand why this doesn't work and have moved on the many other things.

Thank you. Indeed, completely forgotten about this.