sudoku getting harder

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

Postby dukuso » Mon Aug 29, 2005 3:36 pm

Nick70 wrote:
dukuso wrote:The relative hardness of Gordon's 17s was confirmed by Merri and others. Have you tested the whole list ?

I've run it through my solver. Here are the results:

Code: Select all
9276  diff 00 [trivial]
5994  diff 01 [single unit candidate]
 778  diff 02 [naked pair]
 511  diff 03 [hidden pair]
   4  diff 04 [x-wing]
1037  diff 05 [turbot fish]
  17  diff 06 [naked triplet]
   2  diff 07 [swordfish]
   8  diff 08 [hidden triplet]
 499  diff 09 [xy-wing]
  61  diff 10 [skewed swordfish]
   2  diff 14 [jellyfish]
 931  diff 15 [forcing chain]
  72  diff 16 [multi forcing chain]
   5  diff 20 [guessing]

So as you can see more than three quarters of them are trivial or very easy.



thanks for the statistics !
Now, how does this compare with a sample of random sudokus ?
See also :
http://www.icparc.ic.ac.uk/~hs/sudoku.pdf
he has an updated version with tests on 7611 of Gordon's
and my top100, which I can send
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby Moschopulus » Tue Aug 30, 2005 11:15 am

Then there is the problem of whether gfroyle's 17ers are a random sample of all 17ers. He previously said that they were not.

This is in addition to the problems of how we generate a grid at random, and how we rate the difficulty. All interesting items for discussion. (These have been discussed elsewhere.)

Nick70: does your difficulty rating only depend on the hardest technique used, and not on the time taken? Your output seems to indicate this. And then your rating depends on your ordering of the techniques.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby dukuso » Tue Aug 30, 2005 12:44 pm

Moschopulus wrote:Then there is the problem of whether gfroyle's 17ers are a random sample of all 17ers. He previously said that they were not.

**he said that they _might_ not because his method was
** not very random. But now he has 19000, that's quite a large sample.
**And if his method were biased, then I'd assume that it were
** biased towards the easy ones. They are hard to find, so he
** probably tries to find the easy ones first.

This is in addition to the problems of how we generate a grid at random, and how we rate the difficulty. All interesting items for discussion. (These have been discussed elsewhere.)

Nick70: does your difficulty rating only depend on the hardest technique used, and not on the time taken? Your output seems to indicate this. And then your rating depends on your ordering of the techniques.


One thing is clear: most sudokus can be solved by basic methods
alone. I think that's "trivial" or "single unit candidate" by Nick70's
classification.
These are easy by any reasonable program.
But then it's already difficult to decide. Checking for
"naked pair" takes some time and rarely is successful,
so is it worth the effort ? Well, Merri has examined
this and he says it gives him 20% speed increase.
But the other methods are probably too expensive.
Despite "Nishio", which I couldn't find in Nick70's list,
it could be "forcing chain"
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby Nick70 » Tue Aug 30, 2005 2:12 pm

Moschopulus wrote:Nick70: does your difficulty rating only depend on the hardest technique used, and not on the time taken? Your output seems to indicate this. And then your rating depends on your ordering of the techniques.

It depends on the hardest technique, then in the group of puzzles using the same techinque I rate them according to the number of times used, or how difficult the techinque was to apply.

This doesn't change the fact that more than three quarters of the the problems were trivial or very easy.

Difficulties above that are little arbitrary.
Nick70
 
Posts: 156
Joined: 16 June 2005

Postby Moschopulus » Wed Sep 14, 2005 11:11 pm

Nick70 wrote:I've run it through my solver. Here are the results:

Code: Select all
9276  diff 00 [trivial]
5994  diff 01 [single unit candidate]
 778  diff 02 [naked pair]
 511  diff 03 [hidden pair]
   4  diff 04 [x-wing]
1037  diff 05 [turbot fish]
  17  diff 06 [naked triplet]
   2  diff 07 [swordfish]
   8  diff 08 [hidden triplet]
 499  diff 09 [xy-wing]
  61  diff 10 [skewed swordfish]
   2  diff 14 [jellyfish]
 931  diff 15 [forcing chain]
  72  diff 16 [multi forcing chain]
   5  diff 20 [guessing]

So as you can see more than three quarters of them are trivial or very easy.


Could you post (or pm me) the 5 puzzles (or even one) with difficulty rating 20, that require guessing, please?
Moschopulus
 
Posts: 256
Joined: 16 July 2005

"Gordon Royle's 450 Sudoku games with only 17 hints&

Postby Pat » Sun Oct 16, 2005 2:47 pm

tso wrote:The majority of 17-clue Sudoku are easy


this may be unknown to Antonio Cisternino, Dipartimento di Informatica, Università di Pisa, who has published "450 impossible Sudoku games! Gordon Royle's 450 Sudoku games with only 17 hints"

yes, just a few months ago, Gordon Royle's list of 17-clue puzzles had only 450 puzzles; but they were never selected for difficulty of solving!

- Pat
User avatar
Pat
 
Posts: 3521
Joined: 18 July 2005

Previous

Return to General