The hardest sudokus (new thread)

Everything about Sudoku that doesn't fit in one of the other sections

Re: The hardest sudokus (new thread)

Postby denis_berthier » Sat Mar 12, 2022 8:28 am

yzfwsf wrote:2+2 or 4+0, 0+4 is not a dead pattern, while 1+3 or 3+1 is a dead pattern.


I'll have to check this part about diagonals and anti-diags, but I hold to the content of the special cell and on the eliminations rather than assertion view
denis_berthier
2010 Supporter
 
Posts: 4213
Joined: 19 June 2007
Location: Paris

Re: The hardest sudokus (new thread)

Postby denis_berthier » Sat Mar 12, 2022 10:55 am

.
I tried this case:
Code: Select all
   +-------------------------------+-------------------------------+-------------------------------+
   ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
   ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
   ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
   +-------------------------------+-------------------------------+-------------------------------+
   ! 123       123456789 123456789 ! 123       123456789 123456789 ! 123456789 123456789 123456789 !
   ! 123456789 123       123456789 ! 123456789 123       123456789 ! 123456789 123456789 123456789 !
   ! 123456789 123456789 123       ! 123456789 123456789 123       ! 123456789 123456789 123456789 !
   +-------------------------------+-------------------------------+-------------------------------+
   ! 123       123456789 123456789 ! 123       123456789 123456789 ! 123456789 123456789 123456789 !
   ! 123456789 123       123456789 ! 123456789 123456789 123456789 ! 123456789 123456789 123456789 !
   ! 123456789 123456789 123       ! 123456789 123456789 123       ! 123456789 123456789 123456789 !
   +-------------------------------+-------------------------------+-------------------------------+


It doesn't work in T&E(W2, 2); so, finally, there might be additional conditions on the pattern of cells. However, it can't be restricted to only diags or anti-diags, because this is not invariant under isomorphisms.


yzfwsf wrote:The arrangement of three cells in each box is divided into diagonal or anti-diagonal arrangement. If the arrangement of 4 boxes is 3*diagonal + 1*anti-diagonal or 3*anti-diagonal + 1*diagonal, then such an arrangement of 12 cells is considered oddagon.

Considered oddagon by whom? This doesn't have anything to do with oddagons, which are defined as chains of odd length and are totally unrelated to any diagonal conditions.

yzfwsf wrote:The rules of diagonal and anti-diagonal are: find the two cells in the box where the row and column coordinates differ by 1, and the direction of the line between the two cells.

I can't make any sense of this.
denis_berthier
2010 Supporter
 
Posts: 4213
Joined: 19 June 2007
Location: Paris

Re: The hardest sudokus (new thread)

Postby yzfwsf » Sat Mar 12, 2022 12:29 pm

denis_berthier wrote:.
yzfwsf wrote:The rules of diagonal and anti-diagonal are: find the two cells in the box where the row and column coordinates differ by 1, and the direction of the line between the two cells.

I can't make any sense of this.

Code: Select all
diagonal arrangemant
.-------------.
| 123         |
|     123     |
|         123 |
'-------------'
.-------------.
|     123     |
|         123 |
| 123         |
'-------------'
.-------------.
|         123 |
| 123         |
|     123     |
'-------------'
.-------------.
| 123         |
|     123     |
|         123 |
'-------------'

Code: Select all
anti-diagonal arrangement
.-------------.
| 123         |
|         123 |
|     123     |
'-------------'
.-------------.
|     123     |
| 123         |
|         123 |
'-------------'
.-------------.
|         123 |
|     123     |
| 123         |
'-------------'

denis_berthier wrote:.
yzfwsf wrote:The arrangement of three cells in each box is divided into diagonal or anti-diagonal arrangement. If the arrangement of 4 boxes is 3*diagonal + 1*anti-diagonal or 3*anti-diagonal + 1*diagonal, then such an arrangement of 12 cells is considered oddagon.

Considered oddagon by whom? This doesn't have anything to do with oddagon, which are defined as chains of odd length and are totally unrelated to any diagonal conditions.

12 cells construct a trivalue oddagon. See here: http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539-810.html#p306966
yzfwsf
 
Posts: 905
Joined: 16 April 2019

Re: The hardest sudokus (new thread)

Postby denis_berthier » Sat Mar 12, 2022 12:48 pm

yzfwsf wrote:
Code: Select all
diagonal arrangemant
.-------------.
| 123         |
|     123     |
|         123 |
'-------------'
.-------------.
|     123     |
|         123 |
| 123         |
'-------------'
.-------------.
|         123 |
| 123         |
|     123     |
'-------------'
.-------------.
| 123         |
|     123     |
|         123 |
'-------------'

Code: Select all
anti-diagonal arrangement
.-------------.
| 123         |
|         123 |
|     123     |
'-------------'
.-------------.
|     123     |
| 123         |
|         123 |
'-------------'
.-------------.
|         123 |
|     123     |
| 123         |
'-------------'


All these blocks are equivalent to the first under the proper isomorphisms.


yzfwsf wrote:
denis_berthier wrote:
yzfwsf wrote:The arrangement of three cells in each box is divided into diagonal or anti-diagonal arrangement. If the arrangement of 4 boxes is 3*diagonal + 1*anti-diagonal or 3*anti-diagonal + 1*diagonal, then such an arrangement of 12 cells is considered oddagon.

Considered oddagon by whom? This doesn't have anything to do with oddagon, which are defined as chains of odd length and are totally unrelated to any diagonal conditions.

12 cells construct a trivalue oddagon. See here: http://forum.enjoysudoku.com/the-hardest-sudokus-new-thread-t6539-810.html#p306966

I don't think that an occasional remark can in any way justify saying "it is considered...".
denis_berthier
2010 Supporter
 
Posts: 4213
Joined: 19 June 2007
Location: Paris

Re: The hardest sudokus (new thread)

Postby yzfwsf » Sat Mar 12, 2022 12:56 pm

denis_berthier wrote:All these blocks are equivalent to the first under the proper isomorphisms.

A single box that is natural, what about 4 boxes, do you still think it is isomorphic? So before I said, 1 + 3 or 3 + 1.
yzfwsf
 
Posts: 905
Joined: 16 April 2019

Re: The hardest sudokus (new thread)

Postby denis_berthier » Sat Mar 12, 2022 1:31 pm

yzfwsf wrote:
denis_berthier wrote:All these blocks are equivalent to the first under the proper isomorphisms.

A single box that is natural, what about 4 boxes, do you still think it is isomorphic? So before I said, 1 + 3 or 3 + 1.

Do you mean that there must be a global isomorphism such that:
- either 3 blocks are diagonal and 1 block is anti-diagonal
- or 1 block is diagonal and 3 blocks are anti-diagonal
and no other case (such as 4/0, 2/2.., 1/1...)
?
denis_berthier
2010 Supporter
 
Posts: 4213
Joined: 19 June 2007
Location: Paris

Re: The hardest sudokus (new thread)

Postby hendrik_monard » Sat Mar 12, 2022 1:41 pm

Another 11.9 from the loki family?
8..17.93.......1.2.3..2..87......7.95.9.1....6...........9.73.8...23...1....8.29. 11.9/1.2/1.2
hendrik_monard
 
Posts: 96
Joined: 19 April 2021
Location: Leuven (Louvain) Belgium

Re: The hardest sudokus (new thread)

Postby yzfwsf » Sat Mar 12, 2022 2:11 pm

denis_berthier wrote:Do you mean that there must be a global isomorphism such that:
- either 3 blocks are diagonal and 1 block is anti-diagonal
- or 1 block is diagonal and 3 blocks are anti-diagonal
and no other case (such as 4/0, 2/2.., 1/1...)
?

Code: Select all
.---------------------------------.---------------------------------.---------------------------------.
| 123        123456789  123456789 | 123        123456789  123456789 | 123456789  123456789  123456789 |
| 123456789  123        123456789 | 123456789  123        123456789 | 123456789  123456789  123456789 |
| 123456789  123456789  123       | 123456789  123456789  123       | 123456789  123456789  123456789 |
:---------------------------------+---------------------------------+---------------------------------:
| 123        123456789  123456789 | 12356      123456789  12389     | 123456789  123456789  123456789 |
| 123456789  123        123456789 | 123456789  123        123456789 | 123456789  123456789  123456789 |
| 123456789  123456789  123       | 12389      123456789  12356     | 123456789  123456789  123456789 |
:---------------------------------+---------------------------------+---------------------------------:
| 123456789  123456789  123456789 | 123456789  123456789  123456789 | 123456789  123456789  123456789 |
| 123456789  123456789  123456789 | 123456789  123456789  123456789 | 123456789  123456789  123456789 |
| 123456789  123456789  123456789 | 123456789  123456789  123456789 | 123456789  123456789  123456789 |
'---------------------------------'---------------------------------'---------------------------------'

The current state can use this technique to safely delete 56b5p19, without causing no solution, but deleting 89b5p37 will cause no solution.
yzfwsf
 
Posts: 905
Joined: 16 April 2019

Re: The hardest sudokus (new thread)

Postby mith » Sat Mar 12, 2022 3:49 pm

The basic idea of ryokousha's parity flow proof is to consider the permutations of the digits within each box, and the interaction of these permutations between boxes. In the simplest case, consider the following arrangement:

Code: Select all
. . * | . . *
. * . | . * .
* . . | * . .
------+------
. . * | * . .
. * . | . * .
* . . | . . *


Let's start with box 1. The digits in these cells (say ABC) appear with some permutation. There are three different types of parity we can talk about:

i. The cell parity (diagonal or anti-diagonal); in this case, b124 are diagonal, and b5 is anti-diagonal. This is unrelated to how the digits appear in the cells, it is purely positional.
ii. The column/stack parity. As we go from left to right, does the digit permutation have a positive or negative parity? So if r3c1 were A, r2c2 were B, and r1c3 were C, we would say this has a positive column parity - as we go from c1 to c3, the permutation of digits is ABC.
iii. The row/band parity. As we go from bottom to top (note this is different from how we usually label the rows, but choosing this convention to better go with the "diagonal"/"anti-diagonal" parity based on a typical coordinate system), does the digit permutation have a positive or negative parity?

We can make the following statements about how these parities interact, with each other and across boxes:

i. If two boxes are in the same stack, they have the same stack parity. (For example, if c1 to c3 in b1 goes ABC, then c1 to c3 in b4 must either go BCA or CAB; any negative parity will have a conflict.)
ii. If two boxes are in the same band, they have the same band parity.
iii. If the band and stack parities of a box are the same, the cell parity is diagonal; if different, the cell parity is anti-diagonal.

And now we have enough to prove the above configuration is impossible:

i. b4 has the same band and stack parity.
ii. b1 has the same stack parity as b4.
iii. b1 has the same band and stack parity.
iv. b2 has the same band parity as b1.
v. b2 has the same band and stack parity.
vi. b5 has the same stack parity as b2, and the same band parity as b4.
vii. by i-v, b4's band parity and b2's stack parity are the same, so b5 should be diagonal; however, it is anti-diagonal #

Note that a comparable argument can be applied regardless of the actual cell parities of each box - the result is that a 3/1 split of diagonal and anti-diagonal is broken. The point is that the boxes form a loop, and anti-diagonal parties entail flipping band/stack parities within a box, so an odd number of them will always result in a contradiction - you can't have an odd number of parity switches in a cycle.

This generalizes to arrangements in more boxes - for example, you could have a cycle of b124689, and come to a conclusion about certain diagonal/anti-diagonal splits there. However, it seems impossible such an arrangement could lead to a very high SER, as the six digits that aren't part of the trivalue oddagon would be (mostly) obtained as singles in the other boxes.

I presented an alternate proof using coloring (see Loki puzzle thread). I find it useful to think of coloring after the initial TH deduction, as it makes subsequent deductions outside of the four boxes much more apparent (in the case of Loki, you get a remote triple within the four boxes which interacts with r8c1 and some other cells outside of the four boxes).

You could also have multiple TH arrangements within the same grid (on different digits) - however, having too many of the digits in a TH pattern tends to reduce it to bivalue oddagons, and it's hard to see how to set this up in a classic otherwise. (But this could perhaps be used to make some particularly nasty-to-SE sukaku.)

The TH pattern (and extensions) are also further generalized as "chromatic" patterns - that is, patterns of cells which are not 3-colorable. Whenever a sufficient number of cells in a non-3-colorable pattern are limited to 3 digits, you can make a deduction (elimination of those three digits from certain cells - as Denis points out, this may not necessarily lead directly to a placement; later, I'll dig up an example of an 11.6 which doesn't have a direct TH elimination but does result in a weird virtual pair). IIRC, shye's Patto Patto is a very different example of a non-3-colorable pattern.
mith
 
Posts: 996
Joined: 14 July 2020

Re: The hardest sudokus (new thread)

Postby mith » Sat Mar 12, 2022 3:58 pm

hendrik_monard wrote:Another 11.9 from the loki family?
8..17.93.......1.2.3..2..87......7.95.9.1....6...........9.73.8...23...1....8.29. 11.9/1.2/1.2


This is a morph of the other minimal referenced here: the-hardest-sudokus-new-thread-t6539-1125.html#p318311

If our internet ever comes back, I’ll post a full update. I have another 14 11.8s in addition to the two 11.9s.
mith
 
Posts: 996
Joined: 14 July 2020

Re: The hardest sudokus (new thread)

Postby coloin » Sat Mar 12, 2022 4:22 pm

denis_berthier wrote:Note: I can't see how this pattern could seriously be called tri-value oddagon; it doesn't have anything common with an oddagon. As for the name Thor's hammer, it is also totally unjustified (the shape depends on morphs) and it reminds me of some websites that give similarly absurd names to anything. I think this pattern deserves a serious name.


I think Thor's Hammer is a very apt name for this pattern

Code: Select all
+---+---+---+
|..1|2..|...|
|.2.|.3.|...|
|3..|..1|...|
+---+---+---+
|1..|3..|...|
|.3.|.2.|...|
|..2|..?|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+  to be valid , r6c6 cant be a 1, has to be one of 456789

Code: Select all
+---+---+---+
|..1|2..|...|
|.2.|.3.|...|
|3..|..1|...|
+---+---+---+
|1..|3..|...|
|.3.|.2.|...|
|..2|..1|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+ no solutions
coloin
 
Posts: 2494
Joined: 05 May 2005
Location: Devon

Re: The hardest sudokus (new thread)

Postby mith » Sat Mar 12, 2022 9:33 pm

Obviously this isn’t an oddagon in the usual chain sense, but it’s more analogous than it might appear, in two ways:

1. The naive brute-force approach to proving the pattern is broken amounts to showing you end up with a bivalue oddagon in each case. For example, if we try to place A in these cells:

Code: Select all
. . A | . . *
. * . | . * .
* . . | A . .
------+------
. . * | * . .
. A . | . * .
* . . | . . A


Then there is an odd cycle of BC bivalue cells including all the marked cells except r1c6. This happens regardless of your placement of As in the boxes.

2. The parity flow argument amounts to “you can’t have an odd number of parity switches in a cycle”.

I think “chromatic pattern” works nicely for the general class of graph-colorability constraints, and parity flow for the specific case of permutation parity switching, but whether this has a serious formal name or something silly like “Thor’s Hammer” doesn’t particularly matter to me.
mith
 
Posts: 996
Joined: 14 July 2020

Re: The hardest sudokus (new thread)

Postby eleven » Sun Mar 13, 2022 12:01 am

Denis,

maybe this sounds simpler for you:

If in 4 boxes of 2 bands and 2 stacks you have those 3 digits in 3 cells each, where each cell in a box is single in row and column, there are just 3 cases ([added:] classes). The cells form
3 rectangles or no rectangle, or one.
In the first 2 cases easily a solution can be found.
For the 1 rectangle case there are several proofs, that it is an impossible pattern.
All different shapes are just equivalents, which you can get by swapping rows in a band and columns in a stack [added:], and switching the bands or stacks (it is obvious, that these equivalence transformations never can create or delete a rectangle).

Concerning the name trivalue oddagon, mith gave an explanation above. However you place one digit, a bivalue oddagon for the other 2 digits remains.
eleven
 
Posts: 3152
Joined: 10 February 2008

Re: The hardest sudokus (new thread)

Postby denis_berthier » Sun Mar 13, 2022 6:07 am

.
Hi mith, coloin, yzfwsf, eleven
Thanks for your explanations. I hadn't studied this pattern before and what I read recently didn't help much to make the conditions clear.

Do you now all agree that there may be more than one extra candidate in the target cell and that the rule is fundamentally an elimination rule (not an assertion one)?

What about making some of the candidates in the 3-valued cells optional?

mith, do you have any precise reference to a Ryokousha paper or post? I was unable to find any reference to this name on the web (except for a tea brand).
The idea of parity numbers is interesting but IMO overly complicated for this pattern.

eleven, I'm writing a systematic proof based on T&E (admitedly very inelegant) and I find 3 and only 3 different cases. A rectangle appears in each case, but the 3 cases are not equivalent under isomorphisms. I'll make it clean and publish it soon.

BTW, it seems to me we are getting very far from the topic this thread with the discussion of this pattern; it would deserve a thread of its own in the "advanced solving techniques" section.
denis_berthier
2010 Supporter
 
Posts: 4213
Joined: 19 June 2007
Location: Paris

Re: The hardest sudokus (new thread)

Postby eleven » Sun Mar 13, 2022 11:33 am

Whatever pattern with one rectangle you have, by switching rows and columns you can bring it to the center in each box.
Code: Select all
-----------------
| a . . | . . a |
| . c . | . c . |
| . . b | b . . |
-----------------
| . . b | b . . |
| a . . | . . a |
| . c . | . c . |
----------------
-
E.g. for case a switch r12 and c12,c56, for case b r23,r45 and c23,45, for case c r56
Code: Select all
-----------------
| a . b | c . d |
| . x . | . x . |
| b . a | d . c |
-----------------
| . . . | . . . |
| . x . | . x . |
| . . . | . . . |
-----------------

In case b switch r1c3, if then in box 2 you have them in d switch c46.
Code: Select all
-----------------
| x . . | x . . |
| . x . | . x . |
| . . x | . . x |
-----------------
| a . b | c . d |
| . x . | . x . |
| b . a | d . c |
-----------------

In case b switch r46. In box 4 then you can't have case c with 3 rectangles.
I.e. all patterns with one rectangle are equivalent to this:
Code: Select all
-----------------
| x . . | x . . |
| . x . | . x . |
| . . x | . . x |
-----------------
| x . . | . . x |
| . x . | . x . |
| . . x | x . . |
-----------------

For this pattern i showed here, that the 3 digits only are not possible.
This means, that if a puzzle has a solution, at least one other digit in these cells must be true (= the 3 digits must be false in at least one of the cells), wherever one is possible in a given candidates grid.
Last edited by eleven on Sun Mar 13, 2022 8:07 pm, edited 1 time in total.
eleven
 
Posts: 3152
Joined: 10 February 2008

PreviousNext

Return to General