The hardest sudokus

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

Postby coloin » Wed Mar 21, 2007 8:03 am

Thanks also......
I dont think suexrat9 works well in some cases.
Note I edited the one morph so st.patrick 17>16,16>15.

There are many others with a similar suexrat9 rating that I didnt post!

Isomorphic puzzles should have the same SE - but I await the trial of isomorphic 10.8s.

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby StrmCkr » Wed Mar 21, 2007 8:15 am

Code: Select all
5.......9
.2.1...7.
..8...3..
.4.2.6...
....5....
...7.8.1.
3.....8..
.6...4.2.
..9.....5

st-patrick 16 {edited casuse gsf changed the number of the puzzle}


Analysis results
Difficulty rating: 10.9
This Sudoku can be solved using the following logical methods: 58 x Hidden Single 1 x Naked Single 6 x Pointing 2 x Hidden Pair 1 x Swordfish 4 x Hidden Triplet 1 x XYZ-Wing 1 x Turbot Fish 6 x Forcing Chain 1 x Nishio Forcing Chains 4 x Region Forcing Chains 4 x Cell Forcing Chains 4 x Dynamic Cell Forcing Chains 6 x Dynamic Contradiction Forcing Chains 5 x Dynamic Region Forcing Chains 2 x Dynamic Contradiction Forcing Chains (+) 2 x Dynamic Region Forcing Chains (+ Forcing Chains) 11 x Dynamic Contradiction Forcing Chains (+ Forcing Chains) 3 x Dynamic Contradiction Forcing Chains (+ Multiple Forcing Chains)


also the issomophric 10.8 puzzles all r 10.8 ratd
Last edited by StrmCkr on Wed Mar 21, 2007 3:47 pm, edited 1 time in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 647
Joined: 05 September 2006

Postby ravel » Wed Mar 21, 2007 2:23 pm

For my program nr 14 in the list gsf posted (the original one by m_b_metcalf) is the hardest with 16 points, the others have ratings between 10 and 14.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby gsf » Thu Mar 22, 2007 12:18 am

I searched the forums to no avail ...
can SE rate a list of puzzles in batch mode?
if so what is the java invocation?
thanks
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby RW » Thu Mar 22, 2007 5:22 am

Nicolas Juillerat wrote:Included my old testing routines in the .jar file. There is now an
unsupported way of analysing many Sudokus at once:
java -cp SudokuExplainer.jar diuf.sudoku.test.Tester sudoku.txt result.txt
where "sudoku.txt" is a file with Sudokus, one line of 81 digits per puzzle;
and "result.txt" is the file in which analysis results are saved.
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby gsf » Thu Mar 22, 2007 5:40 am

RW wrote:
Nicolas Juillerat wrote:Included my old testing routines in the .jar file. There is now an
unsupported way of analysing many Sudokus at once:
java -cp SudokuExplainer.jar diuf.sudoku.test.Tester sudoku.txt result.txt
where "sudoku.txt" is a file with Sudokus, one line of 81 digits per puzzle;
and "result.txt" is the file in which analysis results are saved.

thanks RW -- got that to work
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby coloin » Thu Mar 22, 2007 12:00 pm

Thanks for you efforts
We now have a number of ways to grade puzzles - not just the hardest step but also an attempt to summate the many hard steps in some puzzles.

I drew a blank on the unavoidable front.......Analysing m_b_metcalfs puzzle not surprizingly there were no insertable clues when you looked at the grid solutions of each [n-1] clues where n = the given clues. When you looked at each clue and the unavoidable sets that they uniquely occupied they envolved all the non given clues

In m_b_metcalf, looking at the clue with the least solutions - the 2 in r4c6 [82 grid solutions] there were 5 unavoidable sets which had between 30 and 50 clues. Of note there didnt tend to be the small unavoidables that you normally have !. The symmetrical nature of the clues must support these large sets. I cant see a way of using this however.

If all these puzzles are difficult because of the chains couldnt we use a more functional method of analysis.

My [sadman] graphical solver solves these difficult puzzle by systematiclly forward tracking on the remaining pencil marks - it takes about 30 seconds with m_b_metcalf's puzzle and 15 seconds with St.Patrick1. This tends to appromimate well to SE !

Here is another variation, possibly up there
Code: Select all
+---+---+---+
|5..|...|..9|
|.2.|1..|.7.|
|..8|...|3..|
+---+---+---+
|.4.|2.7|...|
|...|.3.|...|
|...|.46|.1.|
+---+---+---+
|..9|...|8..|
|.6.|..4|.2.|
|3..|...|..5|
+---+---+---+   SE 10.8  [Seamus5] or [529148#1]

+---+---+---+
|5..|...|3..|
|.2.|1..|.7.|
|..8|...|..9|
+---+---+---+
|.4.|..7|...|
|...|821|...|
|...|6..|.1.|
+---+---+---+
|3..|...|8..|
|.6.|..4|.2.|
|..9|...|..5|
+---+---+---+  SE  11.1  [Edmund5] or [295208#1]

Code: Select all
5.......9.2.1...7...8...3...4.......................1...3...8...6...4.2.9.......5[m_b_m]
5.....3...2.1...7...8.....9.4.......................1.3.....8...6...4.2...9.....5 [Edmund]
5.......9.2.1...7...8...3...4.......................1...9...8...6...4.2.3.......5 [Seamus]
5.......9.2.1...7...8...3...4.......................1.3.....8...6...4.2...9.....5 [Patrick]

295376 sol.
295208 sol.
529148 sol.
414054 sol.


I wonder how many different combinations of Box 3&7 we would have to try....
Last edited by coloin on Wed Apr 04, 2007 6:17 pm, edited 4 times in total.
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby m_b_metcalf » Thu Mar 22, 2007 3:35 pm

coloin wrote:The symmetrical nature of the clues must support these large sets.

Coloin,
There's another puzzle with symmetric clues and values here for your consideration (only SE 7.2, though:( ).

Regards,

Mike Metcalf
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8335
Joined: 15 May 2006
Location: Berlin

Postby daj95376 » Thu Mar 22, 2007 5:38 pm

This is probably not relevant, but ...

In the Patterns Game thread, JPF and m_b_metcalf supplied these four puzzles with the same pattern of givens but increasing difficulty to solve by changing the givens. Below is the sorted counts of the number of initial templates in these puzzles ... and Seamus5.

Code: Select all
4.......5.9.7...2...2...4...8.1.4.......6.......2.5.1...1...2...7...8.6.5.......8
~~~~~
<2> =     4
<8> =     7
<5> =     8
<4> =    16
<1> =    27
<7> =    56
<6> =   130
<9> =   556
<3> =  2424
~~~~~

Code: Select all
4.......5.7.3...6...2...4...8.1.4.......7.......2.5.1...1...2...3...8.5.5.......8
~~~~~
<5> =     4
<8> =     7
<2> =     8
<4> =    16
<1> =    27
<3> =    56
<7> =   130
<6> =   556
<9> =  2424
~~~~~

Code: Select all
1.......2.3.4...5...2...6...7.3.6.......5.......8.2.4...6...7...4...7.9.9.......8
~~~~~
<4> =     4
<7> =     7
<6> =     9
<2> =    16
<8> =    99
<3> =   130
<5> =   130
<9> =   130
<1> =   326
~~~~~

Code: Select all
7.......3.9.4...8...1...5...8.9.5.......3.......2.8.6...5...1...6...9.4.3.......7
~~~~~
<3> =     6
<5> =     9
<9> =    18
<8> =    20
<1> =    28
<7> =    28
<4> =    56
<6> =    56
<2> =   710
~~~~~

Code: Select all
Seamus5:

5.......9.2.1...7...8...3...4.2.7.......3........46.1...9...8...6...4.2.3.......5
~~~~~
<3> =    11
<2> =    16
<4> =    16
<5> =    29
<8> =    29
<1> =    32
<9> =    55
<6> =   148
<7> =   168
~~~~~

I wonder how difficult a puzzle with nearly identical counts might be to solve.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby gsf » Thu Mar 22, 2007 6:39 pm

daj95376 wrote:In the Patterns Game thread, JPF and m_b_metcalf supplied these four puzzles with the same pattern of givens but increasing difficulty to solve by changing the givens. Below is the sorted counts of the number of initial templates in these puzzles ... and Seamus5.

I'm guessing initial means before guessing/backtracking?
but what kind of templates are you counting?
if they're rookery templates then I have some debugging to do ...
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby daj95376 » Thu Mar 22, 2007 7:31 pm

gsf wrote:
daj95376 wrote:In the Patterns Game thread, JPF and m_b_metcalf supplied these four puzzles with the same pattern of givens but increasing difficulty to solve by changing the givens. Below is the sorted counts of the number of initial templates in these puzzles ... and Seamus5.

I'm guessing initial means before guessing/backtracking?
but what kind of templates are you counting?
if they're rookery templates then I have some debugging to do ...

I counted rookery templates for the initial puzzles. It seemed the only fair way to compare them. However, I was tempted to reduce the puzzles using basic techniques first. If your results don't match mine, then I'd definitely like to go to private messages to see if we can find the discrepancy.

BTW: I'm thinking that summing the three/four smallest counts might be a rough way to measure puzzle difficulty. Another comparision option might be the lowest count combined with the standard deviation for all counts. Just letting my thoughts wander.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby coloin » Fri Mar 23, 2007 12:34 am

Interesting indeed

I think its single clue templates - 46656 9 clue patterns possible

Of which 1 pattern per clue solves the puzzle

I suppose difficult to know when basic technigues stop !!!

Code: Select all
+---+---+---+
|5..|...|..9|
|.2.|1..|.7.|
|..8|...|3..|
+---+---+---+
|.4.|2.6|...|
|...|.5.|...|
|...|7.8|.1.|
+---+---+---+
|3..|...|8..|
|.6.|..4|.2.|
|..9|...|..5|
+---+---+---+   st.patrick 16


I thought st.patrick 16 was a good average grid solution puzzle - and it tops gsf's gsfQ rating

It just happens to be nearly the same pattern as yours !

So how does it score ?

I think youve showed that low numbers and high numbers reflect easy puzzles......

Degree of difficulty may be proportional to 1/Standard deviation

We will no doubt see.....

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby daj95376 » Fri Mar 23, 2007 2:24 am

Excerpt (slightly edited) from private message with gsf.

Let me give a lengthy explanation ... starting with my terminology so that you know for sure where I'm coming from.

Rookery/Rookeries: 46,656 uniquely valid ways to place a digit in nine cells on a 9x9 Sudoku grid. Completely independent of the digit or the state of any puzzle.

Templates: A set of nine rookery lists that accurately reflect the state of a puzzle at a particular time while solving it.

Here's what I did to report the values in my post.

1) For digit <n>, I eliminated any entries in its list that did not include all of the given cells for it.

2) Then I eliminated any entries in the list that included cells for the other givens in the puzzle.

3) The number of entries remaining in the list for <n> was the *count* that I reported for it.

4) NO ATTEMPT was ever made to actually solve the puzzle with Templates.

===== ===== ===== ===== ===== st.patrick 16

Code: Select all
5.......9.2.1...7...8...3...4.2.6.......5.......7.8.1.3.....8...6...4.2...9.....5
~~~~~
<5> =     8
<8> =    12
<2> =    16
<1> =    32
<4> =    32
<3> =    38
<9> =    38
<6> =   130
<7> =   130
~~~~~


Footnote: gsf and I managed to iron everything out and reach agreement.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby coloin » Wed Apr 04, 2007 11:06 pm

The last posts were interesting.......perhaps the lack of furthur posts means that it wasnt accurate enough ?

I had thought it would be influenced by
1 number of clues in the puzzle
2 a puzzle only having 8 clue values present.

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby daj95376 » Thu Apr 05, 2007 1:20 am

coloin wrote:The last posts were interesting.......perhaps the lack of furthur posts means that it wasnt accurate enough ?

I had thought it would be influenced by
1 number of clues in the puzzle
2 a puzzle only having 8 clue values present.

I believe that the total number of candidates present in a puzzle, after initial Singles have been found, helps dictate the puzzle's general difficulty level because it often limits the number of fundamental techniques that can be applied. This goes along (in general) with (1) & (2) in your list. Of course, there's a lot more to creating a difficult puzzle.

I didn't make any further posts on the topic because I don't have a collection of puzzles to review using template counts. I was hoping that someone would provide a sample set of puzzles to review ... and ideas on how to analyze the counts to see if anything meaningful exists.

Since there weren't any further comments, I assumed there wasn't any interest and dropped the idea.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

PreviousNext

Return to General