#7 from the top95

Post the puzzle or solving technique that's causing you trouble and someone will help

Postby ttt » Sun Aug 31, 2008 11:40 pm

999_Springs wrote:
ttt wrote:2- if r8c3=7 => r5c1=7 & r4c4=7 => (r2c3,r2c1,r2c7)<>7

I presume you mean r2c4?

YES, I corrected...

Thanks
ttt
ttt
 
Posts: 185
Joined: 20 October 2006
Location: vietnam

Postby gsf » Mon Sep 01, 2008 10:47 pm

999_Springs wrote:
gsf wrote:they were compiled by dukosu in 2005
based on statistical analysis of the behavior of a simple randomized backtrack solver
its amazing how that simple (as in uncomplicated) analysis still holds for a large number of the topn collections

I have little knowledge in Su-Doku programming - could you please explain further?

you can model a sudoku solver using backtrack tree search as a guessing machine on a pencilmark grid
the machine makes a guess on one of the pencilmark candidates
and proceeds to a new search level based on that guess
when a guess fails the search backs up to a previous pencilmark grid and makes a different guess

the guess order can affect the amount of guesses needed to find a solution
the number of guesses can be counted (might be called number of search nodes)
in this model more guesses means more work which means harder

dukosu's solver used for rating made the next guess based on a pseudo-random selection
the pseudo-random select would determine the guess cell and candidate value

for a given puzzle the pseudo-random solver could be run multiple times
each time might require a different number of guesses

dukosu rated puzzles by averaging the number of guesses to solve
over 100's to 1000's of solver passes (a parameter to the rating program)

in general, puzzles that require more average number of guesses to solve
tend to be harder for humans to solve too
the remarkable thing is that this observation still holds today
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby 999_Springs » Tue Sep 02, 2008 2:16 pm

gsf, thanks for all the information.

999_Springs wrote:What is the point of having both #7 and #9 of the top95? The puzzles are completely identical except that the 3 and 4 in r2 have been switched. Their solving paths are near-identical and so are their difficulty levels. From the solution of #7 it is just an easy task to simply find the 12-cell unavoidable containing that 3 and that 4 and no other clues (just take the 3 and 4 in blocks 2, 3, 5, 6, 8 and 9) and switch those numbers round, and then copy out the rest of the solution. It is completely pointless to include both puzzles. How were the top95 designed?


What is the point of having both #8 and #10 of the top95? The puzzles are near-isomorphic and their difficulty levels and techniques required are nearly identical. Their solutions can be transformed into each other by the procedure below. It is completely pointless to include both puzzles.

Ok, near-isomorphic puzzles would produce similar numbers of guesses for a randomized backtrack solver to solve the puzzles. But were the puzzles which were tested for difficulty a truly random sample of puzzles? I am looking for a reason to this infuriating similarity...

Are there any more ridiculously similar pairs of puzzles in the top95? I think that the top95 should be renamed "Puzzles to Subtly And Slowly Enrage Solvers".



procedure:
take puzzle #10's solution
swap bottom and middle bands
interchange 7->6->9->5->8->7, 3<->4
swap around these cell pairs: r2c89 r3c89 r5c89 r7c89 r8c89 r9c89 r46c2 r46c5 r4c8r6c9
you now have puzzle #8
Once upon a time I was a teenager who was active on here 2007-2011
ocean and eleven should have paired up to make a sudoku-solving duo called Ocean's Eleven
999_Springs
 
Posts: 433
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Previous

Return to Help with puzzles and solving techniques