21 posts
• Page **1** of **2** • **1**, 2

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

- kat
**Posts:**10**Joined:**19 July 2005

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.

- Addlan
**Posts:**62**Joined:**15 July 2005

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!

Cafepress Sudoku Store!

- graatz
**Posts:**2**Joined:**28 August 2005

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.|...|

*-----------*

- tso
**Posts:**798**Joined:**22 June 2005

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).

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).

- Moschopulus
**Posts:**256**Joined:**16 July 2005

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.

- PaulIQ164
**Posts:**533**Joined:**16 July 2005

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.

- PaulIQ164
**Posts:**533**Joined:**16 July 2005

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:

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 . . | . . .

- tso
**Posts:**798**Joined:**22 June 2005

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+

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........

- dukuso
**Posts:**479**Joined:**25 June 2005

dukuso wrote: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.

- angusj
**Posts:**306**Joined:**12 June 2005

angusj wrote:dukuso wrote: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.

- dukuso
**Posts:**479**Joined:**25 June 2005

tso wrote: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.

- PaulIQ164
**Posts:**533**Joined:**16 July 2005

dukuso wrote:...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.

- angusj
**Posts:**306**Joined:**12 June 2005

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.

- Nick70
**Posts:**156**Joined:**16 June 2005

21 posts
• Page **1** of **2** • **1**, 2