The hardest sudokus

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

Postby daj95376 » Thu Aug 03, 2006 3:15 pm

In my FreeCell solver, I implemented a tree structure to eliminate checking redundant paths and to find short solutions. I even considered doing something similar in my Sudoko solver. However, having a shortest path for one step doesn't guarantee that it's the best path to choose. A longer path chosen early on may result in a critical elimination to where fewer paths are needed later. So, I dropped the idea.

Besides, unless everyone uses the same techniques in the same order to get to where the first chain is necessary, then it makes solution comparisons -- and ratings -- very difficult. I know this from reading the Big Fish thread. I implemented a rudementary Templates module and it resolves Coloring, Multi-Coloring, and (apparently) Big Fish. I'm very happy with its results, but that doesn't mean that others would accept it.

Actually, using the same techniques in the same order doesn't hold true, either. I tend to scan rows, columns, and boxes -- in that order -- for most techniques. However, I've noticed that Simple Sudoku will scan boxes (or candidate values) first in some cases. Thus, my solution differs from SS even for the same technique.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby gsf » Thu Aug 03, 2006 5:08 pm

daj95376 wrote:Actually, using the same techniques in the same order doesn't hold true, either. I tend to scan rows, columns, and boxes -- in that order -- for most techniques. However, I've noticed that Simple Sudoku will scan boxes (or candidate values) first in some cases. Thus, my solution differs from SS even for the same technique.

that's why the step counting threads { inferior ulterior superior } specify technique order, grouping, and batching
this may not lead to an optimal solution but it does make puzzle permutations and row/col/box application order a wash

i.e., for the current position loop through each technique group in order, and for the first
group that has a placement / elimination, record (but do not apply) all of the placements /
eliminations for all the techniques in the group, and then apply all of the placements /
eliminations in one batch
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby maria45 » Fri Aug 04, 2006 12:17 pm

Hello daj,
daj95376 wrote:...However, having a shortest path for one step doesn't guarantee that it's the best path to choose. A longer path chosen early on may result in a critical elimination to where fewer paths are needed later. So, I dropped the idea.

so, actually, you would not have to consider one chain alone, but all chains together to get the "shortest" solution.

Although, one might ask, what is the "best" solution. Of course, one short forcing chain is "better" or "more elegant" than one long forcing chain if the result is the same. But consider

a) a forcing chain with 21 steps, and the remaining puzzle falls into singles or
b) 3 short forcing chains, each with 5 steps, total 15 steps.

or reverse it:
a) a forcing chain with 15 steps, and the remaining puzzle falls into singles or
b) 3 short forcing chains, each with 7 steps, total 21 steps.

What is "shortest" in this cases?

So perhaps the more "human-like" solution except from people able to consider 21 steps in advance, would of course be the 3 forcing chains. But perhaps the single forcing chain feels more "elegant", because the puzzle is solved with this step.

The same holds true for complicated solutions. What is "better", 5 eliminations with forcing chains or 1 elimination by contradiction. And in this comparison you might again consider different lengths of forcing chains or contradictions. I somehow still feel that the contradictive technique is quite close to T&E, so I try to circumvent it.

Greetings, Maria
maria45
 
Posts: 54
Joined: 23 October 2005

Postby ronk » Fri Aug 04, 2006 1:13 pm

maria45 wrote:a) a forcing chain with 21 steps ...

How do you define a "step" for a forcing chain?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby daj95376 » Fri Aug 04, 2006 5:12 pm

maria45 wrote:so, actually, you would not have to consider one chain alone, but all chains together to get the "shortest" solution.

Yes ... but it's even more complicated. Consider a recent post by Mike Barker.

Code: Select all
Constraint Squirmbag: r1c389|r4c378|r7c1469|r8c12489|r9c249 => r6c8<>1
8....9...2..75..9...4...32..9.47........6..72..7.....5..2....3...5...8......86...
+------------------+---------------+------------------+
|     8     7 *136 |    2  34    9 |     5 *146  *146 |
|     2   136  136 |    7   5   34 |   146    9     8 |
|     9     5    4 |    6   1    8 |     3    2     7 |
+------------------+---------------+------------------+
|     5     9 *168 |    4   7    2 |   *16 *168     3 |
|   134   134  138 |  589   6  135 |   149    7     2 |
|  1346     2    7 |  189  39   13 |  1469 -148     5 |
+------------------+---------------+------------------+
|   *16     8    2 | *159  49 *145 |     7    3  *169 |
| *1346 *1346    5 | *139   2    7 |     8 *146 *1469 |
|     7  *134    9 |  *13   8    6 |     2    5   *14 |
+------------------+---------------+------------------+

Not every solver has every technique implemented and arranged in the same hierarchy. Since my solver doesn't handle Big Fish, I have to enable Templates to detect the same elimination. However, in the process, I detected [r6c8]<>6 as well. In any event, my solver also uses two elimination-by-contradiction (EBC) steps based on strong/weak links to solve this puzzle. Note: my solver only needed to examine bi-value cells for the EBCs. (Naked/Hidden Singles removed for brevity!)

Code: Select all
8....9...2..75..9...4...32..9.47........6..72..7.....5..2....3...5...8......86...

r6c8    <> 1     Templates -- Pass C
r6c8    <> 6     Templates -- Pass C
r1c4    =  2     [r1c4]=3 => [c7]=INVALID    (hidden,naked) = ( 0, 8)
    b8  -  4     Locked Candidate (1)
    b8  -  3     Locked Candidate (1)
r1c5    =  4     [r1c5]=3 => [r7c6]=EMPTY    (hidden,naked) = ( 2,10)

Now, consider if I had enabled XY-Chains and Forcing Chains before EBC in my hierarchy. Then I actually end up with a more complicated solution. Note: my solver still manages by just examining bi-value cells.

Code: Select all
8....9...2..75..9...4...32..9.47........6..72..7.....5..2....3...5...8......86...

r8c5    <> 4     Forcing Chains on [r1c4]
r8c5    <> 9     Forcing Chains on [r1c4]
    b8  -  4     Locked Candidate (1)
r7c1    =  1     [r7c1]=6 => [r7c5]=EMPTY    (hidden,naked) = ( 2,14)
  c4    -  123   Naked  Triple
r2c2    <> 3     Forcing Chains on [r1c9]
r4c8    <> 1     Forcing Chains on [r1c9]
    b1  -  3     Locked Candidate (1)
r1c4    =  2     [r1c4]=3 => [b6]=INVALID    (hidden,naked) = ( 0,20)
r2c2    =  1     [r2c2]=6 => [r6c6]=EMPTY    (hidden,naked) = ( 5,12)
r5      -  34    Naked  Pair
  c7    -  1     Locked Candidate (2)
r1c8    <> 4     XY-Chain on [r1c5]
r6c7    <> 1     XY-Chain on [r4c7]

Finally, consider if I disable XY-Chains, Forcing Chains, and Templates ... and go straight to EBC. My solver is forced to resolve a poly-value cell for the first elimination. But, it turns out that [r1c3] has a backdoor single. Two EBCs later and the puzzle is solved.

Code: Select all
8....9...2..75..9...4...32..9.47........6..72..7.....5..2....3...5...8......86...

r1c3    <> 1 (3) [r1c3]=1 => [r7c5]=EMPTY    (hidden,naked) = ( 3,16)
    b1  -  1     Locked Candidate (1)
  c7    -  1     Locked Candidate (2)
r1c3    =  3     [r1c3]=6 => [r7c5]=EMPTY    (hidden,naked) = ( 4,12)

So, finding a best solution to a difficult puzzle is essentially impossible because of many factors.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby Ocean » Tue Aug 15, 2006 10:09 am

I'm curious about this new pattern, with diagonal symmetry (two variations):
Code: Select all
 *-----------------*
 |. . .|. . 1|. . 2|
 |. 1 .|. 2 .|. 3 .|
 |4 . .|5 . .|. . .|
 |. . 4|. . .|. . 6|
 |. 7 .|. 3 .|. 1 .|
 |8 . .|. . .|9 . .|
 |5 . .|. . 8|. . .|
 |. . .|. 1 .|. 7 .|
 |. . 6|4 . .|5 . .|
 *-----------------*


Eighteen puzzles with Explainer rating from 9.4 to 10.0. If enough of them qualify we could almost double the number of known puzzles in this range. The "10.0-puzzle" is my first with this rating.

#
# M21/D21:
#
.....1..2.1..2..3.4..5.......4.....6.7..3..1.8.....9..5....8.......1..7...64..5.. # ER=10.0
.....1..2.1..3..4.5..6.......4.....1.7..8..3.2.....6..9....2.......4..7...35..8.. # ER=9.9
.....1..2.1..3..4.5..6.......4.....1.7..8..3.2.....9..9....2.......4..7...35..8.. # ER=9.9
.....1..2.1..3..4.5..6.......4.....1.7..8..3.2.....9..9....2.......4..7...37..8.. # ER=9.5
.....1..2.1..3..4.5..6.......4.....1.7..8..3.6.....8..2....6.......5..7...39..5.. # ER=9.4
.....1..2.1..3..4.5..6.......7.....8.9..4..1.8.....5..6....2.......1..9...87..3.. # ER=9.4
.....1..2.3..2..4.5..6.......4.....7.8..3..2.9.....5..1....9.......4..8...75..9.. # ER=9.4
.....1..2.3..2..4.5..6.......7.....3.1..4..8.6.....5..9....6.......7..3...85..9.. # ER=9.4
.....1..2.3..4..5.1..6.......5.....7.8..3..4.6.....1..9....6.......5..7...42..9.. # ER=9.4
.....1..2.3..4..5.6..2.......5.....3.7..8..4.2.....9..9....4.......5..7...41..6.. # ER=9.8
.....1..2.3..4..5.6..2.......5.....7.7..3..4.2.....6..1....8.......7..9...46..8.. # ER=9.5
.....1..2.3..4..5.6..7.......4.....8.9..5..3.8.....6..1....7.......3..9...82..4.. # ER=9.4
.....1..2.3..4..5.6..7.......5.....4.7..8..3.2.....6..1....6.......5..7...39..8.. # ER=9.5
.....1..2.3..4..5.6..7.......5.....4.8..2..9.7.....3..1....4.......5..8...96..7.. # ER=9.8
#
# M22/D22:
#
.....1..2.3..2..4.5..6.......3.....7.1..8..2.4..7..5..6....4.......6..1...73..9.. # ER=9.4
.....1..2.3..4..5.6..7.......4.....8.1..5..9.7..9..6..8....7.......9..4...93..1.. # ER=9.4
.....1..2.3..2..4.5..6.......6.....5.7..4..8.1..8..9..7....2.......3..1...89..6.. # ER=9.7
.....1..2.3..4..1.5..2.......6.....5.7..1..4.8..3..6..7....8.......9..8...36..7.. # ER=9.5
#

Also, some in the range 9.1-9.3:
#
# D21
#
.....1..2.2..3..4.5..6.......4.....5.6..2..3.7.....8..1....7.......5..6...38..7.. # ER=9.1
.....1..2.2..3..4.5..6.......4.....7.8..2..3.6.....9..1....3.......7..8...39..5.. # ER=9.3
.....1..2.3..4..5.1..6.......5.....4.4..3..7.6.....1..8....6.......5..4...92..8.. # ER=9.2
.....1..2.3..4..5.1..6.......7.....4.8..3..7.6.....1..9....6.......7..8...52..9.. # ER=9.3
.....1..2.3..4..5.6..7.......4.....8.9..5..7.8.....6..1....7.......3..9...82..4.. # ER=9.3
#
# D22
#
.....1..2.1..3..4.5..6.......3.....7.8..4..2.6..9..3..8....5.......1..5...73..6.. # ER=9.3
.....1..2.2..3..4.5..6.......3.....7.8..4..2.6..7..9..8....6.......5..8...59..3.. # ER=9.2
.....1..2.2..3..4.5..6.......7.....3.8..4..2.6..8..7..8....6.......9..5...97..1.. # ER=9.2
.....1..2.2..3..4.5..6.......7.....6.8..4..3.9..8..7..8....9.......2..7...57..1.. # ER=9.3
.....1..2.2..3..4.5..6.......7.....8.9..4..2.6..8..5..9....8.......9..3...67..1.. # ER=9.3
.....1..2.3..2..4.1..5.......6.....7.8..4..2.5..7..1..9....7.......3..8...86..9.. # ER=9.3
.....1..2.3..2..4.5..3.......6.....5.7..4..2.8..9..7..7....8.......9..8...16..3.. # ER=9.2
.....1..2.3..2..4.5..6.......3.....1.7..4..2.6..7..5..8....9.......7..8...75..9.. # ER=9.2
.....1..2.3..2..4.5..6.......3.....7.6..4..8.9..8..5..1....9.......7..9...73..6.. # ER=9.3
#
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby ravel » Tue Aug 15, 2006 9:10 pm

Wow, this was 10 times faster than i had expected new toughies:)
Very impressing, the first ER 10.0 puzzle !

I am away from my PC this week, so i cannot got through them before next week (and i suppose i will need some time).
Many thanks.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby ronk » Wed Aug 16, 2006 2:44 am

Ocean, that's an amazing set of puzzles. Six of them won't fall to elimination-by-contradiction (EBC) that is based on singles only. Not surprisingly, they are the puzzles with the highest Explainer ratings:

.....1..2.1..2..3.4..5.......4.....6.7..3..1.8.....9..5....8.......1..7...64..5.. # ER=10.0
.....1..2.1..3..4.5..6.......4.....1.7..8..3.2.....6..9....2.......4..7...35..8.. # ER=9.9
.....1..2.1..3..4.5..6.......4.....1.7..8..3.2.....9..9....2.......4..7...35..8.. # ER=9.9
.....1..2.3..4..5.6..2.......5.....3.7..8..4.2.....9..9....4.......5..7...41..6.. # ER=9.8
.....1..2.3..4..5.6..7.......5.....4.8..2..9.7.....3..1....4.......5..8...96..7.. # ER=9.8
.....1..2.3..2..4.5..6.......6.....5.7..4..8.1..8..9..7....2.......3..1...89..6.. # ER=9.7

Thanks for your contributions, Ron

P.S. As you listed above, that is #1, #2, #3, #10, #14, and #17.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby gsf » Wed Aug 16, 2006 3:48 am

here are 10 permutations of the 10.0 puzzle
could someone with more patience (or maybe a better jre) report the explainer ratings
thanks
Code: Select all
.....1..2.1..2..3.4..5.......4.....6.7..3..1.8.....9..5....8.......1..7...64..5..
.2....1.......4..53...1..2.1...7..3...9..8....6.4..........58....56....47......1.
...8..5....7.1.....5...4..6..1.3..7..9....8..6.......4..3.2..1.2..1..........54..
4.....5......2...1..13...2..6...54.....7...1.5.......8.4..6......71...3.8....9...
..5.....8.6...54......7..1.7...1..3...8..9....4.6........2....11...3..2...4...5..
.5..8.........17..6..4...5...1..23...4.5.........1...2..7..31...8.....9.4.......6
.7..1.........8..5..54...6..1..3.7....9.....86......4....5....42....1....3..2.1..
4.....6...8......9..73...1..5...8...6...4...5...1...7...12...3..4..5.........12..
5...6..4......58...7......1.3.1....2.....4.5...2...1....6.4.....1.7....39....8...
...5...8..5..6.4....7.....12......1....4..5....3..1..26...4......1..7..3.9.8.....
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby ronk » Wed Aug 16, 2006 5:09 am

gsf wrote:here are 10 permutations of the 10.0 puzzle
could someone with more patience (or maybe a better jre) report the explainer ratings

All your permutations also have Explainer rating 10.0

#
# Ocean's original diagonal symmetry puzzle with Explainer rating 10.0
#
.....1..2.1..2..3.4..5.......4.....6.7..3..1.8.....9..5....8.......1..7...64..5.. # ER=10.0
#
# gsf's 10 permutations
#
.....1..2.1..2..3.4..5.......4.....6.7..3..1.8.....9..5....8.......1..7...64..5.. # ER=10.0
.2....1.......4..53...1..2.1...7..3...9..8....6.4..........58....56....47......1. # ER=10.0
...8..5....7.1.....5...4..6..1.3..7..9....8..6.......4..3.2..1.2..1..........54.. # ER=10.0
4.....5......2...1..13...2..6...54.....7...1.5.......8.4..6......71...3.8....9... # ER=10.0
..5.....8.6...54......7..1.7...1..3...8..9....4.6........2....11...3..2...4...5.. # ER=10.0
.5..8.........17..6..4...5...1..23...4.5.........1...2..7..31...8.....9.4.......6 # ER=10.0
.7..1.........8..5..54...6..1..3.7....9.....86......4....5....42....1....3..2.1.. # ER=10.0
4.....6...8......9..73...1..5...8...6...4...5...1...7...12...3..4..5.........12.. # ER=10.0
5...6..4......58...7......1.3.1....2.....4.5...2...1....6.4.....1.7....39....8... # ER=10.0
...5...8..5..6.4....7.....12......1....4..5....3..1..26...4......1..7..3.9.8..... # ER=10.0
#

I was expecting at least some to have a lower rating.
Last edited by ronk on Wed Aug 16, 2006 6:53 am, edited 2 times in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ravel » Wed Aug 16, 2006 10:27 am

All 10 permutations had 10.0, though not the same number of chains (but all 4 x Dynamic Contradiction Forcing Chains +). I also tried them in susser and got 66947 - 85118 tabling implications (average 76436). This also are extremely high values.
So its a very promising candidate for a new number 1:)
ravel
 
Posts: 998
Joined: 21 February 2006

Postby maria45 » Wed Aug 16, 2006 11:50 am

Wow, Ocean, the 10.0.rating! Congratulations, well done. I'll try this soon, just yesterday took on your number 2 of these, with 9.9 rating. But, if I might ask you for numbering your puzzles now, as your number 1 yesterday is now number 2. Just for sake of reference, I'd like to indicate the right puzzle if I post a solution. Thank you.

Greetings, Maria
maria45
 
Posts: 54
Joined: 23 October 2005

Postby ab » Wed Aug 16, 2006 4:12 pm

ronk wrote:Ocean, that's an amazing set of puzzles. Six of them won't fall to elimination-by-contradiction (EBC) that is based on singles only.


Yes amazing puzzles Ocean. And because of the above you forced me to rewrite the message given by my brute force solver when it doesn't find a unique solution. it use to report categorically "not unique" and now says timidly "unique solution not found":!:
ab
 
Posts: 451
Joined: 06 September 2005

Postby tarek » Wed Aug 16, 2006 4:14 pm

That is an amazing puzzle Ocean......
To verify....It is THE most difficult puzzle I've come accross...

My puzzle had to through 18 simple contradiction elimination & 3 complex contradiction eliminations........with different permutations the number may differ...however I can't test test them for reasons similar to ronk's...

here are the 3 complex contradiction eliminations (the 1st 2 are in succession)....
Code: Select all
*-----------------------------------------------------------------*
| 3679   5689   3789  | 36789  46789  1     | 4678   45689  2     |
| 679    1      5789  | 6789   2      4679  | 4678   3      45789 |
| 4      23689  2389  | 5      6789   3679  | 178    689    1789  |
|---------------------+---------------------+---------------------|
| 1239   2359   4     | 1789   5789   279   | 37     258    6     |
| 269    7      59    | 2689   3      2469  | 248    1      458   |
| 8      2356   123   | 1267   456    2467  | 9      245    37    |
|---------------------+---------------------+---------------------|
| 5      2349   17    | 23679  679    8     | 12346  2469   1349  |
| 239    23489  2389  | 2369   1      5     | 23468  7      489   |
| 17     2389   6     | 4      79     2379  | 5      289    1389  |
*-----------------------------------------------------------------*
8 in r3c7 would lead to a contradiction (Complex Contradiction elimination)
*-----------------------------------------------------------------*
| 3679   5689   3789  | 36789  46789  1     | 4678   45689  2     |
| 679    1      5789  | 6789   2      4679  | 4678   3      45789 |
| 4      23689  2389  | 5      6789   3679  | 17     689    1789  |
|---------------------+---------------------+---------------------|
| 1239   2359   4     | 1789   5789   279   | 37     258    6     |
| 269    7      59    | 2689   3      2469  | 248    1      458   |
| 8      2356   123   | 1267   456    2467  | 9      245    37    |
|---------------------+---------------------+---------------------|
| 5      2349   17    | 23679  679    8     | 12346  2469   1349  |
| 239    23489  2389  | 2369   1      5     | 23468  7      489   |
| 17     2389   6     | 4      79     2379  | 5      289    1389  |
*-----------------------------------------------------------------*
2 in r6c3 would lead to a contradiction (Complex Contradiction elimination)
*-----------------------------------------------------------------*
| 3679   5689   3789  | 36789  46789  1     | 4678   45689  2     |
| 679    1      5789  | 6789   2      4679  | 4678   3      4589  |
| 4      23689  2389  | 5      6789   3679  | 17     689    1789  |
|---------------------+---------------------+---------------------|
| 1239   2359   4     | 1789   5789   279   | 37     258    6     |
| 269    7      59    | 2689   3      2469  | 248    1      458   |
| 8      2356   13    | 1267   456    2467  | 9      245    37    |
|---------------------+---------------------+---------------------|
| 5      2349   17    | 23679  679    8     | 12346  2469   1349  |
| 239    23489  2389  | 2369   1      5     | 23468  7      489   |
| 17     2389   6     | 4      79     2379  | 5      289    1389  |
*-----------------------------------------------------------------*
7 in r7c5 would lead to a contradiction (Complex Contradiction elimination)

I also came accross this wonderful step
Code: Select all
*-----------------------------------------------------------------*
| 3679   5689   389   |-36789 *46789  1     |%48     45689  2     |
| 679    1      589   | 6789   2      4679  | 468    3      4589  |
| 4      23689  2389  | 5     *689    369   | 17     689    17    |
|---------------------+---------------------+---------------------|
| 239    2359   4     | 1      5789   279   | 37     58     6     |
| 69     7      59    | 689    3      469   | 2      1      458   |
| 8      2356   1     | 267    456    2467  | 9      45     37    |
|---------------------+---------------------+---------------------|
| 5      2349   7     | 2369  *69     8     | 1346   2469   1349  |
| 239    23489  2389  | 2369   1      5     | 3468   7      489   |
| 1      2389   6     | 4     *79     2379  | 5      289    389   |
*-----------------------------------------------------------------*
Eliminating 8 from r1c4(ALS-XZ A=46789 in r1379c5 B=48 in r1c7  x=4 z=8, a classic VWXYZ wing)

[Edit: Typo corrected]

tarek
Last edited by tarek on Wed Aug 16, 2006 7:09 pm, edited 1 time in total.
User avatar
tarek
 
Posts: 2650
Joined: 05 January 2006

Postby daj95376 » Wed Aug 16, 2006 7:17 pm

[Edit: deleted] Incorrect !!!
Last edited by daj95376 on Wed Aug 16, 2006 7:15 pm, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

PreviousNext

Return to General