The hardest sudokus

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

Postby gsf » Thu Mar 15, 2007 9:44 am

I reposted my solver to fix a paired proposition bug
(and also restored some html files clobbered earlier today)
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby StrmCkr » Sun Mar 18, 2007 11:35 am

im a bit muddled over somethign?

gsf

why is it that my puzzle rates slightly highter them MM's?

MM's has longer and more complicated steps them my variation..

is it becasue your avoiding backdoors to solving where my puzzle actually has more to avoid compared to his?
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 626
Joined: 05 September 2006

Postby gsf » Tue Mar 20, 2007 6:14 am

StrmCkr wrote:im a bit muddled over somethign?
why is it that my puzzle rates slightly highter them MM's?

MM's has longer and more complicated steps them my variation..

is it becasue your avoiding backdoors to solving where my puzzle actually has more to avoid compared to his?

the quick rating I posted uses singles only
so "complications" show up in how many times they must be applied after each proposition
to reach an assignment or contradiction

the hardest puzzles require paired propositions
the number of pairs (~10,000) is much greater than the number of singles backdoors of size 2
so the number of backdoors really doesn't come into play
(if you are guessing with a pencil there isn;t much difference between 1/10,000 and 10/10,000)

also, the quick rating doesn;t ignore backdoors, it just saves them up until all have been found
for the current # candidates per cell round in the proposition loops
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby StrmCkr » Tue Mar 20, 2007 9:01 am

alright that makes more sense.

1/10000 compared to 1/1000 is a huge number 10^1 diffrence... but most people see powers of 10 increments as still way too many numbers to check.

but...
the way ive seen alot of people guess is like so... fill in the entire puzzle based on the guess then change all the incorect numbers fallowing the broken path till the puzzle is corrected. it takes less time then actually backtracing the guess and changing the inital guess.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 626
Joined: 05 September 2006

Postby gsf » Tue Mar 20, 2007 3:18 pm

StrmCkr wrote:1/10000 compared to 1/1000 is a huge number 10^1 diffrence... but most people see powers of 10 increments as still way too many numbers to check.

relative to each other its a big difference
but relative to being a good path to a soultion 1/1000 is not appealing
StrmCkr wrote:but...
the way ive seen alot of people guess is like so... fill in the entire puzzle based on the guess then change all the incorect numbers fallowing the broken path till the puzzle is corrected. it takes less time then actually backtracing the guess and changing the inital guess.

the quick rating is not an attempt to model human or even machine solving techniques
its main point is to provide a metric that is the same up to isomorphism
(valid puzzle permutations do not change the metric)
basically it measures all of the work modulo #candidates per cell rather than work up to the hardest or luckiest point

its fast to compute and comes close to the other ratings on the list
btw, still no takers on providing the ER for the 10 permutations of one puzzle I posted a few days ago?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby StrmCkr » Tue Mar 20, 2007 8:53 pm

just making a point :P i do get what your saying and it makes some sence ... i was just quipping that some time people don't care how many mistakes they have to correct when following what i outlined...



where are the puzzles (as long as its not mine or mm's 11.4 puzzle..remorphed..) way too long to find their's...)

i'll find the ER ratings for you.? outside the above.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 626
Joined: 05 September 2006

Postby gsf » Tue Mar 20, 2007 9:12 pm

StrmCkr wrote:just making a point :P i do get what your saying and it makes some sence ... i was just quipping that some time people don't care how many mistakes they have to correct when following what i outlined...

ok
StrmCkr wrote:where are the puzzles (as long as its not mine or mm's 11.4 puzzle..remorphed..) way too long to find their's...)

i'll find the ER ratings for you.? outside the above.

http://forum.enjoysudoku.com/viewtopic.php?p=42197#p42197
10 copies of the 10.8
how long to compute the 11.4 rating?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby StrmCkr » Tue Mar 20, 2007 9:51 pm

alrighty i checked them... heres what i got.

for the first one.

..6.1....
.9...2...
4..8....5
..1.....7
8..4...3.
.2....9..
.....61..
...5...8.
3...7...4

Analysis results
Difficulty rating: 10.8
This Sudoku can be solved using the following logical methods: 54 x Hidden Single 5 x Direct Hidden Pair 5 x Pointing 1 x Claiming 2 x Naked Pair 2 x Hidden Pair 1 x Naked Triplet 3 x Hidden Triplet 1 x Turbot Fish 4 x Forcing Chain 2 x Cell Forcing Chains 3 x Region Forcing Chains 16 x Dynamic Contradiction Forcing Chains 3 x Dynamic Region Forcing Chains 1 x Dynamic Cell Forcing Chains 1 x Dynamic Double Forcing Chains (+) 6 x Dynamic Contradiction Forcing Chains (+) 17 x Dynamic Contradiction Forcing Chains (+ Forcing Chains)

this took 10-25 mins for me to identify... wasn't watching how long it took this is an approximation. just hit analyize and left it runnign checked it once and a while.


my 11.4 rated puzzle took 1 hr 35 mins.
(with extended memory using the method mm outlined)

and

mm's 11.4 takes 2 hrs 30 mins...
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 626
Joined: 05 September 2006

Postby gsf » Tue Mar 20, 2007 9:58 pm

StrmCkr wrote:alrighty i checked them... heres what i got.

thanks for the results
could you run it on one of the other 10.8 copies and see how it compares with the first 10.8
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby StrmCkr » Tue Mar 20, 2007 10:00 pm

running it right now...

il'll edit this when its finished.

.....wondering....
if its the same puzzle

Should the list of moves to solve it be identical?
.........
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 626
Joined: 05 September 2006

Postby gsf » Tue Mar 20, 2007 10:07 pm

StrmCkr wrote:
.....wondering....
if its the same puzzle

Should the list of moves to solve it be identical?
.........

well that's the challenge of coding a rating or metric
its difficult to wash out the puzzle orientation
even for singles I see some counting differences in my code that I can't explain
the proposition count is the first one I've done that seems to handle permutations
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby StrmCkr » Tue Mar 20, 2007 10:36 pm

.4.8..3..
6...1....
..9..2...
1.....7..
.8.4....5
..2....6.
...3....8
.5..7.4..
.....9.1.


Analysis results
Difficulty rating: 10.8
This Sudoku can be solved using the following logical methods: 56 x Hidden Single 1 x Direct Hidden Pair 2 x Naked Single 6 x Pointing 1 x Claiming 1 x Naked Pair 3 x Hidden Pair 1 x Naked Triplet 3 x Hidden Triplet 1 x Bidirectional Cycle 4 x Forcing Chain 1 x Aligned Triplet Exclusion 1 x Nishio Forcing Chains 3 x Region Forcing Chains 4 x Cell Forcing Chains 3 x Dynamic Cell Forcing Chains 13 x Dynamic Contradiction Forcing Chains 3 x Dynamic Region Forcing Chains 1 x Dynamic Double Forcing Chains (+) 6 x Dynamic Contradiction Forcing Chains (+) 17 x Dynamic Contradiction Forcing Chains (+ Forcing Chains)


........diffrent solving techniques used....

so my guess is diffrence in rating is casued by
poisitional allignment of pattern based solving methods casuing the slight shift as specfic patterns are more difficult to utilze or no longer fit the given settings of the puzzle.

my question is if the intial "fish" was there in the first puzzle isn't it still there in the second puzzle?

ie... so far i haven't seen anyone suggest that a given pattern can be permated>?. to match the issometric puzzle.


ive only seen identical patterns used.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 626
Joined: 05 September 2006

Postby coloin » Wed Mar 21, 2007 1:58 am

Searching this partial grid of m_B_metcalf
Code: Select all
+---+---+---+
|5..|...|..9|
|.2.|1..|.7.| 
|..8|...|3..|
+---+---+---+
|.4.|...|...| 
|...|...|...| 
|...|...|.1.|     
+---+---+---+                       
|..3|...|8..|   
|.6.|..4|.2.|                                         
|9..|...|..5|                                                         
+---+---+---+
Adding 3 clues unfortunately does not give any valid puzzles
Adding 4 clues gives these hard puzzles amongst many others .
These are all morphed variations of the puzzles m_b_metcalf and StrmCkr
Code: Select all
5.......9.2.1...7...8...3...4...2.......5.......7.6.1...3...8...6...4.2.9.......5  StrmCkr  5.......9.2.1...7...8...3...4...2.......8.......7.6.1...3...8...6...4.2.9.......5
5.......9.2.1...7...8...3...4...6.......5.......2.7.1...3...8...6...4.2.9.......5  5.......9.2.1...7...8...3...4...6.......8.......2.7.1...3...8...6...4.2.9.......5 5.......9.2.1...7...8...3...4.6.........5.......2.7.1...3...8...6...4.2.9.......5
5.......9.2.1...7...8...3...4.6.........8.......2.7.1...3...8...6...4.2.9.......5    5.......9.2.1...7...8...3...4.6.2.......5.........7.1...3...8...6...4.2.9.......5  5.......9.2.1...7...8...3...4.6.2.......5.......7...1...3...8...6...4.2.9.......5    5.......9.2.1...7...8...3...4.6.2.......8.........7.1...3...8...6...4.2.9.......5    5.......9.2.1...7...8...3...4.6.2.......8.......7...1...3...8...6...4.2.9.......5  5.......9.2.1...7...8...3...4.7.........5.......2.6.1...3...8...6...4.2.9.......5
5.......9.2.1...7...8...3...4.7.........8.......2.6.1...3...8...6...4.2.9.......5 5.......9.2.1...7...8...3...4.7.2.......5.........6.1...3...8...6...4.2.9.......5 m_b_metcalf
5.......9.2.1...7...8...3...4.7.2.......8.........6.1...3...8...6...4.2.9.......5  5.......9.2.1...7...8...3...4.7.6.......5.......2...1...3...8...6...4.2.9.......5  5.......9.2.1...7...8...3...4.7.6.......8.......2...1...3...8...6...4.2.9.......5
Presumably all SE 11.4

However adding [minimally] 5 clues is also productive producing these two puzzles...
Code: Select all
Suexrat9     Puzzle                                                                                                     
1163 ,5.......9.2.1...7...8...3...4...1......492......7...1...3...8...6...4.2.9.......5   SE 11.1   mbmplus5a
1070 ,5.......9.2.1...7...8...3...4.7.2.......51......6...1...3...8...6...4.2.9.......5   SE 11.1   mbmplus5b

Code: Select all
+---+---+---+
|5..|...|..9|
|.2.|1..|.7.|
|..8|...|3..|
+---+---+---+                                                           
|.4.|..1|...|
|...|492|...|
|...|7..|.1.|
+---+---+---+                                                                             
|..3|...|8..|   
|.6.|..4|.2.|   
|9..|...|..5|   
+---+---+---+ mbmplus5a SE 11.1


Reversing a box [box 7] will increase the yield of non-isomorphic puzzles

however there are not many hard puzzles with 4 added clues
Code: Select all
Suexrat9    Puzzle                                                                                                     
 575 ,   5.......9.2.1...7...8...3...4..3........56......7...1.3.....8...6...4.2...9.....5  SE   10.1 only

But more productive with 5 added clues, all these non-isomorphic puzzles emerged
Code: Select all
Suexrat9    Puzzle                                                                                                     
 967 ,  5.......9.2.1...7...8...3...4.2.6.......5.......7.8.1.3.....8...6...4.2...9.....5  St.Patrick 16  SE 10.9
 976 ,  5.......9.2.1...7...8...3...4.2.5.......36.......7..1.3.....8...6...4.2...9.....5  St.Patrick 15  SE 10.0 
1002 ,  5.......9.2.1...7...8...3...4.2.6......43.........9.1.3.....8...6...4.2...9.....5  St.Patrick 14  SE 10.5
1011 ,  5.......9.2.1...7...8...3...4.2.........57......4.6.1.3.....8...6...4.2...9.....5  St.Patrick 13  SE 11.2
1011 ,  5.......9.2.1...7...8...3...4.2.7.......8.......6.5.1.3.....8...6...4.2...9.....5  St.Patrick 12  SE 10.9
1011 ,  5.......9.2.1...7...8...3...4.72........3.......9.6.1.3.....8...6...4.2...9.....5  St.Patrick 11  SE 10.6
1023 ,  5.......9.2.1...7...8...3...4.26........3.......7.9.1.3.....8...6...4.2...9.....5  St.Patrick 10  SE 10.5 
1038 ,  5.......9.2.1...7...8...3...4.271......9.........6..1.3.....8...6...4.2...9.....5  St.Patrick 9   SE 10.5 
1042 ,  5.......9.2.1...7...8...3...4.26........3.......9.7.1.3.....8...6...4.2...9.....5  St.Patrick 8   SE 10.6
1067 ,  5.......9.2.1...7...8...3...4.2.7.......3........69.1.3.....8...6...4.2...9.....5  St.Patrick 7   SE 10.4
1092 ,  5.......9.2.1...7...8...3...4.3.7......69.........2.1.3.....8...6...4.2...9.....5  St.Patrick 6   SE 10.7
1137 ,  5.......9.2.1...7...8...3...4.2.7......8........4.6.1.3.....8...6...4.2...9.....5  St.Patrick 5   SE 10.4 
1194 ,  5.......9.2.1...7...8...3...4.7.2.......3........46.1.3.....8...6...4.2...9.....5  St.Patrick 4   SE 10.7
1283 ,  5.......9.2.1...7...8...3...4.62........5.......4.7.1.3.....8...6...4.2...9.....5  St.Patrick 3   SE 11.2
1324 ,  5.......9.2.1...7...8...3...4.6.2.......3........47.1.3.....8...6...4.2...9.....5  St.Patrick 2   SE 10.6
1394 ,  5.......9.2.1...7...8...3...4.7.2.......9.......46..1.3.....8...6...4.2...9.....5  St.Patrick 1   SE 11.2

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 SE 10.9

+---+---+---+
|5..|...|..9|
|.2.|1..|.7.|
|..8|...|3..|
+---+---+---+
|.4.|7.2|...|   
|...|.9.|...|     
|...|46.|.1.|   
+---+---+---+
|3..|...|8..|   
|.6.|..4|.2.| 
|..9|...|..5|
+---+---+---+  St.Patrick 1 SE 11.2


C
Last edited by coloin on Sun Apr 22, 2007 9:13 am, edited 4 times in total.
coloin
 
Posts: 1632
Joined: 05 May 2005

Postby StrmCkr » Wed Mar 21, 2007 6:12 am

here yeah go colin for this puzzle took over an hour...

Code: Select all
5.......9
.2.1...7.
..8...3..
.4.7.2...
....9....
...46..1.
3.....8..
.6...4.2.
..9.....5



Analysis results
Difficulty rating: 11.2
This Sudoku can be solved using the following logical methods: 57 x Hidden Single 2 x Direct Hidden Pair 1 x Naked Single 5 x Pointing 4 x Hidden Pair 1 x Swordfish 1 x Hidden Triplet 1 x XY-Wing 1 x Turbot Fish 1 x Bidirectional Cycle 4 x Forcing Chain 1 x Nishio Forcing Chains 2 x Region Forcing Chains 18 x Dynamic Contradiction Forcing Chains 5 x Dynamic Region Forcing Chains 5 x Dynamic Contradiction Forcing Chains (+) 9 x Dynamic Contradiction Forcing Chains (+ Forcing Chains) 1 x Dynamic Double Forcing Chains (+ Forcing Chains) 1 x Dynamic Region Forcing Chains (+ Forcing Chains) 8 x Dynamic Contradiction Forcing Chains (+ Multiple Forcing Chains)

and this one...
Code: Select all
 Er = 11.1
|5..|...|..9|                                                                                                                 
|.2.|1..|.7.|                                                                                                               
|..8|...|3..|                                                                                                               
+---+---+---+                                                                                                               
|.4.|..1|...|                                                                                                               
|...|492|...|                                                                                                                 
|...|7..|.1.|                                                                                                                 
+---+---+---+                                                                                                                 
|..3|...|8..|                                                                                                                 
|.6.|..4|.2.|                                                                                                                 
|9..|...|..5|                                                                                           



aslo on me an mikes puzzle the only number i found that moves around sucessfully is the "7" as it controlls 120 soultion reduction down to 1.
all others #'s generated a solution count beyond 500

also for every 7 removed and not placed where me and mike have it.

2+ 7's must be replaced on the board to equalize the number of solutions from a count range of 75 - 11, (per single replaced).

i never tried other numbers... but it did give me a good impression how that puzzle could change slightly, and reduces it s level of difficulty...
Last edited by StrmCkr on Wed Mar 21, 2007 3:28 am, edited 1 time in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 626
Joined: 05 September 2006

Postby gsf » Wed Mar 21, 2007 7:13 am

thanks coloin
I removed isomorphic dups and tabulated your post, keeping the oldest dup label, and sorted by the quick rating
ERs not done yet listed as 00.0 (awaiting someone else to sit with explainer)
quick rating takes ~1.4s/puzzle/Ghz for these puzzles
although these all look similar, each has a distinct solution
Code: Select all
#!sudoku -c3,ER,gsfQ,puzzle,author
00.0,18637,5.......9.2.1...7...8...3...4.2.6.......5.......7.8.1.3.....8...6...4.2...9.....5,St.Patrick-16
00.0,18075,5.......9.2.1...7...8...3...4.2.7.......8.......6.5.1.3.....8...6...4.2...9.....5,St.Patrick-12 00.0,17570,5.......9.2.1...7...8...3...4.26........3.......7.9.1.3.....8...6...4.2...9.....5,St.Patrick-10
00.0,17091,5.......9.2.1...7...8...3...4.26........3.......9.7.1.3.....8...6...4.2...9.....5,St.Patrick-8 00.0,16668,5.......9.2.1...7...8...3...4.3.7......69.........2.1.3.....8...6...4.2...9.....5,St.Patrick-6
00.0,16436,5.......9.2.1...7...8...3...4.271......9.........6..1.3.....8...6...4.2...9.....5,St.Patrick-9 00.0,16399,5.......9.2.1...7...8...3...4.2.7.......3........69.1.3.....8...6...4.2...9.....5,St.Patrick-7
00.0,16313,5.......9.2.1...7...8...3...4.72........3.......9.6.1.3.....8...6...4.2...9.....5,St.Patrick-11 00.0,15544,5.......9.2.1...7...8...3...4.6.2.......3........47.1.3.....8...6...4.2...9.....5,St.Patrick-2
00.0,15231,5.......9.2.1...7...8...3...4.7.2.......3........46.1.3.....8...6...4.2...9.....5,St.Patrick-4 00.0,15153,5.......9.2.1...7...8...3...4.2.6......43.........9.1.3.....8...6...4.2...9.....5,St.Patrick-14
11.4,15047,5.......9.2.1...7...8...3...4...2.......5.......7.6.1...3...8...6...4.2.9.......5,StrmCkr 11.1,14972,5.......9.2.1...7...8...3...4.7.2.......51......6...1...3...8...6...4.2.9.......5,mbmplus5b
11.4,14903,5.......9.2.1...7...8...3...4.6.........5.......2.7.1...3...8...6...4.2.9.......5,m_b_metcalf 11.2,14553,5.......9.2.1...7...8...3...4.7.2.......9.......46..1.3.....8...6...4.2...9.....5,St.Patrick-1
00.0,14500,5.......9.2.1...7...8...3...4.2.........87......4.6.1.3.....8...6...4.2...9.....5,St.Patrick-13 00.0,14457,5.......9.2.1...7...8...3...4.62........5.......4.7.1.3.....8...6...4.2...9.....5,St.Patrick-3
11.1,12331,5.......9.2.1...7...8...3...4...1......492......7...1...3...8...6...4.2.9.......5,mbmplus5a 00.0,02867,5.......9.2.1...7...8...3...4.2.5.......36.......7..1.3.....8...6...4.2...9.....5,St.Patrick-15
10.1,02693,5.......9.2.1...7...8...3...4..3........56......7...1.3.....8...6...4.2...9.....5,mbrev7 00.0,02247,5.......9.2.1...7...8...3...4.2.7......8........4.6.1.3.....8...6...4.2...9.....5,St.Patrick-5

[edit: renumbered St.Partick dups 16->15 17->16]
Last edited by gsf on Wed Mar 21, 2007 8:58 am, edited 1 time in total.
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

PreviousNext

Return to General