The hardest sudokus

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

Postby Obi-Wahn » Thu Jan 17, 2008 2:44 pm

Because I didn't need my notebook the past two days I used it to rate coloin-4/13-1600, which seems to be the hardest for implication tabling so far, with SE 1.2.1.

Code: Select all
6.......2.9.4...5...1...7...5..84.......2.......3.5.4.2.....6...3...9.8...7.....1

The result now is 11.8

Analysis results
Difficulty rating: 11,8
This Sudoku can be solved using the following logical methods:
53 x Hidden Single
5 x Direct Hidden Pair
2 x Naked Single
3 x Pointing
3 x Claiming
1 x Naked Pair
1 x X-Wing
4 x Hidden Pair
2 x Naked Triplet
1 x Bidirectional Y-Cycle
2 x Turbot Fish
1 x Forcing X-Chain
4 x Forcing Chain
3 x Nishio Forcing Chains
6 x Region Forcing Chains
4 x Cell Forcing Chains
6 x Dynamic Contradiction Forcing Chains
11 x Dynamic Region Forcing Chains
5 x Dynamic Cell Forcing Chains
2 x Dynamic Double Forcing Chains
6 x Dynamic Contradiction Forcing Chains (+)
3 x Dynamic Contradiction Forcing Chains (+ Forcing Chains)
6 x Dynamic Contradiction Forcing Chains (+ Multiple Forcing Chains)
9 x Dynamic Contradiction Forcing Chains (+ Dynamic Forcing Chains)
1 x Dynamic Cell Forcing Chains (+ Dynamic Forcing Chains)
6 x Dynamic Region Forcing Chains (+ Dynamic Forcing Chains)


For coloin-4/13-1414 the result is 11.8, too.
Code: Select all
1.......2.9.4...5...6...7...5.3.4.......6........58.4...2...6...3...9.8.7.......1

Analysis results
Difficulty rating: 11,8
This Sudoku can be solved using the following logical methods:
53 x Hidden Single
3 x Direct Hidden Pair
2 x Naked Single
2 x Direct Hidden Triplet
5 x Pointing
2 x Naked Pair
2 x Naked Triplet
1 x Forcing X-Chain
1 x Forcing Chain
1 x Nishio Forcing Chains
3 x Dynamic Cell Forcing Chains 9 x Dynamic Contradiction Forcing Chains
5 x Dynamic Region Forcing Chains
7 x Dynamic Contradiction Forcing Chains (+)
1 x Dynamic Region Forcing Chains (+ Forcing Chains)
13 x Dynamic Contradiction Forcing Chains (+ Forcing Chains)
6 x Dynamic Contradiction Forcing Chains (+ Multiple Forcing Chains)
5 x Dynamic Contradiction Forcing Chains (+ Dynamic Forcing Chains)
1 x Dynamic Double Forcing Chains (+ Dynamic Forcing Chains)
4 x Dynamic Region Forcing Chains (+ Dynamic Forcing Chains)
Last edited by Obi-Wahn on Mon Jan 21, 2008 7:41 am, edited 1 time in total.
User avatar
Obi-Wahn
 
Posts: 61
Joined: 05 January 2007
Location: Darmstadt, Germany

Postby champagne » Thu Jan 17, 2008 5:12 pm

Obi Whan wrote


Because I didn't need my notebook the past two days I used it to rate coloin-4/13-1600, which seems to be the hardest for implication tabling so far, with SE 1.2.1.


6.......2.9.4...5...1...7...5..84.......2.......3.5.4.2.....6...3...9.8...7.....1

The result now is 11.8


On my side that puzzle is rated poorly: 26 seconds.

Up to now I have not seen a puzzle having the SK loop over 30 seconds. Hardest for me are over 100 seconds.

[/quote]
champagne
2017 Supporter
 
Posts: 5725
Joined: 02 August 2007
Location: France Brittany

Postby coloin » Sun Feb 03, 2008 12:11 pm

Maybe the conflicting opinions is due to whether you are rating from a bifurcationist's or a patternist's viewpoint.

I suspect gsf and SE to be the former.

Interesting development by g.r.emlin in the patterns game 1.5

EP is the highest ER leading to the first placement [Pearl rating]
ED would be the ER of the first method (placement or candidate elimination) [Diamond rating]

With SE 1.2.1 - Golden Nugget.....ER 11.9 / EP 11.9 / ED 11.3


I dont know what a patternist does so I cant decide on the other rating methods:!:

[SK-loop excepted]

C
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby coloin » Wed Feb 06, 2008 2:29 pm

We know Easter monster is classified M3 - by -q1 in gsf's program.
Code: Select all
1.......2.9.4...5...6...7...5.9.3.......7.......85..4.7.....6...3...9.8...2.....1 # 99408 FNBP C21.m/M3.566.938

In these ultra-hard puzzles, this means that no combination of 2 added [correct] proposition clues makes this puzzle easy, but there is a combination of 3 [correct] clues added which does.

Conversely, by adding incorrect proposition clue[s], it is difficult for a human solver to say that these incorrect added clues give a contradiction. [It is easy for a back-tracking computor solver program to do this it may be said].

In easy puzzles a human solver can say with a degree of ease that the guessed clue was wrong.

Mostimes [guess] it is possible to fit 2 incorrect preposition clues to invalidate a puzzle....are there any puzzles which you cant find 3 [or more ?] incorrect preposition clues which scupper a puzzle......a sort of inverse M3 .

Im in the dark here because no conventional solver can "rate" invalid puzzles !

C
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby champagne » Wed Feb 06, 2008 7:24 pm

Hi Coloin,

I red your two last post, but I have difficulties to understand where you want to go.

You wrote

In these ultra-hard puzzles, this means that no combination of 2 added [correct] proposition clues makes this puzzle easy, but there is a combination of 3 [correct] clues added which does.


This is a clear definition of an objective ranking method. For me, the trick is that clearing logic does not lead necessarily to these three fix. What I see most often in such puzzles is that after a long way, the puzzle suddenly collapses.

You wrote

Conversely, by adding incorrect proposition clue[s], it is difficult for a human solver to say that these incorrect added clues give a contradiction. [It is easy for a back-tracking computer solver program to do this it may be said].


Normally this is not the way we are trying to crack puzzles. Most of us exclude any T&E in the cracking process (including human solvers). But as you noticed

In easy puzzles a human solver can say with a degree of ease that the guessed clue was wrong.


You wrote

Mostimes [guess] it is possible to fit 2 incorrect preposition clues to invalidate a puzzle....are there any puzzles which you cant find 3 [or more ?] incorrect preposition clues which scupper a puzzle......a sort of inverse M3 .


If I got your point I doubt that this is an interesting view. You have evident answer if the added clues are taken from dual cell or bi values, if not, you need more clearing to come to added clues.

And finally you wrote

Im in the dark here because no conventional solver can "rate" invalid puzzles !


What means “rating invalid puzzles”??
champagne
2017 Supporter
 
Posts: 5725
Joined: 02 August 2007
Location: France Brittany

Postby gsf » Wed Feb 06, 2008 7:48 pm

champagne wrote:Normally this is not the way we are trying to crack puzzles. Most of us exclude any T&E in the cracking process (including human solvers). But as you noticed

there is a difference between rating and cracking
as SE shows us there must be
SE avoids T&E but because of that can take a good part of a day to rate the hardest

backdoors are one way to expose structure
another way is to see how hard it is to determine a move is bad
coloin is saying that a bad move (those that avoid T&E would never make a bad move)
in a hard puzzle may lead down a much longer path of techniques before failure than in an easy puzzle

re: rating invalid puzzles, that would be equivalent to, after a bad move, determining the rating leading up to the detection of failure
my solver is close to this
may have something tomorrow
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby tarek » Wed Feb 06, 2008 9:33 pm

coloin wrote:Mostimes [guess] it is possible to fit 2 incorrect preposition clues to invalidate a puzzle....are there any puzzles which you cant find 3 [or more ?] incorrect preposition clues which scupper a puzzle......a sort of inverse M3 .
I guess that again, you have to specify the techniques you are measuring this against........

It would be interesting to see such puzzles & how would they rate.

so for a singles M3 puzzle you would be looking for a puzzle that has all combinations of 2 guesses being fruitless (not leading to either invalidity or solution under singles techniques). Or even more, all cobinations of 3 guesses apart from the backdoors being fruitless.


tarek
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

Postby champagne » Wed Feb 06, 2008 9:59 pm

gsf wrote

there is a difference between rating and cracking
as SE shows us there must be
SE avoids T&E but because of that can take a good part of a day to rate the hardest


very interesting.

1) Diffference between rating and cracking ??
What is the reason for rating if it is not to evaluate the difficulty to solve (crack) the puzzle?

2) For sure, rating thru a cracking process is not perfect:
not stable overtime,
highly relying on the solver capability,
no ranking if the solver fails.

3) On the other side, if a "stable" ranking process gives results having no correlation with the solving difficulty, you face another problem

4) By chance, I do not have the problem encountered by SE. All puzzles I tested were cracked and the hardest to solve has been solved in about 120 seconds;

Gsf wrote

backdoors are one way to expose structure
another way is to see how hard it is to determine a move is bad
coloin is saying that a bad move (those that avoid T&E would never make a bad move)
in a hard puzzle may lead down a much longer path of techniques before failure than in an easy puzzle



For me, clearing a candidate thru any non T&E method is equivalent to testing a bad move.
Hard puzzles are requesting more stuff, longer chains..... to be cracked.
Not so different from other way to evaluate. If correlation is not very good, hard puzzles are hard for everybody.

Maybe because I am focusing on difficulty to crack a puzzle, I would be prepared to having a ranking changing overtime following the "best known process".
This is not easy to establish, so I can understand that people working on hardest puzzles can not wait for such an hypothetic tool.
champagne
2017 Supporter
 
Posts: 5725
Joined: 02 August 2007
Location: France Brittany

Postby coloin » Thu Feb 07, 2008 12:54 am

Champagne, indeed your view as a non-bifurcationist is valid, rating puzzles for "hardness" has always been subjective. I am glad that your solving efforts can be used to somehow evaluate a puzzle.
champagne wrote:Normally this is not the way we are trying to crack puzzles. Most of us exclude any T&E in the cracking process (including human solvers).

Not sure, I think more people do than admit to it ![The 1st world champion guessed right on the final puzzle]

Bivalue cells or positions....
These logically are the weakest point of the puzzle, and there are always these bivalue cells......:idea: .....but the step to prove that one [incorrect] value is wrong is equal to proving that the other [correct] value is right !!!

Rating invalid "puzzles"

Well daj95376 did it .....here
he worked out there were only 6 possible ways to add one of the templates, [6-template], of which only one was correct.
he was able to say why the other 5 templates were invalid
Code: Select all
1.......2.9.4...5...6...7...5.3.4......96.........8.4...2...6...3...9.8.7.......1      puzzle
.......6......6.....6..............6....6.....6.............6..6...........6.....      correct template
...6.............6..6.............6.....6.....6.............6..6.............6...      incorrect template
                                  x                                          x
1.......2.9.4...5...6...7...5.3.4.6....96.........8.4...2...6...3...9.8.7....6..1      2 incorrect clues
1..6....2.9.4...56..6...7...5.3.4.6....96.....6...8.4...2...6..63...9.8.7....6..1      6 template completed with singles

daj95376 wrote:1..6....2.9.4...56..6...7...5.3.4.6....96.....6...8.4...2...6..63...9.8.7....6..1
finned Swordfish c268\r357 <> 1 [r3c45] w/fin=[r2c5]
finned X-Wing c26\r35 <> 2 [r3c45] w/fin=[r2c5]
finned Swordfish c268\r157 <> 7 [r1c5] w/fin=[r2c5]


However.....
A combination of two incorrect cells would tend to make even the hard "puzzle" recognizably "invalid".

In the Easter Monster puzzle [unfortunately] I have found two clues [quite easily....]
Code: Select all
+---+---+---+
|1..|...|..2|
|.9.|4..|.5.|
|..6|...|7..|
+---+---+---+
|.5.|9.3|...|
|...|.7.|...|
|...|85.|.4.|
+---+---+---+
|7..|...|6..|
|.3.|..9|.8.|
|..2|...|..1|
+---+---+---+
                      with 6@r9c1 and 4@r3c2
+---+---+---+
|1..|...|..2|
|.9.|4..|.5.|
|.46|...|7..|
+---+---+---+
|.5.|9.3|...|
|...|.7.|...|
|...|85.|.4.|
+---+---+---+
|7..|...|6..|
|.3.|..9|.8.|
|6.2|...|..1|
+---+---+---+
                           expands to
+---+---+---+
|17.|...|462|
|.9.|4.7|.5.|
|.46|...|71.|
+---+---+---+
|.5.|943|...|
|.6.|17.|.2.|
|.2.|856|.4.|
+---+---+---+
|719|...|63.|
|.3.|..9|287|
|682|734|591|
+---+---+---+               no possible clue for r5c6


Golden Nuggett also is invalid with these 2 "incorrect" clues
Code: Select all
+---+---+---+
|...|...|.39|
|...|2.1|..5|
|..3|.5.|86.|
+---+---+---+
|..8|.9.|..6|
|.7.|..2|...|
|1..|4..|...|
+---+---+---+
|..9|.8.|.5.|
|.2.|...|6..|
|4..|7..|...|
+---+---+---+


Perhaps there ant many of these proposition paired clues which do this.
I await gsfs coding, if it is even possible.

In these hardest puzzles I was assuming that single incorrect clues didnt give a simple contradiction.. ...now Im not so sure.

C
Last edited by coloin on Wed Feb 06, 2008 9:34 pm, edited 1 time in total.
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby gsf » Thu Feb 07, 2008 1:30 am

coloin wrote:I await gsfs coding... but its not going to work.....

now that needs a bit more explanation
I thought you were at a point where you wanted a solver to rate an invalid position
I assumed that to be a measure of the difficulty to determine a contradiction
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby coloin » Thu Feb 07, 2008 1:45 am

Well, 2 clues added make the "puzzle" have a constrained grid solution....by even simple techniques..... So Im not sure where it goes from here.

The EM puzzle with 2 bad clues solves to a contradiction with singles and a naked pair.

Any point ? - apart from a count up of all the proposition pairs.......

I suppose were rating how difficult it is to solve the puzzles with T&E.

Nasty taste

C
Last edited by coloin on Wed Feb 06, 2008 9:56 pm, edited 1 time in total.
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby daj95376 » Thu Feb 07, 2008 1:54 am

coloin wrote:Well daj95376 did it here
he worked out there were only 6 possible ways to add one of the templates, [6-template], of which only one was correct.
he was able to say why the other 5 templates were invalid

Just for clarification. My solver wasn't able to make any initial headway on solving coloin-04/13-1426. So, I found the candidate with the fewest number of possible Templates and tested each Template under the assumption that it was correct. For each of the six test cases, my solver was able to either find a solution or else reach an invalid grid. I also did this with Easter Monster, but never reported my results.

Note: In each of the five invalid cases for coloin-04/13-1426, my solver had to work very hard to reach the invalid grid.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby gsf » Thu Feb 07, 2008 2:07 am

coloin wrote:Well, 2 clues added make the "puzzle" have a constrained grid solution....by even simple techniques..... So Im not sure where it goes from here.

The EM puzzle with 2 bad clues solves to a contradiction with singles and a naked pair.

Any point, apart from a count up of all the pairs.......

got it
I was thinkg as a rating technique, not a solution technique
the -q1 method essentially does this for singles
(set all possible single values and determine how far naked/hidden singles get until contradiction or solution,
then set all possible pairs values and determine how far naked/hidden singles get until contradiction or solution)

you can experiment with other constraint combinations
easter monster requires 9 FNB proposition rounds (1 singleton, 8 paired)
Code: Select all
sudoku -v2 -q'{FNB}P*' 100000002090400050006000700050903000000070000000850040700000600030009080002000001

golden nugget requires 1 FN proposition round (paired)
Code: Select all
sudoku -v2 -q'{FN}P*' 000000039000001005003050800008090006070002000100400000009080050020000600400700000
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby gsf » Thu Feb 07, 2008 2:29 am

the -v2 output from the previous post might need some illumination (and it might provide some too)

Code: Select all
[1]      propositions   5390  solutions   0  contradictions   1  iterations  10366  girth   8  degree   3  nesting 2
     P1  [31]^2
         propositions   5782  solutions   0  contradictions   1  iterations  11100  girth   8  degree   3  nesting 2
     P1  [13]^7
         propositions  25009  solutions   0  contradictions   2  iterations  57110  girth   9  degree   3  nesting 2
     P2  [73]^1 [91]^6
         propositions  96667  solutions   0  contradictions   3  iterations 222542  girth   9  degree   4  nesting 2
     P2  [85][52]^4
         propositions 136667  solutions   0  contradictions   6  iterations 321340  girth   9  degree   5  nesting 2
     P2  [26]^8 [84]^5
         propositions 162706  solutions   0  contradictions   3  iterations 383638  girth   9  degree   5  nesting 2
     P2  [59]^6 [62]^1
         propositions    220  solutions   0  contradictions   1  iterations    396  girth   4  degree   4  nesting 1
     P1  [76]^1
         propositions   7548  solutions   0  contradictions   1  iterations  15736  girth   9  degree   3  nesting 2
     P1  [75]^1
         propositions  27656  solutions   2  contradictions   2  iterations  65588  girth   9  degree   3  nesting 2
     P4  [84]=2 [38]=3 [72][31]^4

these are the 9 proposition rounds
nesting 2 means proposition pairs, degree 3 mean trivalue/trilocation values only tested
for the first round 5390 trivalue/trilocation pairs were set, and FNB propagation only
resulted in one pair leading to a contradiction, the remaining pairs were inconclusive

the 136667 round had 136667 5-value/5-location pairs, and only 6 led to a contradiction

this shows that easter monster is resilient to pairs w.r.t. FNB constraints
and -q'{FN}P*-G' it does not yield to singles only, neither single cell nor paired cell
(golden nugget does yield to this)
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby coloin » Thu Feb 07, 2008 3:18 am

Yes, you have analysed this - really well.

However in EM, I cant see more than approx. [60*4]^2 / 2 = 28800 proposition pairs.......

How many of them lead to a contradiction w.r.t. FNB constraints ?

None of the correct pairs lead to a contradiction or advance the puzzle I acknowledge.

C
coloin
 
Posts: 1638
Joined: 05 May 2005

PreviousNext

Return to General