## The hardest sudokus

Everything about Sudoku that doesn't fit in one of the other sections
Inspired by tso's new wonderfully horrible creatures, I started a search in the diagonal pattern. Among the first 100000 three puzzles seem to stand out:
Code: Select all
`#01: r={938,954,956,985,999}000001000010020030400500100006007003080030010200900400009000002070080060800300500#02: r={968,974,980,983,1022}001000002030000010400500300003006001070080030900400500000008009060040020700100800#03: r={1027,1035,1060,1065,1076}001000002030040000500600300007008001060010030100900800005009004080050070200100900`

[The r's are counts similar to "suexrat9" (if I understood that one right) - counts of guesses during brute force solving, average of 100 randomized trials - for five different scrambled versions of the puzzles. Hopefully high r's in combination with the diagonal pattern can indicate hard puzzles - this is not always the case for other patterns. Puzzle #01 and #03 have a gsf-rating >95000, while #02 is lower.]
Ocean

Posts: 442
Joined: 29 August 2005

JPF,
none of your puzzles needed more than 2 steps.

Ocean,
i both love and hate the diagonal pattern
The fist and third of your puzzles needed 11 steps (even more in the standard order), the second 8 steps. For the first one no guess was found that would solve the puzzle with the implemented basic methods, only 5 of 154 false candidates from the first stuck grid could be eliminated, the third sudoku had one guess with singles, one needing other techniques and 10 out of 145 eliminations.

No 1 and 3 were not solved by susser 2.5.4 with standard settings, for no 2 it needed 4 times tabling and 3 times Bowman Bingo for the first number (!), then 3 times tabling and 10 comprehensive forcing chains to solve it.

Tso's 12-stepper had 20 of 133 possible eliminations (but that did not help much either).
ravel

Posts: 998
Joined: 21 February 2006

ravel wrote:JPF,
none of your puzzles needed more than 2 steps.
Thanks ravel.

I underestimated the complexity of the rating problem.
I think I've nearly understood your methodology.

Going back to easier puzzles for the moment...

JPF
JPF
2017 Supporter

Posts: 4383
Joined: 06 December 2005
Location: Paris, France

ravel wrote:The fist and third of your puzzles needed 11 steps (even more in the standard order), the second 8 steps. For the first one no guess was found that would solve the puzzle with the implemented basic methods, only 5 of 154 false candidates from the first stuck grid could be eliminated, the third sudoku had one guess with singles, one needing other techniques and 10 out of 145 eliminations.

No 1 and 3 were not solved by susser 2.5.4 with standard settings, for no 2 it needed 4 times tabling and 3 times Bowman Bingo for the first number (!), then 3 times tabling and 10 comprehensive forcing chains to solve it.

Tso's 12-stepper had 20 of 133 possible eliminations (but that did not help much either).

Thank you for evaluating the puzzles!
It seems that all had some interesting (non-common) properties.
Also satisfactory that the screening process could filter out three puzzles that made it into the top ten.

Two questions: What makes the diagonal pattern so special? Is it possible to come up with new logical solving methods that can crack the diagonal puzzles?
Ocean

Posts: 442
Joined: 29 August 2005

Ocean wrote:Two questions: What makes the diagonal pattern so special? Is it possible to come up with new logical solving methods that can crack the diagonal puzzles?

1) Sudoku is defined in rectangular relationships between row & columns .. with boxes thrown in for added complication.

2) Most techniques are based on interactions in (1) or TRUE/FALSE logic on bivalue cells or candidate pairs.

3) The inner-relationships between candidates in difficult diagonal puzzles defy (1) & (2) for the most part. This leaves only complex/convoluted advanced techniques to legitimately solve these puzzles. Some people, like myself, cheat and use brute-force techniques to find a weakness in the puzzles that can be capitalized upon.
daj95376
2014 Supporter

Posts: 2624
Joined: 15 May 2006

Code: Select all
`1) ...5..7...2..6..4...6..1..39..2..4...3.....1...7..3..81..7..6...5..4..7...9..8...2) .....1....1..2..3.4..5..1....6..7..3.8..3..1.2..9..4....9.....2.7..8..6.8..3..5.. 3) ..1.....2.3..4....5..6..3....7..8..1.6..1..3.1..9..8....5..9..4.8..5..7.2..1..9.. 4) 7.....4...2..7..8...3..8..9...5..3...6..2..9...1..7..6...3..9...3..4..6...9..1..5 `

#1) is the "12 step" 144: tso #7/31
#2) is Ocean's 11 step 165: Ocean #1/3
#3) is Ocean's 11 step 167: Ocean #3/3
#4) is the 10 step top1465 #77 "the toughest known"

Just for comparision purposes, here are ratings of these four puzzles from other sources:

Suexrat9 (gives slightly different ratings each time it's run):
http://magictour.free.fr/sudoku.htm

1) 694
2) 964
3)1043
4) 867

Into Sudoku 1.83:
http://www.intosudoku.com/

1) 11922
2) 21007
3) 24832
4) 12465

SudoCue 1.3.0.0:
http://www.sudocue.net/

1) Total score: 21638, solving rounds: 106
2) Total score: 32027, solving rounds: 122
3) Total score: 14370, solving rounds: 82
4) Total score: 13047, solving rounds: 86

Sudoku Explainer 1.1:
http://diuf.unifr.ch/people/juillera/Sudoku/Sudoku.html

1) 9.4 (out of 10)
2) 9.5
3) 9.9 (!)
4) 9.8

Susser 2.5.4 does not solve any of these at default settings.

1) Does not complete, solving only a single cell.
2) Does not complete, solving only a single cell.
3) Does not complete, solving only two cells.
4) Does not complete, solving only a single cell.

Adding "aggressive forces" and pins solves 1, 2 and 4, but NOT 3. Adding "sets and intersections" finally solves #3.

(As to why earlier versions of Susser might solve a puzzle when a newer version won't, my guess is that as he added more capabilities, the new version's defaut settings probably did not include the same heuristcs options as the old one.)

What other software will give numerical ratings similar to these?

My search found that the fewer clues a diagonal pattern had, the higher percentage of harder puzzles there were at various levels -- but at the same time, it was several times more difficult to find a puzzle with each fewer clue. I'd assume that the 18 cell diagonal patterns with 2 clues per row, column and box hide the hardest possible puzzles -- but they may be *very* hard to find with out smarter searches or by direct construction as they may be extremely rare -- the toughest 27's will be astronomically more common.

(Do some of the 17's fit the diagonal pattern and if so, could *they* be the toughest? This should be an easy enough test since there already is a large database.)

Viggo's comments on this subject earier in this thread seem logical to me.
Last edited by tso on Wed Jul 05, 2006 3:39 am, edited 1 time in total.
tso

Posts: 798
Joined: 22 June 2005

Thanks, tso, for the alternative ratings.
For the top 3 i also used a scrambled version and the reversed puzzles to get the minimum step count. The highest minimum steps i had for a version of the 3 puzzles were 16, 16 and 17. I would be interested, how the differences are in the ratings of the other programs.

Code: Select all
`000500700020060040006001003900200400030000010007003008100700600050040070009008000000800900070040050006007001800300700010000030004002009300100600040060020007005000001030000800007003040900200070000500300006001004020060000009008060100700007050040040050700007001060800900000060020400100600003005000070002009040300700008000030100000001000010020030400500100006007003080030010200900400009000002070080060800300500005003008060080070200000900004009002010030080300700600001005004030020010000100000020004009008010030600300700040001005001030020000000100900200000080005003007060080080060700300500080000002009001000000020030100500100040007003006030010800900400020300050060002001000000300004900020010070800005004005900030600001800010090001007800008700100090010008100006030009500400500008070010020009400003000000100200060050003001000002030040000500600300007008001060010030100900800005009004080050070200100900009001002070050080400900500008009001030010060100800700003006005000040030200000100`

[Edit: numbers and list corrected]
ravel

Posts: 998
Joined: 21 February 2006

ravel wrote:And we have a new leader !
No 7 is a very extreme puzzle. Though one guess (r1c2=4) could solve the puzzle with singles, it needed 12 steps.

The puzzle have 4 candidates in r1c2 and it can be solved by one guess (r1c2=4). Then this puzzle can be solved in 3 steps. The 3 steps are to eliminate the other three candidates in this cell.

Have I missed some point here?

/Viggo
Viggo

Posts: 60
Joined: 21 April 2006

Thanks for the link to Sudoku Explainer, tso. It seems to be a very good program (also running without ms windows).
The ratings are the same for the equivalent puzzles and look very trustable for me.

According to this rating the top list would be (i checked down to 6 steps):
9.9:
167: Ocean #3/3

9.8:
1: top1465 #77 (toughest)

9.5:
165: Ocean #1/3

9.4:
144: tso #7/31
140: tso #3/31
6: top1465 #280
8: top1465 #113
160: tso #26/31

Viggo wrote:Then this puzzle can be solved in 3 steps. The 3 steps are to eliminate the other three candidates in this cell.

Have I missed some point here?

The problem is, how the other 3 candidates can be eliminated.
ravel

Posts: 998
Joined: 21 February 2006

### Susser rating

Hi tso,

I noticed you use a very old version of Susser.

The latest one (2.5.4) solves the 4 puzzles with the following "rating" (e.g. max size of the generated table) :
1) 67509
2) 71990
3) 59141
4) 71182
Mage

Posts: 17
Joined: 20 March 2006
Location: France

### Re: Susser rating

Mage wrote:Hi tso,

I noticed you use a very old version of Susser.

The latest one (2.5.4) solves the 4 puzzles with the following "rating" (e.g. max size of the generated table) :
1) 67509
2) 71990
3) 59141
4) 71182

Oops. That was a typo. I have the latest version. I corrected my previous post.

I hadn't thought to look at the max size of table for a rating before. Makes sense.
tso

Posts: 798
Joined: 22 June 2005

Findings in a set of about half a million minimal puzzles in the diagonal pattern. The three previously reported had 25 to 24 clues. The eighteen new puzzles have 23/22/20/19 clues. Eleven of the puzzles have gsf-rating above 95000, while seven are below.
Code: Select all
`##Diagonal pattern puzzles.##1. Exceptionally highest score (r=1312). But with only 20 clues: is it still hard enough?001000002030040050600700000000008000020030040900600700006000000040010030800000900#2-8. (r=966/967/1079/941/960/918/954)001000002030000010400500300006007000080060030900800500004008009000040060200900800001000002030040000500600700008007000000010030700500600005009004000050080200300900001000002030040010500600000007008001020000030400500600005009003080000070300100900001002003020030040000500600000004002070050080900300100008000000050060070700900300001002003020040000500600200007008001030000020100900600009007004080000050000100700001002003020040010500600000000007001030080020400500600005009002070000080300000900001002003020040010500600000007008001030000020400500600005009000080000070700100900#9-17. Outsiders: (r in the range 800-900).001000002030000040500600300007008000000090030100500600005009001040080070200400900001000002030020010400500300006007000000010030800400500009006008070040060200000900001000002030040000500600300004007001000080030900200600000008009070020040200100800001000002030040010500600300007008001020010080000500600005009000040030070800000900001000002030040050200600000007005008060010020900700100004000006000080030700900800001000002030040050600700000000003000020050080700600100006000000050080030900000400001000002030040050600700000000008000040050030900600700006000000050030010800000900001002003020040010500600200000007000080010020400500600005009008070000040800000900001002003030040050600100700008001002000060040900500600007000000000010090100800400#18. Finally one with 19 clues, even though it scored lower than the others (r=636).000000001020030040500600000000007000030040010700500800005000000040010090800000600#`
Ocean

Posts: 442
Joined: 29 August 2005

tso wrote:
Code: Select all
`1) ...5..7...2..6..4...6..1..39..2..4...3.....1...7..3..81..7..6...5..4..7...9..8...2) .....1....1..2..3.4..5..1....6..7..3.8..3..1.2..9..4....9.....2.7..8..6.8..3..5.. 3) ..1.....2.3..4....5..6..3....7..8..1.6..1..3.1..9..8....5..9..4.8..5..7.2..1..9.. 4) 7.....4...2..7..8...3..8..9...5..3...6..2..9...1..7..6...3..9...3..4..6...9..1..5 `

#1) is the "12 step" 144: tso #7/31
#2) is Ocean's 11 step 165: Ocean #1/3
#3) is Ocean's 11 step 167: Ocean #3/3
#4) is the 10 step top1465 #77 "the toughest known"

Just for comparision purposes, here are ratings of these four puzzles from other sources [...]

ISTM that the rating should in principle not change when a puzzle is changed to any one of its symmetrically-equivalent versions. But with 180-degree rotation, this was NOT true of Trebor's Table size, SudoCue, nor suexrat9 (even when the latter was stabilised to two significant figures).

(Tso, I suspect you used suexrat9's default sample-size of 100, which isn't enough to remove the significant sampling variation that's due to its random sampling approach. For SudoCue, I suppose my results vary a bit from yours due to some minor settings being different.)

It WAS true of Sudoku Explainer's ratings, although this might not be the case for other puzzles -- because the solving-methods it used (the basis of its rating) DID change due to the rotation.

Here's a summary of the results, with '*' marking the highest rating in each column ...

Code: Select all
`                        Before / After 180-degree puzzle-rotation        ----------------------------------------------------------------------------Puzzle  Trebor's Tables [a]       SudoCue [b]      suexrat9 [c]  SudokuExplainer [d]------  -------------------  --------------------  ------------  ------------------- (1)       67509 / 65837*    106;21656 / 97;19991*  670 / 680      9.4 / 9.4 (2)      *71990 / 63464    *122;32027 / 85;14362   890 / 880      9.5 / 9.5 (3)       59141 / 64031      82;14370 / 88;15812  *890 / 930*    *9.9 / 9.9* (4)       71182 / 58723      86;13047 / 84;12861   830 / 820      9.8 / 9.8            [a] Tabling was performed after other applicable solving-methods.             [b] The format is Solving_rounds;Total_score.            [c] Rounded to two significant figures; sample-size = 2*10^5.            [d] Solving-methods changed, but not enough to change the rating.`

Here are the 180-degree rotated versions of the four puzzles (i.e., reversed-string):

Code: Select all
`(1') ...8..9...7..4..5...6..7..18..3..7...1.....3...4..2..93..1..6...4..6..2...7..5...(2') ..5..3..8.6..8..7.2.....9....4..9..2.1..3..8.3..7..6....1..5..4.3..2..1....1.....(3') ..9..1..2.7..5..8.4..9..5....8..9..1.3..1..6.1..8..7....3..6..5....4..3.2.....1..(4') 5..1..9...6..4..3...9..3...6..7..1...9..2..6...3..5...9..8..3...8..7..2...4.....7`

Last edited by r.e.s. on Wed Jul 05, 2006 6:41 pm, edited 10 times in total.
r.e.s.

Posts: 337
Joined: 31 August 2005

Thanks, i will check them tomorrow. Seem to be ultra hard again. This is the analysis of Sudoku Explainer to the first one:

Difficulty rating: 9,5 / 10
This Sudoku can be solved using the following logical methods:
..
1 x X-Wing
3 x Swordfish
1 x XYZ-Wing
2 x Turbot Fish
2 x Bidirectional Y-Cycle
1 x Bidirectional Cycle
7 x Forcing Chain
2 x Nishio Forcing Chains
1 x Region Forcing Chains
1 x Cell Forcing Chains
3 x Dynamic Cell Forcing Chains
22 x Dynamic Contradiction Forcing Chains
10 x Dynamic Region Forcing Chains
1 x Dynamic Contradiction Forcing Chains (+)
ravel

Posts: 998
Joined: 21 February 2006

Thanks r.e.s. for the analysis. As i expected there are rather different results for equivalent puzzles for SudoCue and susser (and my own ratings) - i assume the same for IntoSudoku. The suexrat ratings tend to be more relevant for programs than for humans.

So my favorite now is the Explainer. I tried several times, but never got a different rating for a scrambled puzzle. But i also noticed that the solution paths (numbers of chains of a type) differ. I am not sure, why this is possible, because all possible "easier" steps are done before a harder one (and there were no uniqueness reductions). The rating is based on the hardest step, where there also the length of the implication chain is taken into account (the author told me this, see here for the rating ranges of different techniques).

So eventually i want to reorder the list based on this rating in the future, because i think it is better and more transparent than mine - with some additional advantages:
- My program is very slow and needs hours for a list of super hard puzzles.
- The Explainer can be downloaded and runs on all platforms, so puzzle creators can check puzzles themselves.

This program is the first one (i know) that really solves all the toughies in a rather good way that avoids unnecessary monster chains (but does not omit unnecessary steps) and shows all steps needed in human readable (graphical) form. Thats also a bit sad for me like the chess programs that beat the best human players.

These are the ratings for Oceans puzzles. The last line shows the Explainer rating, where the "9." is omitted.
Code: Select all
`1  2  3  4  5   6   7  8  9 10  11 12 13 14 15 16 17 187, 5, 8, 5, 7, 10, 12, 5, 4, 5, 15, 7, 7, 7, 5,12, 5, 35  2  4  3  4   8   9  3  1  2   4  3  2  2  3  3  3 8.4`

Note that here are some differences between Explainer's and my rating, especially for #11 (9.4/15 steps) and #16 (9.3/12). But we had this with other rating systems also, none is perfect.

[Edit:] Since a 9.5-rated from the Explainers site was solved in 3 steps by my program, i will keep my rating.
ravel

Posts: 998
Joined: 21 February 2006

PreviousNext