## The hardest sudokus

Everything about Sudoku that doesn't fit in one of the other sections
m_b_metcalf wrote:Is some recalibration called for?
The main problem i have with my rating is, that changing the parameter, when to search for subnets (the most time consuming step) always gives worse results for some (but different) puzzles and i dont have an argument, that this or that value would be more justified. So in my current top list i show the minimum points from four different runs, but it takes me too much time to do that for all puzzles.

Up to Mauricio's symmetrical puzzles and now yours the sudokus with very high Explainer rating always have been in my top list also (i only remember one more exception, a 10.1 puzzle by RW). Of course there must be a difference between ER and my rating, because the Explainer only rates the hardest step, while i take the "shortest solution" for the rating. But i agree, that the hardest step is underrepresented in my rating and i am thinking of giving extra points for longer subnet steps. Of course then i will have to recalculate the list, because other solutions would become "better".

For the moment here is a list of puzzles with highest ER, as far as i found them in this thread:
Code: Select all
`11.4:m_b_metcalf:500000009020100070008000300040702000000050000000006010003000800060004020900000005StrmCkr:50000000902010007000800030004000200000005000000070601000300080006000402090000000511.2:Ocean's New Year's present for RW00000102030004050000060000700200000108009003040000080050000200009003040000670000011.1:dml 1/0700300000940000002008060010020000400009080000700503000000090080000000503007001000611.0:Mauricio's non minimal puzzle (62 non isomorphic minimals):60000205952004001000350020030019450001065803000527300100400510003002004575040000810.9:Some more puzzles by Mauricio:30000500204001003000900080050009000002060804000420000500600170001003002040050000110000500404002003000800070050010000003060801000007300500900260001004002020050000370000000602003001000150040000019050004060002000527300000200530003001004080000000910050000407000006000203010002019000500400820050007300000301040008000009020000500310.8:dml 3/07003400080000009200000060001007010000060002000500800040010000900800000030004500007Another one by Mauricio:100040030000007004005800700002500080600090002030000400003006000700200000060080001`
ravel

Posts: 998
Joined: 21 February 2006

ravel wrote:For the moment here is a list of puzzles with highest ER, as far as i found them in this thread:

For the record, here are the two with SE = 10.7, gsfr = 99992 (but maybe they're isomorphs):
Code: Select all
`500000009020100060008000300040702000000090000000506010003000800070004020900000005300000004080700090006000500010908000000060000000507020005000600070001080400000003`

Regards,

Mike Metcalf

m_b_metcalf
2017 Supporter

Posts: 8416
Joined: 15 May 2006
Location: Berlin

Can I know about these puzzles' solving method result by SE?

m_b_metcalf wrote:
Code: Select all
`11.4:m_b_metcalf:500000009020100070008000300040702000000050000000006010003000800060004020900000005StrmCkr:50000000902010007000800030004000200000005000000070601000300080006000402090000000511.2:Ocean's New Year's present for RW00000102030004050000060000700200000108009003040000080050000200009003040000670000011.1:dml 1/0700300000940000002008060010020000400009080000700503000000090080000000503007001000611.0:Mauricio's non minimal puzzle (62 non isomorphic minimals):60000205952004001000350020030019450001065803000527300100400510003002004575040000810.9:Some more puzzles by Mauricio:30000500204001003000900080050009000002060804000420000500600170001003002040050000110000500404002003000800070050010000003060801000007300500900260001004002020050000370000000602003001000150040000019050004060002000527300000200530003001004080000000910050000407000006000203010002019000500400820050007300000301040008000009020000500310.8:dml 3/07003400080000009200000060001007010000060002000500800040010000900800000030004500007Another one by Mauricio:100040030000007004005800700002500080600090002030000400003006000700200000060080001`
Eioru

Posts: 182
Joined: 16 August 2006

11.4:
m_b_metcalf:
500000009020100070008000300040702000000050000000006010003000800060004020900000005
StrmCkr:
500000009020100070008000300040002000000050000000706010003000800060004020900000005

solving methods's aren't directly disscussed as there still debated on..

the method of steps is listed on the previous page (not in detail) used for solving each of these two.

this one is for mine.
[Added:] This is Explainers output for the variant (ER 11.4):
61 Hidden Single
4 Pointing
3 Claiming
4 Naked Pair
1 X-Wing
3 Hidden Pair
2 Naked Triplet
1 Swordfish
2 XY-Wing
3 Bidirectional Y-Cycle
3 Turbot Fish
4 Bidirectional Cycle
14 Forcing Chain
2 Nishio Forcing Chains
7 Region Forcing Chains
1 Cell Forcing Chains
1 Dynamic Cell Forcing Chains
1 Dynamic Double Forcing Chains
6 Dynamic Region Forcing Chains
5 Dynamic Contradiction Forcing Chains (+)
6 Dynamic Contradiction Forcing Chains (+ Forcing Chains)
6 Dynamic Contradiction Forcing Chains (+ Multiple Forcing Chains)

and mikes puzzle.
A very difficult and interesting puzzle. It seems to require nested chains with multiple inferences. I have not seen this before.

It is still possible to rate this puzzle with the current version of the Sudoku Explainer. But you need to start the .jar file from a command line, and to use the "-Xmx" option to tell the Java VM to use more memory (by default it only uses a fraction of the available memory). For instance:

java -Xmx500m -jar SudokuExplainer.jar

starts the application and tells the Java VM to use at most 500MB. This should be enough to solve the puzzle.

By the way, if you have installed the full Java JDK (not only the JRE), you may want to use the java command from the jdk, and to also add the "-server" option: the GUI gets less responsive but the long analyses run faster (about 2h20 instead of 3h15 on my computer).

Difficulty rating: 11.4

57 x Hidden Single
2 x Direct Hidden Pair
1 x Naked Single
5 x Pointing
2 x Naked Pair
1 x X-Wing
3 x Hidden Pair
2 x Naked Triplet
1 x Swordfish
1 x XY-Wing
1 x BUG type 1
1 x Forcing X-Chain
1 x Bidirectional Cycle
8 x Forcing Chain
2 x Nishio Forcing Chains
14 x Region Forcing Chains
5 x Cell Forcing Chains
1 x Dynamic Cell Forcing Chains
7 x Dynamic Contradiction Forcing Chains
3 x Dynamic Region Forcing Chains
3 x Dynamic Contradiction Forcing Chains (+)
11 x Dynamic Contradiction Forcing Chains (+ Forcing Chains)
2 x Dynamic Region Forcing Chains (+ Forcing Chains)
5 x Dynamic Contradiction Forcing Chains (+ Multiple Forcing Chains)
2 x Dynamic Region Forcing Chains (+ Dynamic Forcing Chains)
4 x Dynamic Contradiction Forcing Chains (+ Dynamic Forcing Chains)

as for the other one's in this link.
http://forum.enjoysudoku.com/viewtopic.php?t=5194

there is a listing of most of the other puzzles and how to solve them. (all using contradictions subnets. found in my post.
Some do, some teach, the rest look it up.

StrmCkr

Posts: 647
Joined: 05 September 2006

ronk wrote:
udosuk wrote:Where he later found a cousin by swapping r4c4 & r6c6:
Code: Select all
`5.......9.2.1...7...8...3...4.6.2.......5.........7.1...3...8...6...4.2.9.......5`

Wouldn't that be a reflection about the anti-diagonal making puzzles 1 & 2 isomorphic?

I may have mis-identified the anti-diagonal. Sudopedia defines it to run "from left-top to right-bottom". However, that definition is not consistent with the orientation of an anti-diagonal matrix.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

### re: diagonal

ronk wrote:I may have mis-identified the anti-diagonal.

Sudopedia defines it to run "from left-top to right-bottom".

However, that definition is not consistent with the orientation of an anti-diagonal matrix.

Sudopedia is wrong

Wikipedia is more mature,
and they got it right --
the main diagonal starts at r1c1 --
Wikipedia wrote:
the main diagonal
is the diagonal which runs from the top left to the bottom right

Pat

Posts: 3448
Joined: 18 July 2005

Its about time we finally get to the bottom of what makes our hard sudokus hard...- we cant really quantify our ratings until we know this......

The 20 clue from m_b_metcalf has 20 given clues and 61 insertable clues.
Code: Select all
`5.......9.2.1...7...8...3...4.7.2.......5.........6.1...3...8...6...4.2.9.......5     SE 11.4`
It is the hardest according to the SE ratings.....

Lets break it down into the unavoidables......

The sudoku has N number of unavoidables [size 4 - 63][possibly more than 50000 at a guess]
All the unavoidable sets are covered by the 20 given clues. The vast majority of the unavoidable sets are covered by more than one clue.
Each clue covers uniquely a number [n] of unavoidable sets of size [x]
n must be greater than 1 [EDIT - at least 1] to be an essential clue in a minimal sudoku puzzle.

The number of grid solutions for each clue is larger than average but not extraordinary.[This is more a function of the other grid solutions which are irrelevant to the unique grid solution of our puzzle]

If we could look at the unavoidable sets which are uniquely covered [by each clue]

Is n greater than expected ?
Is the average size of x large ?

It would appear on a superficial glance that the sole effect of each given clue reaches out to every empty cell so I think both n and x will tend to be larger than normal.

We have 20 given clues and 61 [correct] insertable clues.

This will give 1830 [61*60 / 2] ways to insert 2 [back-door correct] clues [non-minimally]

I have added two clues - here is one of the easiest, one of the hardest and the original minimal puzzle for comparison.
Code: Select all
`suexrat9                                                                                      SE  59 ,  5.......9.2.1.9.7...8...3...4.7.2.......5.........6.1...3...8...6...4.2.9......45     SE 1.5  [all hidden singles] 832 ,  5.......9.2.1...7...8...3...4.7.2.......5.........6.1.4.3...8...6...4.2.9.2.....5     SE 10.61285 ,  5.......9.2.1...7...8...3...4.7.2.......5.........6.1...3...8...6...4.2.9.......5     SE 11.4`

For some reason the addition of the above 2 clues in the first example makes the puzzle very easy - although it doesnt make any of the original 20 given clues superfluous.[EDIT it does make 2@r4c6 superfluous] The two clues by being there must reduce the value of n and x for some [? all] of the given clues. [EDIT - This is an understatement !]

Is "hardness" an unknown function of n,x, which is consistently high for each given clue ?

C
Last edited by coloin on Fri Apr 13, 2007 9:56 pm, edited 2 times in total.
coloin

Posts: 1638
Joined: 05 May 2005

coloin wrote:Its about time we finally get to the bottom of what makes our hard sudokus hard...- we cant really quantify our ratings until we know this......

The 20 clue from m_b_metcalf has 20 given clues and 61 insertable clues.
Code: Select all
`5.......9.2.1...7...8...3...4.7.2.......5.........6.1...3...8...6...4.2.9.......5     SE 11.4`

One thing that struck me about this puzzle (from staring at it for so long waiting for SE to solve it), is the symmetery not only of the clue pattern, but of the values themselves. They have an extraordinary degree of symmetry: box 1 reflects box 9, two
values in box 3 reflect those in box 7, the two 'cross-bars' are identical, and the central value is a repeat of r1c1 and r9c9.

Does this play a role?

Regards,

Mike Metcalf
Last edited by m_b_metcalf on Wed Mar 14, 2007 8:28 am, edited 1 time in total.

m_b_metcalf
2017 Supporter

Posts: 8416
Joined: 15 May 2006
Location: Berlin

Maybe the symmetry means that the unavoidable sets can be large.

This was the case in Greatest divergance possible in dual solution puzzle?: where the largest unavoidable possible in a 21 clue puzzle was found.

In MM's puzzle there are not many unavoidables specific to the r1c1 clue smaller than 27 clues......

For example here are 2 pseudopuzzles with 2 solutions
The unavoidable set includes the 5@r1c1
Code: Select all
`+---+---+---+|..4|...|289||.2.|18.|574||7.8|42.|361|+---+---+---+|.4.|7.2|658||...|.51|43.||...|.46|91.|+---+---+---+|4.3|21.|896||86.|..4|.23||9.2|..8|.45|+---+---+---+ [x = 33 clues]+---+---+---+|.1.|...|2.9||.26|1..|.7.||.98|..5|361|+---+---+---+|.4.|7.2|...||...|951|...||...|.46|.1.|+---+---+---+|..3|.1.|8.6||.6.|..4|.2.||9..|...|1.5|+---+---+---+  [x = 49 clues]`

Probably unremarkable except there could be rather a lot of these........

C
coloin

Posts: 1638
Joined: 05 May 2005

this doesn't take into account unavoidables
but a very simple (and fast) rating correlates with the ER ratings for ravel's most recent list
the rating counts the number of propositions and guesses using singles constraints
and weighs guesses more than propositions

use these option with my solver for the quick rating
%e lists the elapsed time
-e G filters out puzzles that require guessing with the FNP constraints (singles with propositions)
the rating is guesses*100+propositions
Code: Select all
`-R'G*100+P' -BX -qFNP -f'%v # %04r' -Ff%e -e G`

here is ravels list with the ER and the quick rating
Code: Select all
`ER   gsfQ puzzle                                                                            author11.4,1013,5.......9.2.1...7...8...3...4...2.......5.......7.6.1...3...8...6...4.2.9.......5,StrmCkr11.4,1008,5.......9.2.1...7...8...3...4.7.2.......5.........6.1...3...8...6...4.2.9.......5,m_b_metcalf11.2,0418,.....1.2.3...4.5.....6....7..2.....1.8..9..3.4.....8..5....2....9..3.4....67.....,Ocean's New Year's present for RW11.1,0215,..3.....94......2..8.6..1..2....4....9.8....7..5.3.......9..8.......5.3..7..1...6,dml 1/0711.0,0204,6....2.5952..4..1...35..2..3..1945...1.658.3...5273..1..4..51...3..2..4575.4....8,Mauricio's non minimal10.9,0510,7.......6.2..3..1...15..4.....19.5...4.6...2...5273.....2..53...3..1..4.8.......9,Mauricio10.9,0206,1..5....4.7.....6...2.3.1...2.19...5..4..82..5...73.....3.1.4...8.....9.2....5..3,Mauricio10.9,0205,3....5..2.4..1..3...9...8..5...9.....2.6.8.4...42....5..6..17...1..3..2.4..5....1,Mauricio10.9,0203,1....5..4.4..2..3...8...7..5..1......3.6.8.1.....73..5..9..26...1..4..2.2..5....3,Mauricio10.8,0507,1...4..3......7..4..58..7....25...8.6...9...2.3....4....3..6...7..2......6..8...1,Mauricio10.8,0308,..34...8......92......6...1..7.1.....6...2...5..8...4..1....9..8......3...45....7,dml 3/070.397939s`
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Could you explain the difference betwwen a guess and a proposition ! ?

I think I understand your rating weighting [guesses*100]

Doesnt it depend on which clue you guess as to the ease with which the puzzle succumbs ?

It is possible to analyse all the possible guesses.

20 given clues
61 cells without a clue

total cells without a clue = 61 correct guesses possible,488 possible guesses incorrect.

The analysis of these 488 wrong guesses
All will have a conflict - many will have simple box and row constraint - but many will not reveal a conflict until a long chain reaches one - this happens in difficult puzzles. I cant see milage in differentiating these - after all if a clue is wrong it will reveal conflicts throughout the puzzle.

I think it holds that difficult puzzles have a larger number of large unavoidable sets uniquely covered by one clue.
Certainly the converse is true - easy puzzles tend to have one of the clues [commonly the one with the least grid solutions] which only have a small number of smaller unavoidables uniquely covered by that clue.

I await Red Ed to comment - as I can only make amateurish attempts to find the large unavoidables !

C
coloin

Posts: 1638
Joined: 05 May 2005

coloin wrote:Could you explain the difference betwwen a guess and a proposition ! ?

I think I understand your rating weighting [guesses*100]

Doesnt it depend on which clue you guess as to the ease with which the puzzle succumbs ?

It is possible to analyse all the possible guesses.

a proposition step loops over all candidate values, sets a value, and applies the basic constraints
until { solution, contradiction, no-progress }
with -X on solutions are ignored (to nullify lucky backdoor discovery)
-B batches all of the proposition step contradictions until the end of the step and applies them en masse

so propositions with -BX are essentially unbiased guesses

when basic constraints and propositions fail to advance pure guessing is applied
starting with cells with the least number of candidates -- but you're right, luck comes
into play with guesses

nested propositions should take care of this
I was originally concerned about that getting out of hand
but the backdoor conjecture means that limiting to 2 concurrent propositions will be enough
(or the conjecture is refuted)

so when a singleton proposition step fails to advance a pairwise proposition step
could be applied and the number of solutions found in the pairwise step (there'd better be
at least one for the conjecture) would factor into the rating
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

I coded pairwise propositions in my solver and reposted it
use
Code: Select all
`-qquick`

for quick rating for the hardest puzzles
the %r format prints the rating which is just a count of the number of batched propositions

for the hardest sudoku pairwise propositions uncover backdoors
those backdoors are not applied until all have been uncovered (and accounted for in the proposition count)
the result is a rating that is emprically immune to automorphic puzzle permutations

you can test it by using the -JN option which re-solves each input puzzle using N permuted
copies of the orginal (e.g., -J100 to solve the original and 100 permuted copies)

btw, you can also use
Code: Select all
`-J100 -f%v`

to generate a stream of puzzles with 100 permuted copies for other rating progs

here is ravel's list with the quick pairwise proposition ratings
Code: Select all
`11.4,15511,5.......9.2.1...7...8...3...4...2.......5.......7.6.1...3...8...6...4.2.9.......5,StrmCkr11.4,15351,5.......9.2.1...7...8...3...4.7.2.......5.........6.1...3...8...6...4.2.9.......5,m_b_metcalf11.2,12444,.....1.2.3...4.5.....6....7..2.....1.8..9..3.4.....8..5....2....9..3.4....67.....,Ocean's New Year's present for RW11.1,13473,..3.....94......2..8.6..1..2....4....9.8....7..5.3.......9..8.......5.3..7..1...6,dml 1/0711.0,10860,6....2.5952..4..1...35..2..3..1945...1.658.3...5273..1..4..51...3..2..4575.4....8,Mauricio's non minimal10.9,10940,7.......6.2..3..1...15..4.....19.5...4.6...2...5273.....2..53...3..1..4.8.......9,Mauricio10.9,10940,1..5....4.7.....6...2.3.1...2.19...5..4..82..5...73.....3.1.4...8.....9.2....5..3,Mauricio10.9,10940,3....5..2.4..1..3...9...8..5...9.....2.6.8.4...42....5..6..17...1..3..2.4..5....1,Mauricio10.9,10944,1....5..4.4..2..3...8...7..5..1......3.6.8.1.....73..5..9..26...1..4..2.2..5....3,Mauricio10.8,08932,1...4..3......7..4..58..7....25...8.6...9...2.3....4....3..6...7..2......6..8...1,Mauricio10.8,14469,..34...8......92......6...1..7.1.....6...2...5..8...4..1....9..8......3...45....7,dml 3/073.070533s`

the last one does not correlate with SE
how consistent is SE with permuted copies?
here are 10 generated by -J10 for testing
Code: Select all
`..6.1.....9...2...4..8....5..1.....78..4...3..2....9.......61.....5...8.3...7...4..9..2....4.8..5..6...1.....8.4....31.....7....2....9......6.1..3..7.4.....5....8.4.8..3..6...1......9..2...1.....7...8.4....5..2....6....3....8.5..7.4.......9.1.....3...8.5...7.4....9..1...4..8..3...6..1...9..2.......1....7..8..4...52.....6..1......6...8.3...4.2....9......7..1......62....45....8..38.....7...4...5.9...1.....34...7.....1.6.......8..52...9......8..3..4.1.7.....9.....2....45....8.6.....1.5..4....7.....1.9.....8.3...1.7.....8...5.4....2..6....6......14..3..8....9....2.....1.7....4..8..3...2...9..1..6......8..45..2..9.....6......1...5.....8.7...34...5...4..8...9...2.....6.1..3....8..4..92......7..1.....4...37..8.......5..1....6.....5.8.....6....1.3...7.4.6....1.....92......4..8..5...2.....9.8..4.3..1......7.`
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

gsf wrote:when basic constraints and propositions fail to advance pure guessing is applied starting with cells with the least number of candidates...
gsf,
i didn't understood exactly, how your quick rating (in both versions) works. I had expected that the first version would corellate good with dukusos suexrat9, but it doesn't.
When stuck, often strongly linked (conjugated pair) candidates are a better choice for a try to eliminate them than bivalue candidates, because you do not only get a number, but also more candidates can be eliminated immediately.

I only had a quick look now at your last quick rating. Could you explain, what you mean with ?
those backdoors are not applied until all have been uncovered (and accounted for in the proposition count)
The new rating correlates better with mine. dml 3/07 is number 5 in my current top list (as i already said, i'm not satisfied with my rating, still hoping for a good idea, that would allow me to improve it with slight canges ).
I also want to say, that (as i see it), the quick ratings like Explainer's only rate the hardest step, not the amount of very hard steps, as my program does (in a more or less good way).
ravel

Posts: 998
Joined: 21 February 2006

ravel wrote:
gsf wrote:when basic constraints and propositions fail to advance pure guessing is applied starting with cells with the least number of candidates...
gsf,
i didn't understood exactly, how your quick rating (in both versions) works. I had expected that the first version would corellate good with dukusos suexrat9, but it doesn't.
When stuck, often strongly linked (conjugated pair) candidates are a better choice for a try to eliminate them than bivalue candidates, because you do not only get a number, but also more candidates can be eliminated immediately.

from my ancient understanding of suexrat9, it basically takes metrics from a backtraking
solver that is presented with N permuted copies of the same puzzle, with some formula
for combining the different results

the first rating I posted yesterday that counted guesses suffers from a similar bias as suexrat9 because
cell values are assigned as the backtrack search progresses, which allows either good
or bad choices early on to bias the rest of the search
ravel wrote:I only had a quick look now at your last quick rating. Could you explain, what you mean with ?
those backdoors are not applied until all have been uncovered (and accounted for in the proposition count)
The new rating correlates better with mine. dml 3/07 is number 5 in my current top list (as i already said, i'm not satisfied with my rating, still hoping for a good idea, that would allow me to improve it with slight canges ).
I also want to say, that (as i see it), the quick ratings like Explainer's only rate the hardest step, not the amount of very hard steps, as my program does (in a more or less good way).

right
* differences due to input puzzle permutations
* counting the number of methods required to get to a solution could be expensive
* counting only the hardest method could hide the effects of uncounted almost-hardest methods

the second method I posted addresses these issues by
* using naked and hidden singles only
* singleton proposition logic that looks at all single cell assignments and counts the propositions
only after all assigments have been tested
(this part is done stepwise by partitioning the cells by the number of candidates
and operating on all cells with the least number of candidates first, ending the step
when any cell with i candidates progresses the puzzle)
* pairwise proposition logic that assigns all cells pairwise and counts the propositions
(using the same stepwise partitioning as singleton propositions)

if the backdoor conjecture holds then puzzles that foil singleton propositions will fall to pairwise propositions
contradictions and backdoors found during the pairwise propositions are also batched
and not applied until all pairs are tested (for rating they don;t need to be applied -- discovery
of any backdoor in this step means the puzzle is solved)

you can use the -J option of my solver to generate a stream of permutations of one puzzle
to test if the -qquick rating, SE, or any other ratings, are biased on input puzzle layout
Last edited by gsf on Fri Mar 16, 2007 12:37 am, edited 1 time in total.
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

PreviousNext