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 mith » Wed Jul 14, 2021 4:31 pm

It looks like a sort of trivalue oddagon? Whatever you put in r5c6 and r6c5, you need the third digit in one of r1c1, r1c6, and r6c1, but none of these work - r1c1 implies r3c4 and r4c3 are different (via r3c3) and the same (via r1c6 and r6c1). r1c6 and r6c1 don't work either, for somewhat more complicated reasons.
mith
 
Posts: 950
Joined: 14 July 2020

Re: The hardest sudokus (new thread)

Postby marek stefanik » Wed Jul 14, 2021 4:58 pm

Interesting, my way to prove it was that the digit that appears in both c12 then restricts one of the digits in the other stack, forcing it to appear twice in one column. Also feels very complicated.

Luckily the pattern is simple to recognize (in each box one cell in each miniline forming exactly one rectangle), so one doesn't have to go through that every time.

Were the puzzles generated with the idea in mind or did it just naturally appear in the setting algorithm?
Is there any list of these multi-floor patterns that have been used to generate these puzzles?
marek stefanik
 
Posts: 354
Joined: 05 May 2021

Re: The hardest sudokus (new thread)

Postby mith » Wed Jul 14, 2021 5:29 pm

Someone on the CTC discord came up with the following argument (sort of the reverse of my r1c1 case above):

Set box 5 (1r4c4, 2r5c6, 3r6c5, WLOG). Both of r3c4 and r4c3 see r4c4, so they are both 2 or 3.

Case 1: r3c4 and r4c3 are the same (say 2, WLOG). Then r2c5 and r6c1 are both 1 due to 3r6c5, r1c6 and r5c2 are both 3, and now r1c1 and r2c2 must both be 2.
Case 2: r3c4 and r4c3 are different (say 23 in that order, WLOG). Now 1 must be in r2c5 and r5c2, putting 2 in r6c1 and 3 in r1c6... and now r1c1 and r3c3 must both be 1.

These puzzles weren't specifically designed with this pattern (or any pattern) in mind. They are result of neighborhood searches on existing hard puzzles. I have four scripts that I run:

"Generator" (-2, +2), "Adder" (-1, +2), and "Reducer" (-2, +1) all generate new potential grids by removing 1 or 2 clues and then adding back 1 or 2 clues, in all possible ways. If the result is uniquely solvable, distinct from other puzzles in the database, and sufficiently hard to pass some filters (I use backdoor count and q2 as a first pass filter, then skfr as a second filter; I also calculate q1 if it passes both filters), then they get added to the database (trying to find the right balance between having it in the database so I don't rate it again in future, and not having the database too big).
"Expander" takes a puzzle, adds all possible singles, and then minimizes the result; there's no filter on these, the resulting puzzles are guaranteed to be at least as hard (unless there is a uniqueness pattern being used, perhaps) so I just calculate the new ratings if it's a new puzzle. The main benefit to this one has been in improving the seeding of the larger clue count databases.

I have a complicated (and somewhat arbitrary) metric for choosing puzzles to try next, and I run these on a variety of clue counts to reduce the chance of a database collision (until I convert this into a proper multi-threaded program). And then I have a separate database for sufficiently hard filter ratings to be rated with SER, which is eating most of the CPU threads all the time. :)
mith
 
Posts: 950
Joined: 14 July 2020

Re: The hardest sudokus (new thread)

Postby marek stefanik » Wed Jul 14, 2021 6:23 pm

What I meant was that if you generate a puzzle from a known hard puzzle with JE, it will most likely contain a JE itself. Sometimes it can mutate into a Senior Exocet, SK loop or the half JE + SK loop (or even something new), but there will be some similarities.

This pattern seems completely different, so I'd be surprised if it came from a JE seed two clues at a time. If there are any families of difficult puzzles that do not have a known exotic pattern, it could be possible to discover some new ones.

Thanks for the insights into the creation process, especially the Expander sounds very cool.
marek stefanik
 
Posts: 354
Joined: 05 May 2021

Re: The hardest sudokus (new thread)

Postby denis_berthier » Wed Jul 14, 2021 6:32 pm

marek stefanik wrote: what kind of magic would one have to use to prove this contradiction

Code: Select all
123   .    .  |  .    .   123
 .   123   .  |  .   123   .
 .    .   123 | 123   .    .
––––––––––––––+––––––––––––––
 .    .   123 | 123   .    .
 .   123   .  |  .    .   123
123   .    .  |  .   123   .


As it seems related to "braids analysis", I've asked an expert of it; waiting his answer.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: The hardest sudokus (new thread)

Postby eleven » Wed Jul 14, 2021 9:41 pm

Very nice observation of an impossible pattern !
Nothing related to Exocet or SK loop, but oddagon, i think.

My proof:
Set the digits in b1 123 (no loss of generality)
Code: Select all
 |--------------------+------------------+
 |  1    .      .     |  .     .    23   |
 |  .     2     .     |  .     13  .     |
 |  .     .     3     |  12    .   .     |
 |---------------------------------------+
 |  .     .      12   | a12+3  .  .      |
 |  .     13     .    |  .     .  b12-3  |
 |  23    .      .    |  .    c12-3 .    |
 |--------------------+------------------+

ab cannot be 23 (two 1's in b3) or 13 (two 2's in b2) -> b<>3
ac cannot be 23 (two 1's in b2) or 13 (two 2's in b3) -> c<>3
=> a=3
Code: Select all
 |--------------------+-----------------+
 |  1    .      .     |  .     .    23  |
 |  .     2     .     |  .     13  .    |
 |  .     .     3     |  12    .   .    |
 |---------------------+----------------+
 |  .     .      12   |  3     .   .    |
 |  .     13     .    |  .     .  b12   |
 |  23    .      .    |  .    c12  .    |
 |--------------------+-----------------+

bc cannot be 21 (two 3's in b2) or 12 (two 3's in b3)
=> impossible pattern
[edit: corrected b4 to b3]
Last edited by eleven on Sun Mar 13, 2022 11:30 am, edited 1 time in total.
eleven
 
Posts: 3082
Joined: 10 February 2008

Re: The hardest sudokus (new thread)

Postby coloin » Wed Jul 14, 2021 10:05 pm

Yes ...my contribution - since i have studied these "diagonal " in box patterns

Seems that some of them are impossible / deadly patterns

Boxes 124 can always be morphed to this pattern - and there are only 2 ED ways to legally fill 3 clues in a diagonal
Code: Select all
1..3......2..1......3..2...3.........1.........2.................................
1..3......2..1......3..2...2.........3.........1.................................

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

filling box 5 with 3 clues - these are the only valid ones with the "diagonal pattern"
Code: Select all
1..3......2..1......3..2...3..1......1..2......2..3..............................
1..3......2..1......3..2...3..2......1..3......2..1..............................
1..3......2..1......3..2...3...2.....1...3.....21................................
1..3......2..1......3..2...3....1....1.2.......2.3...............................

1..3......2..1......3..2...2..1......3..2......1..3..............................
1..3......2..1......3..2...2....1....3.2.......1.3...............................
1..3......2..1......3..2...2....3....3.1.......1.2...............................

Of these 9 there are 3 Essentially Different
Code: Select all
1..3......2..1......3..2...3..1......1..2......2..3..............................
1..3......2..1......3..2...3..2......1..3......2..1..............................
1..3......2..1......3..2...3...2.....1...3.....21................................

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

all others would tend to give an invalid 3-template

Code: Select all
And hence this 6-template is fruitlessly invalid
+---+---+---+
|.45|.87|6.9|
|6.7|4.9|8.5|
|98.|56.|.74|
+---+---+---+
|.58|67.|94.|
|4.9|8.5|.67|
|76.|.94|.58|
+---+---+---+
|.76|95.|48.|
|5.4|..8|796|
|89.|746|5..|
+---+---+---+


So quite possibly there could be a new solving technique - based on invalid templates - but some already have employed valid templates as a technique [mbm]
Code: Select all
+-------------------------------+-------------------------------+-------------------------------+
| 1         456789    456789    | 3         456789    456789    | 2456789   2456789   2456789   |
| 456789    2         456789    | 456789    1         456789    | 3456789   3456789   3456789   |
| 456789    456789    3         | 456789    456789    2         | 1456789   1456789   1456789   |
+-------------------------------+-------------------------------+-------------------------------+
| 3         456789    456789    | 456789    456789    456789    | 12456789  12456789  12456789  |
| 456789    1         456789    | 456789    2         3456789   | 3456789   3456789   3456789   |
| 456789    456789    2         | 1         3456789   3456789   | 3456789   3456789   3456789   |
+-------------------------------+-------------------------------+-------------------------------+
| 2456789   3456789   1456789   | 2456789   3456789   13456789  | 123456789 123456789 123456789 |
| 2456789   3456789   1456789   | 2456789   3456789   13456789  | 123456789 123456789 123456789 |
| 2456789   3456789   1456789   | 2456789   3456789   13456789  | 123456789 123456789 123456789 |
+-------------------------------+-------------------------------+-------------------------------+


r4c6 cant be a 3
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Re: The hardest sudokus (new thread)

Postby eleven » Wed Jul 14, 2021 10:33 pm

coloin wrote:So quite possibly there could be a new solving technique - based on invalid templates - but some already have employed valid templates as a technique
The point is, that this pattern can be spotted quite easily manually.
eleven
 
Posts: 3082
Joined: 10 February 2008

Re: The hardest sudokus (new thread)

Postby mith » Wed Jul 14, 2021 11:32 pm

marek stefanik wrote:What I meant was that if you generate a puzzle from a known hard puzzle with JE, it will most likely contain a JE itself. Sometimes it can mutate into a Senior Exocet, SK loop or the half JE + SK loop (or even something new), but there will be some similarities.

This pattern seems completely different, so I'd be surprised if it came from a JE seed two clues at a time. If there are any families of difficult puzzles that do not have a known exotic pattern, it could be possible to discover some new ones.

Thanks for the insights into the creation process, especially the Expander sounds very cool.


Yeah, unfortunately I don't track the "parent" grid - if there's one thing I would change if I could go back to when I started this, it would probably be that. There's no single seed I'm using, rather I started from champagne's database and once I find neighbors of one puzzle I move on to the next (which could be one of the newly generated ones, or could be a completely unrelated one that happens to have a similar rating). It would be neat to see which puzzle is the most removed from its seed, and which scripts were the biggest contributors.
mith
 
Posts: 950
Joined: 14 July 2020

Re: The hardest sudokus (new thread)

Postby marek stefanik » Thu Jul 15, 2021 12:04 am

coloin wrote:
Code: Select all
And hence this 6-template is fruitlessly invalid
+---+---+---+
|.45|.87|6.9|
|6.7|4.9|8.5|
|98.|56.|.74|
+---+---+---+
|.58|67.|94.|
|4.9|8.5|.67|
|76.|.94|.58|
+---+---+---+
|.76|95.|48.|
|5.4|..8|796|
|89.|746|5..|
+---+---+---+
see page 54 for fruit (any puzzle with 30+ clues except for the first one which has three guardians and no direct elimination).

Looking at the valid patterns, I realized that all the diagonals go the same way. When morfed, there will always be an even number of diagonals in each direction.

Have you done any research on 6-box templates? I've had a quick look and from what I've seen both one hexagon and diagonal parity approaches seem to be useful.
marek stefanik
 
Posts: 354
Joined: 05 May 2021

Re: The hardest sudokus (new thread)

Postby dobrichev » Thu Jul 15, 2021 9:14 pm

eleven wrote:
coloin wrote:So quite possibly there could be a new solving technique - based on invalid templates - but some already have employed valid templates as a technique
The point is, that this pattern can be spotted quite easily manually.

Maybe close to this subject is this known invalid pattern from here.
Code: Select all
....12.34
.134..2..
.423..1..
.21.34...
3..1...42
4..2...13
.34....21
1...234..
2...413..

Actually all valid permutations of 4 digits in this pattern have no completion and the above is one of them.
Code: Select all
....11.11
.111..1..
.111..1..
.11....11
1...111..
1...111..
.11.11...
1..1...11
1..1...11

In theory one can generate a puzzle where spotting this pattern eliminates a candidate, and this would be a really exotic solving technique.
I agree with Eleven's general doubts that easy techniques solve such puzzles after all.
dobrichev
2016 Supporter
 
Posts: 1845
Joined: 24 May 2010

Re: The hardest sudokus (new thread)

Postby coloin » Fri Jul 16, 2021 5:39 pm

I read it that eleven was saying that these patterns can be spotted easily by the manual solver ...

I suppose it helps to clarify the valid/invalid patterns of the "diagonal" 123 clues.
Boxes 1,2 and 4 can always be morphed to this pattern

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


There are 6 ways to add 3 diagonal clue patterns to box 5

Here are representatives of the possible valid patterns
Code: Select all
+---+---+---+              +---+---+---+              +---+---+---+       
|1..|3..|...|              |1..|3..|...|              |1..|3..|...|       
|.2.|.1.|...|              |.2.|.1.|...|              |.2.|.1.|...|       
|..3|..2|...|              |..3|..2|...|              |..3|..2|...|       
+---+---+---+              +---+---+---+              +---+---+---+       
|3..|1..|...|              |3..|.2.|...|              |3..|..1|...|       
|.1.|.2.|...|              |.1.|..3|...|              |.1.|2..|...|       
|..2|..3|...|              |..2|1..|...|              |..2|.3.|...|       
+---+---+---+              +---+---+---+              +---+---+---+       
|...|...|...|              |...|...|...|              |...|...|...|       
|...|...|...|              |...|...|...|              |...|...|...|       
|...|...|...|              |...|...|...|              |...|...|...|       
+---+---+---+  valid       +---+---+---+   valid      +---+---+---+   valid 


Here are representatives of the invalid patterns
Code: Select all
                                                                 
+---+---+---+              +---+---+---+              +---+---+---+         
|1..|3..|...|              |1..|2..|...|              |1..|2..|...|         
|.2.|.1.|...|              |.2.|.3.|...|              |.2.|.3.|...|         
|..3|..2|...|              |..3|..1|...|              |..3|..1|...|         
+---+---+---+              +---+---+---+              +---+---+---+         
|3..|1..|...|              |2..|.1.|...|              |2..|..3|...|         
|.1.|..3|...|              |.3.|X..|...|              |.3.|.1.|...|         
|..2|.X.|...|              |..1|..2|...|              |..1|X..|...|         
+---+---+---+              +---+---+---+              +---+---+---+         
|...|...|...|              |...|...|...|              |...|...|...|         
|...|...|...|              |...|...|...|              |...|...|...|         
|...|...|...|              |...|...|...|              |...|...|...|         
+---+---+---+  invalid     +---+---+---+   invalid    +---+---+---+   invalid   



For comepleteness
of the 15 ED ways to form a 27 clue pattern with 3 "diagonal" clues per box
there are only 3 out of the 15 which have valid template

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

Re: The hardest sudokus (new thread)

Postby marek stefanik » Fri Jul 16, 2021 6:41 pm

dobrichev wrote:Maybe close to this subject is this known invalid pattern from here.
Code: Select all
....12.34
.134..2..
.423..1..
.21.34...
3..1...42
4..2...13
.34....21
1...234..
2...413..

That's a really cool find!
It also can be proven quite easily.

Code: Select all
   +---------+---------+---------+
   | XY .  . | .  1  2 | .  3  4 |
   | .  1  3 | 4  .  . | 2  .  . |
   | .  4  2 | 3  .  . | 1  .  . |
   +---------+---------+---------+
   | .  2  1 | X  3  4 | .  .  . |
   | 3  .  . | 1  .  . | .  4  2 |
   | 4  .  . | 2  .  . | .  1  3 |
   +---------+---------+---------+
   | .  3  4 | .  .  . | Y  2  1 |
   | 1  .  . | .  2  3 | 4  .  . |
   | 2  .  . | .  4  1 | 3  .  . |
   +---------+---------+---------+

With r1c1b68:
Xr4c4 => Xr1c1, -Xr7c7
Yr7c7 => Yr1c1

Or with multi-links:
Code: Select all
   +---------+---------+---------+
   | *  *  * | *  1  2 | *  3  4 |
   | *  1  3 | 4  .  . | 2  .  . |
   | *  4  2 | 3  .  . | 1  .  . |
   +---------+---------+---------+
   | *  2  1 | *  3  4 | *  *  * |
   | 3  .  . | 1  .  . | *  4  2 |
   | 4  .  . | 2  .  . | *  1  3 |
   +---------+---------+---------+
   | *  3  4 | *  *  * | *  2  1 |
   | 1  .  . | *  2  3 | 4  .  . |
   | 2  .  . | *  4  1 | 3  .  . |
   +---------+---------+---------+

r147c147b168 / 2 ie. 4-link
21 truths: *-marked cells
20 links: 5 digits with 4 links each
rank -1, ie. contra.

Edit: I've had another look at 6-box rookeries (with three digits on diagonals). We can always morf the puzzle into this state:
Code: Select all
   +---------+---------+---------+
   | X  .  . | X  .  . | .  .  . |
   | .  X  . | .  X  . | .  .  . |
   | .  .  X | .  .  X | .  .  . |
   +---------+---------+---------+
   | X  .  . | .  .  . | X  .  . |
   | .  X  . | .  .  . | .  X  . |
   | .  .  X | .  .  . | .  .  X |
   +---------+---------+---------+
   | .  .  . | X  .  . | .  .  . |
   | .  .  . | .  X  . | .  .  . |
   | .  .  . | .  .  X | .  .  . |
   +---------+---------+---------+

Then by checking the diagonals in b9:

r7c7, r8c8, r9c9;
r7c8, r8c9, r9c7 and
r7c9, r8c7, r9c8
have solutions, there either are three hexagons or there is none, even when morfed there will be even number of diagonals in each direction.

r7c9, r8c8, r9c7;
r7c8, r8c7, r9c9 and
r7c7, r8c9, r9c8
don't have solutions, there is always one hexagon and odd number of diagonals in each direction.
marek stefanik
 
Posts: 354
Joined: 05 May 2021

Re: The hardest sudokus (new thread)

Postby eleven » Fri Jul 16, 2021 8:06 pm

Nice XY proof.

In it's diagonal form this pattern also could be spotted easily:
Code: Select all
   +---------+---------+---------+
   | .  .  . | .  3  4 | .  1  2 |
   | .  1  3 | 2  .  . | 4  .  . |
   | .  4  2 | 1  .  . | 3  .  . |
   +---------+---------+---------+
   | .  2  1 | .  .  . | .  3  4 |
   | 3  .  . | .  4  2 | 1  .  . |
   | 4  .  . | .  1  3 | 2  .  . |
   +---------+---------+---------+
   | .  3  4 | .  2  1 | .  .  . |
   | 1  .  . | 4  .  . | .  2  3 |
   | 2  .  . | 3  .  . | .  4  1 |
   +---------+---------+---------+

I wonder, if there are puzzles, where it would be useful (i guess no).

[Added:] Hm, a unique puzzle with this pattern is impossible. Wherever you have 1,2,3,4 given, it would destroy the pattern. In the 3 digit pattern above, those 3 digits can only be givens in one box.
eleven
 
Posts: 3082
Joined: 10 February 2008

Re: The hardest sudokus (new thread)

Postby marek stefanik » Sat Jul 17, 2021 12:13 am

It definitely can be useful, even though probably not when looking for very hard puzzles.

This puzzle, for example, simplifies to singles:
....3..127132...8..421..3.9.21....3.37..421..4..8132...34.21...1..4..62329.37..41
YZF_Sudoku rates it 8.2.

The hardest puzzle I was able to get (with a setting algorithm you can probably get a better one):
....3..127132...8..421.63.9.21....3.3...421..4.5.132...34.21...1..4..62329.3...41
YZF_Sudoku rates it 9.0.
With the trick it only requires a Skyscraper to finish.

SE might rate them differently.
marek stefanik
 
Posts: 354
Joined: 05 May 2021

PreviousNext

Return to General