The New Sudoku Players' Forum

[kat]

as they get harder does it just mean that you are given less and less numbers to work it out from

[Addlan]

Not necessary. It depends on how you put the numbers. Usually when there are fewer digits, the number of possible digits varies a lot and you can work it out one by another. I believe in some cases when the possible numbers are almost equal (or even equal), it will be really hard to work it out. I haven't come across such Sudoku yet. It will be interesting to see an example if people have.

[graatz]

I believe that difficulty is rated on the computational power nessesary to solve the problem, rather than the number of starting numbers. I don't think an easy board can have too few starting numbers, but certainly the much more difficult ones can have a large number of starting numbers.


Cafepress Sudoku Store!

[tso]

The majority of 17-clue Sudoku are easy. For example, this one requires only the most elementary logic:

Code: Select all

 *-----------*
 |...|...|.13|
 |...|8..|.7.|
 |...|5.2|...|
 |---+---+---|
 |...|4..|9..|
 |1.7|...|...|
 |...|...|2..|
 |---+---+---|
 |89.|...|.5.|
 |.4.|...|6..|
 |...|.1.|...|
 *-----------*

[Moschopulus]

Yes, I don't know if any relationship has been established between the number of clues and the difficulty. Initially most people think that the fewer clues there are, the more difficult the puzzle is. But that seems to be false.

it would be interesting if someone could generate some statistics on this.
We need to choose lots of puzzles with k clues "randomly" and rate their difficulty, for each k from 17 to 35 (say).

[PaulIQ164]

I assume it depends on how the puzzles are generated, mind. I'm presuming here that Pappocom's (which generally do have more clues the easier they are) and other such generator programs, build sudokus employing the tactics that will be used to solve them, so that fiendishes are built using more advanced tactics than easys. So although Pappocom puzzles are harder the more clues there are, this does not mean the rule would hold for all sudokus, as Pappocom's are not generated 'randomly'. I don't know how you're generating 17-cluers and some of the other difficult sudokus you have round here, but seeing as you're using them to develop new tactics, I presume they're generated in ways which don't use particular tactics in their building.

[Pappocom]

Pappocom puzzles are generated randomly.

- Wayne

[PaulIQ164]

Yes, I understand that Pappocom puzzles are generated at random in the sense that there's no preordained set of puzzles it picks them out from or anything, but since they only require certain tactics in their solving, these tactics must in some form be 'built in' to the generating algorithms, so the puzzles aren't just a random subset of all possible unique-solution grids.

[tso]

There's random and then there's random. If I break a stick into three pieces, what's the chance that one piece will be at least twice the size of another? It depends on what random method I use. If I pick a spot at random, break the stick in two, pick one of the pieces at random and break it in the same way -- I get a completely different solution than if I pick two places at random to make both breaks at once.

I don't know how Poppocom does it, but you could:

-- Start with a finished grid, remove cells one by one, testing to make sure after each removal that the remaining cells yeild a unique solution until no more can be removed. (You probably WON'T get many with only 17 or 18 cells this way.) At this point, you could judge the difficulty of the resulting puzzle based on whatever criteria you choose. If the user was looking for an "easy" one but the puzzle is rated "medium", discard it and repeat.

OR

-- Start with an empty grid, add clues one by one, testing to mae sure after each addition that clues will admit one (or more) solutions. If added clue makes the puzzle unsolvable, it is retracted. Continue until a unique-solution puzzle is found. Rate for difficutly.

I imagine an advantage of the former method is that you could pick the solution in a less than random way that might be more likely to lead to a certain structure.

Or maybe the advantage of the *latter* is that no solution grid is decided upon in advance -- maybe that would more easily allow the inclusion of the traps you want.

I dunno...


Here's a 17 clue that requires advanced methods:

Code: Select all

 . 5 . | . . . | 6 . .
 9 . . | . 1 . | . . .
 . . . | . . . | . . .
-------+-------+------
 . . . | 5 . 2 | 8 . .
 3 . . | . . . | 4 . .
 . . 1 | . . . | . . .
-------+-------+------
 . . . | 2 . . | . 1 9
 . . . | . 6 . | . 3 .
 . 8 . | 7 . . | . . .

[dukuso]

in average the 17-clue puzzles are harder than random ones.
They require about double as much computer solving time.
Human solving time should be similar.


BTW.
here is an easy 17: you can solve the 1s by ignoring the other values
(but not their positions)
then you can solve the 2s the same way etc. until 6s
Just one 17-sudoku with this property from Gordon's 19000+

Code: Select all

.7.86....
3.......1
.........
....134..
.5.....6.
....2....
...5..78.
1..4.....
2........



[angusj]

in average the 17-clue puzzles are harder than random ones.
They require about double as much computer solving time.
Human solving time should be similar.

17 clue puzzles are if anything easier not harder to solve by both humans and computers - unless you rely entirely on trial and error as your computer solving algorithm.

[dukuso]

in average the 17-clue puzzles are harder than random ones.
They require about double as much computer solving time.
Human solving time should be similar.

17 clue puzzles are if anything easier not harder to solve by both humans and computers - unless you rely entirely on trial and error as your computer solving algorithm.

...which, as you can see below correlates well with other programs
as for measuring hardness:

correlation coefficients for computer-program
timings for sudokus
-----------------------------------
[code]
Bri Mer Rae bpd eye kaf xyz duk
Bri -- 22 05 04 07 20 28 36
Mer 22 -- 09 03 08 29 36 42
Rae 05 09 -- 05 01 20 07 12
bpd 04 03 05 -- 00 03 03 02
eye 07 08 01 00 -- 07 07 07
kaf 20 29 20 03 07 -- 23 40
xyz 28 36 07 03 07 23 -- 39
duk 36 42 12 02 07 40 39 --


sum 225 253 162 123 141 245 247 282


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


Can you or others time the 1011 instances at:
http://www.vbforums.com/showthread.php?t=357212
so we can see how programs correlate with
each other ?
Only relative timings are needed, so take any computer
you want or even multiply by a constant.

[PaulIQ164]

I don't know how Poppocom does it, but you could:

-- Start with a finished grid, remove cells one by one, testing to make sure after each removal that the remaining cells yeild a unique solution until no more can be removed. (You probably WON'T get many with only 17 or 18 cells this way.) At this point, you could judge the difficulty of the resulting puzzle based on whatever criteria you choose. If the user was looking for an "easy" one but the puzzle is rated "medium", discard it and repeat.

OR

-- Start with an empty grid, add clues one by one, testing to mae sure after each addition that clues will admit one (or more) solutions. If added clue makes the puzzle unsolvable, it is retracted. Continue until a unique-solution puzzle is found. Rate for difficutly.

I'd imagine Pappocom would use a method much more similar to the second method. Because it's surely that way easier to ensure that none of your clue numbers can be worked out from the others, and that it can be solved using only the methods Pappocom advocates (because at each step of building it, you're "solving" the proto-puzzle yourself, and can choose what methods to use when doing that. I know someone whose made a program to generate sudokus, and this is how he does it, though I don't understand fully how it works, it's pretty close to this, I think.

[angusj]

...which, as you can see below correlates well with other programs as for measuring hardness:

Hi dukuso. I'm sorry I can't tell from your reply whether we're in agreement or disagreement.

Pappocom has requested that puzzle generation techniques not be discussed here so perhaps what I can say to emphasise my point (that fewer givens does not tend to harder puzzles) is - when solving puzzles the hard parts (ie parts requiring complex human solving techniques) are very rarely at the beginning.

[Nick70]

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.