The New Sudoku Players' Forum

[coloin]

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

[eleven]

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.

[mith]

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.

[marek stefanik]

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.

[dobrichev]

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.

[coloin]

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|
 +---+---+---+     +---+---+---+      +---+---+---+   

[marek stefanik]

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.

[eleven]

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.

[marek stefanik]

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.

[dxSudoku]

For this one:
1 2 . | 4 . . | 3 . .
3 . . | . 1 . | . 5 .
. . 6 | . . . | 1 . .
-------+-------+------
7 . . | . 9 . | . . .
. 4 . | 6 . 3 | . . .
. . 3 | . . 2 | . . .
-------+-------+------
5 . . | . 8 . | 7 . .
. . 7 | . . . | . . 5
. . . | . . . | . 9 8

I made it harder by setting R6C9 to have a value of 1:

Rating Program: gsf's sudoku q1
Rating: 99529
Poster: eleven
Label: HardestSudokusThread-02085;Discrepancy
1 2 . | 4 . . | 3 . .
3 . . | . 1 . | . 5 .
. . 6 | . . . | 1 . .
-------+-------+------
7 . . | . 9 . | . . .
. 4 . | 6 . 3 | . . 1
. . 3 | . . 2 | . . .
-------+-------+------
5 . . | . 8 . | 7 . .
. . 7 | . . . | . . 5
. . . | . . . | . 9 8

At least it made it harder on the solver I use.

Here's the hardest puzzle I've ever seen:

. . 9 | . . . | 2 . .
. 8 . | 5 . . | . 1 .
7 . . | . . . | , . 6
-------+-------+------
. . 6 | . 9 . | . . .
. 5 . | 8 . . | 3 . .
4 . . | . . 7 | . . .
-------+-------+------
. . . | . . 4 | . . 9
. 3 . | . 1 . | . 8 .
. . . | 2 . . | 5 . .

[m_b_metcalf]

Here's the hardest puzzle I've ever seen:

For the curious:

Code: Select all

..9...2...8.5...1.7.......6..6.9.....5.8..3..4....7........4..9.3..1..8....2..5..  ED=10.7/10.7/3.4

Hard, but not that hard by the standards of this thread, with its recent posts of 11.8.

Regards,

Mike

[dxSudoku]

Here's the hardest puzzle I've ever seen:

For the curious:

Code: Select all

..9...2...8.5...1.7.......6..6.9.....5.8..3..4....7........4..9.3..1..8....2..5..  ED=10.7/10.7/3.4

Hard, but not that hard by the standards of this thread, with its recent posts of 11.8.

Regards,

Mike

I'm not using the same software as you. I'm using Hodoku which is probably not as high-tech as what you guys are using. But in Hodoku, the 11.8 ones clocked in at a difficulty level of about 35,000. The one I posted has a difficulty level of 39806. I guess it depends on how you weight difficulty levels for the required puzzle-solving techniques as to how a constellation of givens is scored.

[marek stefanik]

Hodoku takes the point value of each step and sums them up, whereas SE uses Nested Dynamic Chains (for the most part) and gives the rating of the hardest step (depending on the total length of the chains used).

Since Hodoku needs brute force to solve these puzzles, giving the same value every time, it will rate a puzzle higher when it gets in a few nets before having to use the bruteforce.

[denis_berthier]

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.

He came up with a proof, but not simpler than those already provided.

[denis_berthier]

Hodoku takes the point value of each step and sums them up, whereas SE uses Nested Dynamic Chains (for the most part) and gives the rating of the hardest step (depending on the total length of the chains used).

Summing up the steps is probably the dumbest way of computing the rating of a full resolution path.
The complexity of a step of length n increases as expk(n). The only kind of sum that could make sense is sum(expk(length (step))), for some k to be determined.