The New Sudoku Players' Forum

Website · by **denis_berthier** » Fri Jan 20, 2023 4:14 am

.
In how many puzzles a pattern appears is certainly an important question.
I tried Eleven's pattern #97 (ex #37) in 15 cells on mith's collection of 158,276 min-expands.

Code: Select all: +-------+-------+-------+ ! . . . ! X . . ! . . X ! ! . . X ! . . . ! . X . ! ! . X . ! . . X ! X . . ! +-------+-------+-------+ ! . . . ! . . X ! . . X ! ! . X . ! . X . ! . X . ! ! . . X ! X . . ! X . . ! +-------+-------+-------+ ! . . . ! . . . ! . . . ! ! . . . ! . . . ! . . . ! ! . . . ! . . . ! . . . ! +-------+-------+-------+

Like Tridagon, eleven's pattern is looked for immediately after whips[2] and Subsets[3].
Also like Tridagon, it has a trivial but essential pre-filter: the 3 digits of the pattern can only appear as givens in mini-column b7-c1 (in the above representation) and at least two of them must appear there.

I found 21,262 puzzles with eleven's pattern - that is 13.43%
.

by **eleven** » Fri Jan 20, 2023 1:12 pm

I can't believe, that patterns like this one

Code: Select all: +-------+-------+-------+ ! . . . ! . . . ! . . . ! ! . . 1 ! . . 1 ! . . 1 ! ! . . 1 ! . 1 . ! . 1 . ! +-------+-------+-------+ ! . . . ! . . 1 ! . 1 . ! ! . . . ! . 1 . ! . . 1 ! ! . . 1 ! 1 . . ! 1 . . ! +-------+-------+-------+

are not in T&E(2), because it is very easy to see, that it is impossible:
The digit in r6c3 must either be in r4c6 and r5c9 - killing it in r2, or in r5c5 and r4c8 - killing it in r3.

Website · by **denis_berthier** » Fri Jan 20, 2023 3:04 pm

eleven wrote:I can't believe, that patterns like this one
Code: Select all
+-------+-------+-------+ ! . . . ! . . . ! . . . ! ! . . 1 ! . . 1 ! . . 1 ! ! . . 1 ! . 1 . ! . 1 . ! +-------+-------+-------+ ! . . . ! . . 1 ! . 1 . ! ! . . . ! . 1 . ! . . 1 ! ! . . 1 ! 1 . . ! 1 . . ! +-------+-------+-------+

are not in T&E(2), because it is very easy to see, that it is impossible:

What I wrote is: the patterns I listed are POTENTIALLY in T&E(3); they can't be proven contradictory in RESTRICTED T&E(2), i.e. using only candidates in the pattern; this can be checked quite fast.
But I haven't checked if they can indeed be proven contradictory in the full T&E(2). The problem is, full T&E(2) takes much time to check for such patterns (651 candidates; many pairs of candidates must be tested, potentially several times each).
Rather than spending time on this, I was more interested in testing the presence of some patterns in real puzzles.

[Edit]: I checked this pattern in full T&E(2): it can indeed be proven contradictory in T&E(2). Computation took 17 mins; computation for restricted T&E only 1s.

Website · by **denis_berthier** » Sat Jan 21, 2023 1:36 pm

denis_berthier wrote:
eleven wrote: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).
Added: i have copied a zip file to my old google drive: here (list).

Instead of one pattern potentially in T&E(3) - i.e. that can't be proven contradictory in the simplified version of T&E(2), restricted to cells in the pattern - we now have 10:
Code: Select all
000001001000010010000100100000001001000010100000100010000000000000000000000000000 #38 12-cells 000000000001001001001010010000001010000010001001100100000000000000000000000000000 #171 13-cells 000000000001001001001010010001000000010001010010010001000000000000000000000000000 #180 13-cells 000000000001001001001010010001000000010001010100010001000000000000000000000000000 #181 13-cells 000000001000011010001100100001000001010100001100100010000000000000000000000000000 #56 15-cells 000000001001001010010010100001001000010100001100010001000000000000000000000000000 #66 15-cells 000001001001000010010010100000010001001001100010100010000000000000000000000000000 #97 15-cells (ex #37) 000001001001010010001010010001000001010001100010001100000000000000000000000000000 #5 16-cells 000001001001010010001010010001000001010001100100001100000000000000000000000000000 #6 16-cells 000001001001010010001010100001001000010100001100100001000000000000000000000000000 #9 16-cells

So, from 680 3-digit contradictory patterns produced by eleven, quick calculations in CSP-Rules have led to the above list of 10 patterns that cannot be proven contradictory in the restricted form of T&E(2) (which considers only candidates in the pattern). In and of itself, this is an interesting result:
- if you want to prove contradiction for them, you must either remain in T&E(2) and use some candidate(s) not in the pattern or jump to T&E(3);
- restricted T&E(2) is a very fast procedure and this pre-selection allows drastic improvements wrt a selection in full T&E(2).

Now, the question remains: are these 10 patterns contradictory in T&E(2) - i.e. in the full version of T&E(2) that allows using any candidate(s).
Until now, I have been busy other things.
But I have now done the full calculations for the 10 patterns. And the results are worth mentioning IMO.
1) The 10 patterns are contradictory in restricted T&E(3).
2) Only one pattern (#38 in 12 cells) is not contradictory in the full T&E(2); it is isomorphic to the tridagon pattern, with no condition on a target cell.

Code: Select all: +-------+-------+-------+ ! . . . ! . . 1 ! . . 1 ! ! . . . ! . 1 . ! . 1 . ! ! . . . ! 1 . . ! 1 . . ! +-------+-------+-------+ ! . . . ! . . 1 ! . . 1 ! ! . . . ! . 1 . ! 1 . . ! ! . . . ! 1 . . ! . 1 . ! +-------+-------+-------+ ! . . . ! . . . ! . . . ! ! . . . ! . . . ! . . . ! ! . . . ! . . . ! . . . ! +-------+-------+-------+ 000001001000010010000100100000001001000010100000100010000000000000000000000000000 #38 12-cells isomorphic to something closer to the trivalue oddagon: +-------+-------+-------+ ! . . . ! . . 1 ! . . 1 ! ! . . . ! . 1 . ! . 1 . ! ! . . . ! 1 . . ! 1 . . ! +-------+-------+-------+ ! . . . ! . . 1 ! . . 1 ! ! . . . ! 1 . . ! . 1 . ! ! . . . ! . 1 . ! 1 . . ! +-------+-------+-------+ ! . . . ! . . . ! . . . ! ! . . . ! . . . ! . . . ! ! . . . ! . . . ! . . . ! +-------+-------+-------+

Code: Select all: Reminder: trivalue oddagon pattern: +-------+-------+-------+ ! . . . ! . . 1 ! . . 1 ! ! . . . ! . 1 . ! . 1 . ! ! . . . ! 1 . . ! 1 . . ! +-------+-------+-------+ ! . . . ! 1 . . ! . . 1 ! ! . . . ! . 1 . ! . 1 . ! ! . . . ! . . 1 ! 1 . . ! +-------+-------+-------+ ! . . . ! . . . ! . . . ! ! . . . ! . . . ! . . . ! ! . . . ! . . . ! . . . ! +-------+-------+-------+

[Edit]: in order to be complete: none of the 630 patterns can be proven contradictory in full T&E(1).

by **totuan** » Tue Jan 24, 2023 7:19 pm

denis_berthier wrote:
Code: Select all
+-------+-------+-------+ ! . . . ! . . . ! . . . ! ! . . 1 ! . . 1 ! . . 1 ! ! . . 1 ! . 1 . ! . 1 . ! +-------+-------+-------+ ! . . . ! . . 1 ! . 1 . ! ! . . . ! . 1 . ! . . 1 ! ! . . 1 ! 1 . . ! 1 . . ! +-------+-------+-------+ ! . . . ! . . . ! . . . ! ! . . . ! . . . ! . . . ! ! . . . ! . . . ! . . . ! +-------+-------+-------+ 000000000001001001001010010000001010000010001001100100000000000000000000000000000 #171 13-cells

I found this one from mith's list, it’s not solving a puzzle, just one elimination.

Code: Select all: 1.345.7.9...1.9.......37.5.....95..3.3.7.19.4.9.34.5...1..74...8.2........6......;486938;29;3;11.2;11.2;10.4;DCFC+MFC

Code: Select all: *--------------------------------------------------------------------------------------* | 1 268 3 | 4 5 *268 | 7 *268 9 | | 24567 245678 4578 | 1 *268 9 | 23468 23468 *268 | | 2469 2468 489 |*268 3 7 | 12468 5 1268 | |----------------------------+----------------------------+----------------------------| | 2467 24678 1478 |*268 9 5 | 1268 12678 3 | | 256 3 58 | 7 *268 1 | 9 *268 4 | | 267 9 178 | 3 4 *268 | 5 12678 *12678 | |----------------------------+----------------------------+----------------------------| | 359 1 59 |*25689 7 4 | 268-3 *23689 *2568 | | 8 457 2 | 569 16 36 | 1346 134679 1567 | | 34579 457 6 | 2589 128 238 | 12348 1234789 12578 | *--------------------------------------------------------------------------------------*

eleven’s impossible pattern #171 13-cells => (359)r7c489=(17)r6c9
Move: (359)r7c13489=(1|7)r6c9-(1|7=7|1268)r1456c8-(268=359)r7c138 => r7c7<>3

totuan

by **ryokousha** » Thu Jan 26, 2023 10:43 pm

An open question in the field of chromatic patterns has been whether it is possible to fill a pattern with 3 cells in each row, column, and box such that all rows and columns within each box are covered (which is referred to as an "open" configuration) with three values. In other words, is a given open 3-rookery 3-colorable? Recently, Marek and I made some progress in being able to answer and understand this question.
There are three criteria that must be met for the pattern to be 3-colorable:

Permutation Parity Consistency (also known as TH/TO): Each loop of boxes must have an even number of - possibly shifted - upward (and downward) diagonals.
Any parity consistent pattern can then be transformed to a canonical form with standard downward diagonals in boxes 1,2,3,4 and 7, and - possibly shifted - downward diagonals in the other boxes to apply a
modulo 3 test
If r_i and c_i are the row- and column-numbers of the 9 instances of some digit d with r_i,c_i ∈ {0,…,8} for i ∈ {0,…,8}, then ∑_i=0..8 (r_i-c_i) = ∑_i=0..8 (r_i) - ∑_i=0..8 (c_i) ≡ 0 (mod3).

So the box-diagonals fall in three modulo-classes {-1,0,1} summing to 0 mod 3, which, given the arrangements of 8 of the 9 3x3 boxes, allows to determine the one arrangement of the 9th box allowing a 1-template.
It turns out this is not sufficient though. There is exactly one ED open 3-rookery that is not 3-colorable and does not even have a 1-template (is not fillable with a single digit), but passes the parity consistency and modulo 3 tests:
Code: Select all
+-------+-------+-------+ ! X . . ! X . . ! X . . ! ! . X . ! . X . ! . X . ! ! . . X ! . . X ! . . X ! +-------+-------+-------+ ! X . . ! . X . ! . . X ! ! . X . ! . . X ! X . . ! ! . . X ! X . . ! . X . ! +-------+-------+-------+ ! X . . ! . . X ! . X . ! ! . X . ! X . . ! . . X ! ! . . X ! . X . ! X . . ! +-------+-------+-------+

To understand why this is impossible, we must test for
spin consistency
In the top band, a chosen digit travels downward (spin down) or upward (spin up) going from left to right. Rows 4, 5, and 6 collide exactly with the possible positions of a digit traveling downward. In other words, the middle band prevents spin down as that would break one of these rows. Likewise, the bottom band prevents spin up for the top band. Therefore, the pattern has no 1-template - it is impossible to fill it even with one digit.

As a corollary of 3, it is possible to understand a certain family of 15c 3-digit chromatic patterns at a glance. For example here

Code: Select all: +-------+-------+-------+ ! X . . ! X . . ! X . . ! ! . X . ! . X . ! . X . ! ! . . X ! . . X ! . . X ! +-------+-------+-------+ ! . . . ! . . . ! . . . ! ! X . . ! . X . ! . . X ! ! . . . ! . . . ! . . . ! +-------+-------+-------+ ! . . . ! . . . ! . . . ! ! . . X ! . X . ! X . . ! ! . . . ! . . . ! . . . ! +-------+-------+-------+

row 5 prevents spin down for the top band, row 8 prevents spin up, qed.
jovi_al has used this in a clever way (not in its full impossible form though) in a recent puzzle.

by **ryokousha** » Sun Feb 26, 2023 3:09 pm

Eleven's list of 4-chromatic patterns in 2 bands contains an error in line 11 of the 10-cell pattern list (all10.txt). This pattern has 4 cells in box 6 and removal of any of those results in a 3-chromatic pattern.
I first wanted to retain the original numbering for the patterns 12-31, but this turns out to be a pain in the a** and very error-prone. So I'd suggest deleting the line instead and using the following lists of 629 patterns in total:

https://drive.google.com/file/d/1KtWpjasgS_509_Mw84t96fW-zhjmqhfX/view?usp=sharing

I have also added the missing 27 zeros at the end of the lines, so the strings work with standard tools without hassle.

by **ryokousha** » Sun Feb 26, 2023 3:20 pm

Unrelated, I have not posted the following (probably new) pattern yet:

Code: Select all: +-------+-------+-------+ ! . . X ! . . . ! X . . ! ! . X . ! X . . ! . . X ! ! X . . ! . . X ! . . . ! +-------+-------+-------+ ! . X . ! . X . ! X . . ! ! . . . ! X . . ! . . . ! ! . . X ! . . X ! . . X ! +-------+-------+-------+ ! . X . ! X . . ! . . . ! ! . . . ! . . . ! . . . ! ! . . X ! . . X ! . . . ! +-------+-------+-------+ ..1...1...1.1....11....1....1..1.1.....1.......1..1..1.1.1................1..1...

It is interesting in that it works much like "sausage roll": the induced connection graph of the restricted cells is 3-chromatic, but the restricted digits cannot be fully filled into the grid (r8c8 would have two of these, a "Schrödinger cell").
In tentative terminology the pattern is pseudo-chromatic.

Two proofs by marek:

Hidden Text: Show

Website · by **denis_berthier** » Sun Feb 26, 2023 3:59 pm

ryokousha wrote:
Code: Select all
+-------+-------+-------+ ! . . X ! . . . ! X . . ! ! . X . ! X . . ! . . X ! ! X . . ! . . X ! . . . ! +-------+-------+-------+ ! . X . ! . X . ! X . . ! ! . . . ! X . . ! . . . ! ! . . X ! . . X ! . . X ! +-------+-------+-------+ ! . X . ! X . . ! . . . ! ! . . . ! . . . ! . . . ! ! . . X ! . . X ! . . . ! +-------+-------+-------+ ..1...1...1.1....11....1....1..1.1.....1.......1..1..1.1.1................1..1...

It is interesting in that it works much like "sausage roll": the induced connection graph of the restricted cells is 3-chromatic, but the restricted digits cannot be fully filled into the grid (r8c8 would have two of these, a "Schrödinger cell").

Like sausage roll, it has a single free cell (marked "o") for givens:

Code: Select all: +-------+-------+-------+ ! . . X ! . . . ! X . . ! ! . X . ! X . . ! . . X ! ! X . . ! . . X ! . . . ! +-------+-------+-------+ ! . X . ! . X . ! X . . ! ! . . . ! X . . ! . . . ! ! . . X ! . . X ! . . X ! +-------+-------+-------+ ! . X . ! X . . ! . . . ! ! . . . ! . . . ! . o . ! ! . . X ! . . X ! . . . ! +-------+-------+-------+

It means it can never appear in non-degenerate form in a real puzzle.

The New Sudoku Players' Forum

Chromatic Patterns

Re: Chromatic Patterns

Re: Chromatic Patterns

Re: Chromatic Patterns

Re: Chromatic Patterns

Re: Chromatic Patterns

Re: Chromatic Patterns

Re: Chromatic Patterns

Re: Chromatic Patterns

Re: Chromatic Patterns