The New Sudoku Players' Forum

[Ocean]

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.]

[ravel]

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).

[JPF]

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

[Ocean]

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?

[daj95376]

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?

IMHO to your first question:

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.

[tso]

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

[edit]
Susser 2.5.4 does not solve any of these at default settings.
http://www.madoverlord.com/projects/sudoku.t

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.

[ravel]

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

000500700020060040006001003900200400030000010007003008100700600050040070009008000
000800900070040050006007001800300700010000030004002009300100600040060020007005000
001030000800007003040900200070000500300006001004020060000009008060100700007050040
040050700007001060800900000060020400100600003005000070002009040300700008000030100

000001000010020030400500100006007003080030010200900400009000002070080060800300500
005003008060080070200000900004009002010030080300700600001005004030020010000100000
020004009008010030600300700040001005001030020000000100900200000080005003007060080
080060700300500080000002009001000000020030100500100040007003006030010800900400020

300050060002001000000300004900020010070800005004005900030600001800010090001007800
008700100090010008100006030009500400500008070010020009400003000000100200060050003
001000002030040000500600300007008001060010030100900800005009004080050070200100900
009001002070050080400900500008009001030010060100800700003006005000040030200000100


[Edit: numbers and list corrected]

[Viggo]

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

[ravel]

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

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.

[Mage]

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

[tso]

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.

[Ocean]

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)
001000002030000010400500300006007000080060030900800500004008009000040060200900800
001000002030040000500600700008007000000010030700500600005009004000050080200300900
001000002030040010500600000007008001020000030400500600005009003080000070300100900
001002003020030040000500600000004002070050080900300100008000000050060070700900300
001002003020040000500600200007008001030000020100900600009007004080000050000100700
001002003020040010500600000000007001030080020400500600005009002070000080300000900
001002003020040010500600000007008001030000020400500600005009000080000070700100900
#9-17. Outsiders: (r in the range 800-900).
001000002030000040500600300007008000000090030100500600005009001040080070200400900
001000002030020010400500300006007000000010030800400500009006008070040060200000900
001000002030040000500600300004007001000080030900200600000008009070020040200100800
001000002030040010500600300007008001020010080000500600005009000040030070800000900
001000002030040050200600000007005008060010020900700100004000006000080030700900800
001000002030040050600700000000003000020050080700600100006000000050080030900000400
001000002030040050600700000000008000040050030900600700006000000050030010800000900
001002003020040010500600200000007000080010020400500600005009008070000040800000900
001002003030040050600100700008001002000060040900500600007000000000010090100800400
#18. Finally one with 19 clues, even though it scored lower than the others (r=636).
000000001020030040500600000000007000030040010700500800005000000040010090800000600
#


[r.e.s.]

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

EDIT: Added quote; improved wording; added SudoCue results; improved formatting.

[ravel]

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]

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 18
7, 5, 8, 5, 7, 10, 12, 5, 4, 5, 15, 7, 7, 7, 5,12, 5, 3
5  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.