The New Sudoku Players' Forum

[eleven]

Nice observation with the remote triples.

I have generated now 680 non equivalent 3-digit patterns in 6 boxes (10 cells: 31, 12: 38, 13: 290, 14: 159, 15: 102, 16: 10). This should be all, if i made no mistake.
I didn't see one more, which i would suspect to be as hard as the TH or the mentioned 15 cell pattern.

Added: i have copied a zip file to my old google drive: here (list). As patterns here (wait a bit, until it is shown). [Edit: updated link to patterns (10 cells were missing)]
Added: the latter link did not work anymore (?). I made a new copy 3digit6boxesAsPatterns.zip.

[ryokousha]

I'm still exploring the topic in various directions, maybe there will be a bigger update in the future.
Until then, some interesting things that came up on the way:

The trivalue oddagon / Thor's Hammer can, with help of extra constraints, be realized in rows, columns or even disjoint groups instead of boxes.
Here's a row version using both diagonals (Sudoku X):

Code: Select all

------------------------------
  .  .  X | X  .  . | X  .  .
  .  X  . | .  X  . | .  X  .
  .  .  . | .  .  . | .  .  .
------------------------------
  .  .  . | .  .  . | .  .  .
  .  .  . | .  .  . | .  .  .
  .  .  . | .  .  . | .  .  .
------------------------------
  .  .  . | .  .  . | .  .  .
  .  .  X | X  .  . | X  .  .
  X  .  . | .  X  . | .  .  X
------------------------------


This is an anti-knight version using 5 columns instead of the 4 boxes:

Code: Select all

------------------------------
  X  .  . | .  .  . | .  X  .
  .  .  . | X  .  X | .  .  .
  .  .  X | .  .  . | .  .  .
------------------------------
  .  .  X | .  .  . | .  .  .
  .  .  . | X  .  X | .  .  .
  X  .  . | .  .  . | .  X  .
------------------------------
  X  .  . | .  .  . | .  X  .
  .  .  . | .  .  X | .  .  .
  .  .  X | X  .  . | .  .  .
------------------------------


With diagonals or anti-knight, 3 row or column versions can be made. But these have an extra triangle and are therefore less complex to prove not 3-colorable.

This is a version with 4 triangles in disjoint groups, marked A,B,C,D for better visibility:

Code: Select all

------------------------------
  A  .  . | .  B  . | .  .  .
  .  .  D | .  .  . | .  C  .
  .  .  . | .  .  . | .  .  .
------------------------------
  .  B  . | .  .  . | A  .  .
  .  C  . | .  .  . | .  .  D
  .  .  . | .  .  . | .  .  .
------------------------------
  A  .  . | .  .  . | .  B  .
  .  .  D | .  C  . | .  .  .
  .  .  . | .  .  . | .  .  .
------------------------------


Aside from Thor's Hammer here is a - maybe - promising pattern that just came up yesterday:
(classic)

Code: Select all

------------------------------
  .  X  . | X  .  . | X  .  .
  X  .  . | .  .  . | .  .  .
  .  .  . | .  .  . | .  .  .
------------------------------
  X  .  . | .  X  . | X  .  .
  .  .  . | X  .  . | .  .  .
  .  .  . | .  .  . | .  .  .
------------------------------
  X  .  . | X  .  . | .  X  .
  .  .  . | .  .  . | X  .  .
  .  .  . | .  .  . | .  .  .
------------------------------


It is not completely trivial to prove, needing the use of graph symmetry or a bifurcation. Ultimately it relies on the combinatorial fact that any 3-coloring of a 6-cycle produces at least one opposing pair of edges with the same two colors. The 6-cycle in question being the single cells in b236478.

[ryokousha]

Two interesting new patterns appeared while toying around:

The first one I initially thought being in T&E(3), but marek showed on the CTC discord that it is likely not. The proof is still quite symmetric and interesting:

Code: Select all

------------------------------
  .  .  . | .  .  . | .  .  .
  .  .  . | .  .  . | .  .  .
  .  .  X | .  .  X | .  .  X
------------------------------
  .  .  X | .  .  . | X  .  .
  .  .  . | .  .  . | .  X  .
  .  .  . | .  .  . | .  .  X
------------------------------
  .  .  . | X  .  . | .  .  X
  .  .  X | .  X  . | .  X  .
  .  .  . | .  .  X | X  .  .
------------------------------

Hidden Text: Show

r8c3 has two possible arrangements in boxes 8 and 9 - either r9c6/r7c9 or r7c4/r9c7. The first one does not work as the value would be excluded from r3. The same argument can be made for r3c9, b6, b9 and c3 to show that r3c9 also goes in r9c7, so r8c3=r3c9. This quickly reveals a 9-loop bivalue oddagon.

(explanation thanks to marek and Youri on the discord)

The second pattern is interesting because it is - as far as I can tell - the first nontrivial example having a 3-chromatic subgraph induced by the occupied cells, but is 4-chromatic considering the whole sudoku graph.


"concerningly short sausage roll" [Edit: typo corrected]

Code: Select all

------------------------------
  .  X  . | X  .  . | X  .  .
  X  .  . | .  X  . | .  X  .
  .  .  . | .  .  . | .  .  .
------------------------------
  X  .  . | .  .  . | X  .  .
  .  X  . | .  .  . | .  X  .
  .  .  . | .  .  . | .  .  .
------------------------------
  X  .  . | X  .  . | .  X  .
  .  X  . | .  X  . | X  .  .
  .  .  . | .  .  . | .  .  .
------------------------------


Hidden Text: Show

We color the digit pairs in the boxes with three colors - think of assigning each missing digit to a color. B2 and b8 have opposite permutation parities which means they must be the same color. The same holds for b4 and b6. Considering the possible colorings of b1379, the b2/b8 color and the b4/b6 color must be the same. This assigns two different values to r6c6.

Marek gave an elegant explanation in more conventional terms on discord:

Hidden Text: Show

16 cells with 3 digits => at least one digit must appear in all six columns
Either that digit appears in r1c4, r8c5, r4c7, and r5c2 or in r7c4, r2c5, r4c1, and r5c8.
WLOG (diagonal symmetry) let it be 1 in r1c4, r8c5, r4c7, and r5c2.
x-wing 1r27 \ c18
x-wing 23r18 \ c27
1 takes one diagonal of its x-wing, the other is forced to contain twice the same digit, eliminating it from r7c4, r2c5, r4c1, and r5c8
The remaining digit must therefore take all four of them.
Both 1 and that digit are then forced into r6c6 in b5, ie. contra.

[denis_berthier]

.
The first pattern can be proven contradictory in T&E(3, BRT) but not in T&E(2, BRT).
The second pattern can't be proven contradictory in T&E(3, BRT).
Marek's proofs may prove that the patterns are contradictory; but they don't allow any conclusion about the T&E-depth necessary for the proof.

Do you have any real puzzle with any of these patterns?

[ryokousha]

Oh, interesting!

Not to do injustice to marek, he did not claim to have a proof the pattern is TE2 - it was just a suspicion. I myself have to recuse from the discussion due to lack of competence

I do not have working puzzles for the patterns yet. For the first one that should be possible, but I don't know if there's much hope for "sausage roll". I will let you know if there's any progress on that.

[denis_berthier]

.
Just in case you'd want check the T&E-depth necessary to prove that a k-digit pattern is contradictory, CSP-Rules allows to do this very easily. See section 6.24.2 of the Basic User Manual.
(I added this feature when eleven found a big bunch of 3-digit patterns and wanted a quick way to find those in T&E(3).)

[marek stefanik]

The first pattern can be proven contradictory in T&E(3, BRT) but not in T&E(2, BRT).

Interesting, I believed that my proof was in T&E(2, singles).
I must have misunderstood the definition. Can you explain where I go wrong?

Hidden Text: Show

Naked triples at the start are in T&E(2) (for any elimination, any candidate in the first cell leaves a single in the second cell and a contradiction in the third one).
Suppose 1r8c3.

Code: Select all

------------------------------
  .  .  . | .  .  . | .  .  .
  .  .  . | .  .  . | .  .  .
  .  .  X | .  .  X | .  .  X
------------------------------
  .  .  X | .  .  . | X  .  .
  .  .  . | .  .  . | .  X  .
  .  .  . | .  .  . | .  .  X
------------------------------
  .  .  . | X  .  . | .  .  X
  .  .  1 | .  X  . | .  X  .
  .  .  . | .  .  X | X  .  .
------------------------------

A contradiction can be reached in T&E(1):
biv-chain[2]: r3n1{c9 c6} – b8n1{r9c6 r7c4} ==> r7c9≠1
hidden-single-in-a-box ==> r9c7=1
whip[2]: c3n2{r3 r4} – c7n2{r4 .} ==> r3c9≠2
whip[2]: c3n3{r3 r4} – c7n3{r4 .} ==> r3c9≠3
naked-single ==> r3c9=1
biv-chain[8]: r3c6{n2 n3} – r9c6{n3 n2} – r8c5{n2 n3} – r8c8{n3 n2} – r7c9{n2 n3} – r6c9{n3 n2} – r4c7{n2 n3} – r4c3{n3 n2} ==> r3c3≠2
biv-chain[8]: r3c6{n3 n2} – r9c6{n2 n3} – r8c5{n3 n2} – r8c8{n2 n3} – r7c9{n3 n2} – r6c9{n2 n3} – r4c7{n3 n2} – r4c3{n2 n3} ==> r3c3≠3
no digit left in r3c3
Analogical proofs exist for 23r3c8.

AFAIK this is a proof in T&E(T&E(1)), which is how T&E(2) is defined. Where do I go wrong?

To add a new pattern, this one appears in the most recent puzzle in the tridagon thread:

Code: Select all

   +---------+---------+---------+
   | .  .  . | .  .  . | .  .  . |
   | .  .  . | .  .  . | .  .  . |
   | .  .  . | .  .  . | .  .  . |
   +---------+---------+---------+
   | .  X  . | .  X  . | X  .  . |
   | .  .  . | .  .  . | .  .  . |
   | .  .  . | .  .  . | .  .  . |
   +---------+---------+---------+
   | .  .  . | .  X  . | .  .  . |
   | .  X  . | .  X  . | X  .  . |
   | .  X  . | .  .  X | .  .  X |
   +---------+---------+---------+

Each of r4789 must have the same parity (each cell in r8 sees the corresponding cells in the other rows).
For a given parity, there are three possible permutations, therefore at least one must repeat.
That creates a contradiction, as each two rows have at least one pair of corresponding cells linked in a column.
(More traditionally, there is an oddagon on the digit in r8c7.)

Marek

[ryokousha]

.
Just in case you'd want check the T&E-depth necessary to prove that a k-digit pattern is contradictory, CSP-Rules allows to do this very easily. See section 6.24.2 of the Basic User Manual.
(I added this feature when eleven found a big bunch of 3-digit patterns and wanted a quick way to find those in T&E(3).)

I will have a look at CSP-rules!

For the time being, can we also grade conventional impossible puzzles?
For example this

Code: Select all

..4..5.3..1623....5.....2...23.....56.....4.2...12..6...............3.1......4...

is a 21 given "minimal impossible" based on (a morph of) the sausage roll pattern. So it may or may not be hard to prove contradictory. I'm not 100% sure.

(Also I could generate those in the thousands if necessary. But then I'd have to rate them myself, after getting a grasp of CSP-rules)

[denis_berthier]

The first pattern can be proven contradictory in T&E(3, BRT) but not in T&E(2, BRT).

Interesting, I believed that my proof was in T&E(2, singles).
I must have misunderstood the definition. Can you explain where I go wrong?

Ah, sorry; I used function "solve-k-digit-pattern-string" (which basically launches a simplified form of T&E), but I forgot it is only intended as a filter of patterns. Said otherwise, it can prove that a pattern is contradictory in some T&E(n), but it can't conclude anything in the other case.
By applying the full T&E(2) procedure, this pattern is provably contradictory in T&E(2).

About your proof, it is correct. However, I would make it simpler (using shorter chains):

Code: Select all

Resolution state after Triplets:
   +-------------------------------+-------------------------------+-------------------------------+
   ! 123456789 123456789 456789    ! 123456789 123456789 123456789 ! 123456789 123456789 456789    !
   ! 123456789 123456789 456789    ! 123456789 123456789 123456789 ! 123456789 123456789 456789    !
   ! 456789    456789    123       ! 456789    456789    123       ! 456789    456789    123       !
   +-------------------------------+-------------------------------+-------------------------------+
   ! 123456789 123456789 123       ! 123456789 123456789 123456789 ! 123       456789    456789    !
   ! 123456789 123456789 456789    ! 123456789 123456789 123456789 ! 456789    123       456789    !
   ! 123456789 123456789 456789    ! 123456789 123456789 123456789 ! 456789    456789    123       !
   +-------------------------------+-------------------------------+-------------------------------+
   ! 123456789 123456789 456789    ! 123       456789    456789    ! 456789    456789    123       !
   ! 456789    456789    123       ! 456789    123       456789    ! 456789    123       456789    !
   ! 123456789 123456789 456789    ! 456789    456789    123       ! 123       456789    456789    !
   +-------------------------------+-------------------------------+-------------------------------+

Level 1 of T&E: suppose r8c3=1

Code: Select all

(solve-sukaku-grid
   +-------------------------------+-------------------------------+-------------------------------+
   ! 123456789 123456789 456789    ! 123456789 123456789 123456789 ! 123456789 123456789 456789    !
   ! 123456789 123456789 456789    ! 123456789 123456789 123456789 ! 123456789 123456789 456789    !
   ! 456789    456789    123       ! 456789    456789    123       ! 456789    456789    123       !
   +-------------------------------+-------------------------------+-------------------------------+
   ! 123456789 123456789 123       ! 123456789 123456789 123456789 ! 123       456789    456789    !
   ! 123456789 123456789 456789    ! 123456789 123456789 123456789 ! 456789    123       456789    !
   ! 123456789 123456789 456789    ! 123456789 123456789 123456789 ! 456789    456789    123       !
   +-------------------------------+-------------------------------+-------------------------------+
   ! 123456789 123456789 456789    ! 123       456789    456789    ! 456789    456789    123       !
   ! 456789    456789    1         ! 456789    123       456789    ! 456789    123       456789    !
   ! 123456789 123456789 456789    ! 456789    456789    123       ! 123       456789    456789    !
   +-------------------------------+-------------------------------+-------------------------------+
)
biv-chain[2]: r3n1{c6 c9} - b9n1{r7c9 r9c7} ==> r9c6≠1
singles ==> r7c4=1, r9c7=1
biv-chain[2]: r3n1{c6 c9} - b6n1{r6c9 r5c8} ==> r5c6≠1
biv-chain[2]: r4c7{n3 n2} - r4c3{n2 n3} ==> r4c4≠3, r4c5≠3, r4c6≠3, r4c1≠3, r4c2≠3
biv-chain[2]: r4c3{n2 n3} - r4c7{n3 n2} ==> r4c1≠2, r4c2≠2, r4c4≠2, r4c5≠2, r4c6≠2
z-chain[2]: c3n2{r3 r4} - c7n2{r4 .} ==> r3c9≠2
biv-chain[2]: r8n2{c5 c8} - c9n2{r7 r6} ==> r6c5≠2
z-chain[2]: c3n3{r3 r4} - c7n3{r4 .} ==> r3c9≠3
singles ==> r3c9=1, r5c8=1
biv-chain[2]: r8n3{c5 c8} - c9n3{r7 r6} ==> r6c5≠3
biv-chain[2]: r3c6{n3 n2} - r9c6{n2 n3} ==> r1c6≠3, r2c6≠3, r5c6≠3, r6c6≠3
biv-chain[2]: r9c6{n2 n3} - r3c6{n3 n2} ==> r5c6≠2, r6c6≠2, r1c6≠2, r2c6≠2
biv-chain[4]: b8n3{r9c6 r8c5} - b9n3{r8c8 r7c9} - b6n3{r6c9 r4c7} - c3n3{r4 r3} ==> r3c6≠3
singles ==> r3c6=2, r3c3=3, r4c3=2, r4c7=3, r6c9=2, r7c9=3, r8c8=2
GRID 0 HAS NO SOLUTION : NO CANDIDATE FOR FOR BN-CELL b8n2


Then, by symmetry, the same is bound to work for hypotheses r8c3=2 and fr8c3=3.

[denis_berthier]

can we also grade conventional impossible puzzles?
For example this

Code: Select all

..4..5.3..1623....5.....2...23.....56.....4.2...12..6...............3.1......4...

By activating either T&E(1) or T&E(2) or ... in the configuration file, standard function solve will either find a solution or prove a contradiction (or conclude nothing).

Example:
1) Choose T&E(2), then type (solve "..4..5.3..1623....5.....2...23.....56.....4.2...12..6...............3.1......4...").
You'll get:GRID 0 HAS NO SOLUTION : NO CANDIDATE FOR RN-CELL r7n8

2) Choose T&E(1), then type (solve "..4..5.3..1623....5.....2...23.....56.....4.2...12..6...............3.1......4...").
You'll get:PUZZLE 0 IS NOT SOLVED. 48 VALUES MISSING

It means this puzzle requires T&E(2) to be proven contradictory.

Needless to say, this broad classification of contradictory puzzles can be refined in exactly the same way as well-formed puzzles.

(Also I could generate those in the thousands if necessary. But then I'd have to rate them myself, after getting a grasp of CSP-rules)

CSP-Rules has functions for dealing with files of puzzles. It can output the list of solved or contradictory puzzles.

[ryokousha]

We just realized the sausage roll pattern on the last page contained a typo (the pair in b7 was one step too far to the right). This is the correct one:

Code: Select all

------------------------------
  .  X  . | X  .  . | X  .  .
  X  .  . | .  X  . | .  X  .
  .  .  . | .  .  . | .  .  .
------------------------------
  X  .  . | .  .  . | X  .  .
  .  X  . | .  .  . | .  X  .
  .  .  . | .  .  . | .  .  .
------------------------------
  X  .  . | X  .  . | .  X  .
  .  X  . | .  X  . | X  .  .
  .  .  . | .  .  . | .  .  .
------------------------------

Denis, you probably corrected for that typo before checking?

[denis_berthier]

We just realized the sausage roll pattern on the last page contained a typo (the pair in b7 was one step too far to the right). This is the correct one:

Code: Select all

------------------------------
  .  X  . | X  .  . | X  .  .
  X  .  . | .  X  . | .  X  .
  .  .  . | .  .  . | .  .  .
------------------------------
  X  .  . | .  .  . | X  .  .
  .  X  . | .  .  . | .  X  .
  .  .  . | .  .  . | .  .  .
------------------------------
  X  .  . | X  .  . | .  X  .
  .  X  . | .  X  . | X  .  .
  .  .  . | .  .  . | .  .  .
------------------------------

Denis, you probably corrected for that typo before checking?

No, I hadn't corrected. This one is provably contradictory in T&E(2).

[marek stefanik]

About your proof, it is correct. However, I would make it simpler (using shorter chains):

Thank you for having a look at it. I knew that the pairs would allow for shorter chains, but decided for an option that required much less typing (as I wasn't trying to prove that the pattern was in B4B, just that it was in T&E(2)).

Marek

[eleven]

To add a new pattern ...

It's nr 5 in my list of 10 cell patterns here.

Code: Select all

 .  .  . |  .  .  . |  .  .  .
 .  .  . |  .  .  . |  .  .  .
 .  .  # |  .  .  # |  .  .  o
-------------------------------
 .  .  . |  .  .  . |  .  .  X
 .  .  o |  .  .  # |  .  .  X
 .  .  # |  .  #  . |  .  o  .


The digit in r6c8 must be in r3c9 and r5c3 too, leaving an oddagon for the other 2 digits in the #-ed cells.

[Added:] The pattern above is possible, isn't it ?

Code: Select all

------------------------------
  .  1  . | 2  .  . | 3  .  .
  2  .  . | .  3  . | .  1  .
  .  .  . | .  .  . | .  .  .
------------------------------
  3  .  . | .  .  . | 2  .  .
  .  2  . | .  .  . | .  3  .
  .  .  . | .  .  . | .  .  .
------------------------------
  1  .  . | 3  .  . | .  2  .
  .  3  . | .  2  . | 1  .  .
  .  .  . | .  .  . | .  .  .
------------------------------

[marek stefanik]

To add a new pattern ...

It's nr 5 in my list of 10 cell patterns here.

You're right, I should have checked those.

The pattern above is possible, isn't it ?

Technically it is, but you'll always force two digits in b5 into r6c6.

Marek