Chromatic Patterns

Advanced methods and approaches for solving Sudoku puzzles

Re: Chromatic Patterns

Postby 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%
.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: Chromatic Patterns

Postby 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.
eleven
 
Posts: 3082
Joined: 10 February 2008

Re: Chromatic Patterns

Postby 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.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: Chromatic Patterns

Postby 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).
Last edited by denis_berthier on Wed Jan 25, 2023 8:59 am, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: Chromatic Patterns

Postby 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
totuan
 
Posts: 230
Joined: 25 May 2010
Location: vietnam

Re: Chromatic Patterns

Postby 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:

  1. 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
  2. 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
  3. 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.
ryokousha
 
Posts: 37
Joined: 30 April 2022

Re: Chromatic Patterns

Postby 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.
Last edited by ryokousha on Sun Feb 26, 2023 3:56 pm, edited 1 time in total.
ryokousha
 
Posts: 37
Joined: 30 April 2022

Re: Chromatic Patterns

Postby 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
r3c1 has to appear in b6p19 because of TH 8-loop in b1346, then it takes r5c4 in r5 and the rest is just colouring.

Hidden Text: Show
you can get r5c1, then b1346 have a TH without a rectangle line (c8), so r2c29 r4c27 contain each digit (456) at least once, then r2c4 appears in r4c27, b5p9, and by skyscrapers in r26 on the remaining digits even in r1c3 and r4c2, then the other digits are both forced into r8c8 by pairs in r79 and c79.
ryokousha
 
Posts: 37
Joined: 30 April 2022

Re: Chromatic Patterns

Postby 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.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Previous

Return to Advanced solving techniques