The New Sudoku Players' Forum

[mith]

The trivalue oddagon pattern is receiving a lot of attention at the moment, and as discussed in the hard puzzle thread there have been other patterns discussed which are related in the sense of requiring at least 4 distinct digits present (that is, they form graphs which are not 3-colorable).

The following posts will discuss some known patterns in this category, and some approaches to proving their status. Feel free to suggest your own and discuss alternate proofs or uses in puzzles.

[mith]

Trivalue Oddagon (aka tridagon)

Code: Select all

. . * | * . .
. * . | . * .
* . . | . . *
------+------
* . . | * . .
. * . | . * .
. . * | . . *
The "Thor's Hammer" form; the starred cells cannot all be from the same three digits.

Like all patterns discussed here, the specific shape of the pattern is subject to morphing, but the following conditions hold for the pattern to be impossible:

1. Four boxes, appearing in two bands and two stacks
2. In each box, the pattern cells span the rows and columns of the box.
3. The diagonal parity of the pattern cells in the boxes have an odd split (3/1 diagonal/anti-diagonal or vice versa) - equivalently, the pattern cells form exactly one rectangle of cells (the center cells in the illustrated example), with the other cells forming an 8-cell loop.

To apply as a technique, the guardian cells must be considered - in the simplest case, there is exactly one cell of the pattern which can contain a digit outside the triple, and therefore the three digits are eliminated from that cell. With more guardians, links may be established to result in other deductions (such as virtual pairs/triples in a common row or column).

This pattern can be extended to larger loops (with an even number of boxes) - however, for 9x9 sudoku, a 6-box pattern is believed to always collapse to a 4-box pattern or something even simpler.

See Denis's thread for further discussion.

This pattern was first pointed out as appearing in many high clue count minimals I started finding in mid-2021 which were beginning to break through long held records for SER per clue count. marek stefanik's post, with some outlines of proofs for the impossibility discussed.

An elegant proof via "parity flow" is due to ryokousha of the CTC fan discord, and is discussed in detail here by rangsk (David Clamage) as a follow-up to our discussion of the pattern in the previous episode.

[mith]

Patto Patto

Code: Select all

* . . | * . . | * . .
. . . | . . . | . . .
. . . | . . . | . . *
------+-------+------
. . . | . . . | . . .
. . . | . . . | . . .
* . . | * . . | . . *
------+-------+------
. . . | . . . | . . .
. . . | . . . | . . .
* . . | * . . | . . *

This is a pattern appearing in the puzzle Patto Patto by shye, with the impossibility of 3-coloring mentioned by marek stefanik in the first reply to that thread.

[mith]

"Fryer's Ring of Doom"

Code: Select all

* . . | . * . | * . .
. * . | . . . | . * .
. . * | . . . | . . *
------+-------+------
. . . | . . . | . . .
. . * | . * . | . . *
. . . | . . . | . . .
------+-------+------
* . . | . * . | * . .
. * . | . . . | . * .
. . * | . . . | . . *

This is in some ways an extension of the trivalue oddagon pattern to cases where the diagonal parity of the four boxes has an even split (4/0, 2/2, 0/4). Here, each band and stack also has a row and column with three cells in the pattern, such that the minimum of five additional cells is used. This was first discussed by Fryer of the CTC fan discord (and illustrated in that original form), and named by ryokousha after a fully symmetric morph.

Relaxing the band/stack requirement for where the additional five cells appear can result in other similar patterns, as discussed by xzccs here.

[impossibility argument to be added]

[mith]

Unnamed 10-cell Pattern

Code: Select all

* * . | . * .
* . . | . . *
. . . | . . *
------+------
. . . | . . .
* . . | . . .
. * * | . . *

This is a smaller example offered by ryokousha. Logically, this can be reduced to simple chain deductions:

Assume all cells in the pattern are from three digits. Then whatever digit is in r6c6 must be in r1c5 and r5c1, and cannot appear in b1. #

[mith]

"Space Invaders"

Code: Select all

. . * | . . . | * . .
. . * | . * . | * . .
. * . | . . . | . * .
------+-------+------
. . . | . . . | . . .
. * . | . * . | . * .
. . . | . . . | . . .
------+-------+------
. * . | . * . | . * .
. . . | . . . | . . .
. . . | . . . | . . .

Another offered by ryokousha, and named after the shape reminding him of the aliens from Space Invaders.

WLOG, let the cells in r5 be 123 and the cells in r7 be 231. Then r3c2 is 3, r2c5 is 1, and r3c8 is 2. In b1, r2c3 is 2 and so r1c3 is 1; but in b3, r2c7 is 3, so r1c7 is 1. #

[mith]

I will note that the original proof I offered for the "trivalue oddagon" pattern's impossibility explicitly uses bivalue oddagons.

Code: Select all

. . * | * . .
. * . | . * .
* . . | . . *
------+------
* . . | * . .
. * . | . * .
. . * | . . *

Note that in each box, we can pick two cells which are part of the 8-loop (not part of the rectangle r25c25) of row/column links. WLOG, let's choose the cells in b5 (r4c4, r6c6) and say these are 2 and 3 in that order, with 1 in the other cell (r5c5). Note that in all cases, the two cells chosen form a 5-cell oddagon by picking one cell from each of the other three boxes (this is an inherent property of the 8-loop; we are just choosing three cells between the two sharing a box, in either direction of the loop) - for example, r1c3, r1c4, r6c3.

Since we have 23 in two cells, at least one of the other cells must contain a 1 (or we have a broken bivalue oddagon).

Code: Select all

. . 1 | 3 . .
. * . | . 2 .
* . . | . . *
------+------
* . . | 2 . .
. 3 . | . 1 .
. . 2 | . . 3

In the first case (the cell in the opposite box from the 23 pair, in this case r1c3), we immediately get a 23 remote pair in the other cells of the oddagon, in turn giving a 23 remote pair in the b24 cells of the rectangle, and now r2c2 sees all three digits.

Code: Select all

. . * | 1 . .
. * . | . 3 .
* . . | . . 2
------+------
* . . | 2 . .
. * . | . 1 .
. . * | . . 3

The other cases are messier, but we can focus on the rectangle to get through: one of the rectangle cells (r25c2) is 2. However, whichever it is results in an oddagon through the other. For example, if r2c2 is 2, we have the following loop of cells all forced to be from 13: r5c2 - r5c5 - r2c5 - r1c4 - r1c3 - r3c1 - r4c1 - r5c2.

The other link to oddagons is in the parity flow proof - an odd number of parity changes in the loop is broken.

All that said, I would argue there are as clear if not clearer analogues to the bivalue oddagon in some of the other patterns. Patto Patto's pattern is essentially a 5-cell bivalue oddagon expanded in each row and column to cover a third cell. The other 10-cell pattern is perhaps best explained as a "Broken Wing" (single-digit oddagon) on each digit, with an odd number of links (b124, r16, c16).

We can also think of bivalue oddagons themselves as simple examples of non-2-colorable graphs. In some sense, all of these patterns are analogues to the bivalue or bilocal oddagons, generalized to trivalue cells. (I would say this is similar to how an X-Wing/2-fish is a continuous nice loop, but its extension the Swordfish/3-fish is not any type of AIC, because of the reliance on binary propositions. Perhaps some sort of trinary links are necessary to relate these things to existing patterns.)

[denis_berthier]

.
Good idea to create this thread.
However, the name doesn't fit. Any pattern is chromatic. The thread should be something like non-3-chromatic patterns or 4+chromatic patterns or high chromatic patterns.

[denis_berthier]

.
Some exercise for flexing one's chromatic muscles before dealing with very complex patterns.
What's the chromatic number of a complete Naked-Quad (i.e. all 4 digits present in all 4 places)?

[mith]

.
Good idea to create this thread.
However, the name doesn't fit. Any pattern is chromatic. The thread should be something like non-3-chromatic patterns or 4+chromatic patterns or high chromatic patterns.

Any pattern is chromatic, yes. The name is something of a shorthand for “patterns with chromatic number greater than the lower bound trivially given by the number of cells in any single house” or something along those lines. Open to suggestions.

Not specifying a chromatic number in the name is a deliberate choice though - as mentioned, things like bivalue oddagons are examples of having chromatic number 3, and such patterns also exist for non-trivial chromatic number 5 (ryokousha mentions an extension of the idea in the unnamed 10-cell which is 5-colorable with at most 4 cells per house).

Whether such a pattern exists which provides eliminations not obtainable by much simpler sudoku techniques (and this needs to be defined) is an open question.

[mith]

ryokousha gave a reminder earlier that graph theoretical colorability and sudoku colorability are not the same, with a simple example: r1c123+r2c456+r456c8+r789c9 is not 3-colorable in sudoku, but is as a graph. Obviously in this case the pattern is trivially extended (r1c123+r2c456 in => r3c789 in) to a non-3-colorable graph, but it's an open question whether that is always the case (depending on what extensions are allowed).

Unrelated, here's another interesting pattern which is not 3-colorable:

Broken Windmill

Code: Select all

. * . | * . . | . . *
* . . | * . . | . * .
. . . | . . . | . . .
------+-------+------
. . . | . . . | . * *
. . . | . . . | . . .
* * . | . . . | . . .
------+-------+------
. . . | . . . | . . .
* . . | . . * | . . *
. * . | . . * | . * .

In b1379, the only cell for the third digit of the triple are the interior corners (r37c37), due to the triples in r1289 and c1289. But now we have a trivalue oddagon in b1379. #

[edit]An interesting thing about this pattern is that it also works with a 16x16 grid, so long as the cells in edge boxes appear in pairs in the same box. While the third digit in each corner box has flexibility in where it can appear - and in fact these cells don't even need to see each other - it remains the case that the band/stack parity must be preserved. Say b1 is 1-2-3 from left to right: the only way to reverse this parity in b13 without an immediate conflict in the corners is 2-1-3, but then the cells in b5/9 must both be 3, so the parity argument still holds to prove the pattern has chromatic number 4.

Unnamed Chromatic Number 5 Example

Code: Select all

. * * | . * *
* . . | . . *
* . . | . . *
------+------
. . . | . . .
* . . | . . .
* * * | . . *

(Proof is identical to the unnamed 10-cell above - r6c6 is in r1c5 and r5c1 and ruled out of b1.)

[mith]

As for naming, perhaps "pattern" is the real issue. Really, we are talking about a general class of resolution rules - eliminations, links, etc. - imposed by the (sudoku) chromatic number of a particular set of cells. (This of course still encompasses trivial examples like naked tuples where the eliminations are - in this context - due to being unable to add any other cell in the house to the pattern without increasing the trivial chromatic number of the tuple.)

[eleven]

This pattern can be extended to larger loops (with an even number of boxes) - however, for 9x9 sudoku, a 6-box pattern is believed to always collapse to a 4-box pattern or something even simpler.

Since this pattern (and all with exactly one 6-cycle) does not have a solution, it also cannot have one, if there are 2 or more givens of the digits in the empty boxes.

Code: Select all

.   .   123 | .   .   123 | .   .   . 
.   123 .   | .   123 .   | .   .   .
123 .   .   | 123 .   .   | .   .   .
------------+-------------+-----------
.   .   123 | .   .   .   | .   .   123
.   123 .   | .   .   .   | .   123  .
123 .   .   | .   .   .   | 123 .   .
------------+-------------+-----------
.   .   .   | .   .   123 | 123 .   .
.   .   .   | .   123 .   | .   123 .
.   .   .   | 123 .   .   | .   .   123

E.g. also this must be impossible:

Code: Select all

.   .   123 | .   .   123 | .   .   . 
.   123 .   | .   13  .   | .   .   .
123 .   .   | 23  .   .   | .   .   .
------------+-------------+-----------
.   .   123 | .   .   .   | .   .   123
.   23  .   | 1   .   .   | .   23  .
13  .   .   | .   2   .   | 13  .   .
------------+-------------+-----------
.   .   .   | .   .   123 | 123 .   .
.   .   .   | .   13  .   | .   123 .
.   .   .   | 23  .   .   | .   .   123

[denis_berthier]

.
I liked the idea of this thread.
Apart from the trivalue odddagon ones, do we have any "hardest" puzzle related to the other patterns?

[mith]

Not that I'm aware of, though I haven't really done a dedicated search. If there is a reason we're seeing so much of the trivalue oddagon other than the obvious neighborhood bias, I suspect it's due to how contained the pattern is (only in four boxes) or how few triples it requires (again the four boxes, compared to the 3 rows/3 columns of Patto Patto, say, or 4/4 for the Broken Windmill).

Here's a new pattern from Trevor Tao:

The "Socks" Pattern

Code: Select all

* . . | . . . | * . .
. . * | . . . | . * .
. * . | . * . | . . *
------+-------+------
. . . | . . . | . . .
. . * | . . . | * . .
. . . | . . . | . . .
------+-------+------
* . . | . * . | . * .
. * . | . . . | * . .
. . * | . . . | . . *

Consider r1c1, r2c8, r8c2, r9c9. If the pattern is three colorable, obviously at least two of these must be the same. We can further say that at least two of these in the same band or stack must be the same (if we had two matching which were diagonally opposed, they would force the other two to match as well). But:

1. If the two matching cells are in the same band, they see r3c29 and r7c18 (one pair in the boxes, one pair in the columns), and the matching digit would need to be in both of r37c5.
2. If the two matching cells are in the same stack, they see r29c3 and r18c7 (one pair in the boxes, one pair in the rows), and the matching digit would need to be in both of r5c37.

Much like socks, you can never find a matching pair...

You can construct these patterns in different ways by choosing four cells in different boxes that don't see each other, completing a valid parity pattern in those boxes, and then adding the right extra cells to force this sort of contradiction.

ryokousha added a few other variants of this idea (including one that looks more like the Patto Patto pattern), might post them later (would be much easier if I could share images).