The New Sudoku Players' Forum

[MCC]

Code: Select all

 *-----------*
 |123|...|...|
 |...|123|...|
 |...|...|123|
 |---+---+---|
 |...|.12|3..|
 |...|...|.12|
 |---+---+---|
 |..1|2..|...|
 |...|..1|2..|
 |...|...|..1|
 *-----------*


Cec

I should point out, since no one else has, that Cec's grid has only 8 rows.

MCC

[Cec]

"..What are the characteristics that make a sudoku puzzle easy, medium or hard?"

Whilst there may be exceptions, I usually find the number of "clues" (given numbers) in a puzzle indicates the degree of difficulty. This seems to be supported by the minimum number of clues - I think it's 17 - which are considered necessary to solve a puzzle. Unless I'm missing something I would expect a puzzle is more difficult when identical clues are repeated within the boxes like this:

Code: Select all

 *-----------*
 |123|...|...|
 |...|123|...|
 |...|...|123|
 |---+---+---|
 |.12|3..|...|
 |...|.12|3..|
 |...|...|.12|
 |---+---+---|
 |..1|2..|...|
 |...|..1|2..|
 |...|...|..1|
 *-----------*


Cec

The number of clues has *no* correlation with the difficulty of the puzzle. There 17's that are trivial and 17s that are very difficult. A 17 chosen at random from the 36 thousand here is more likely to be easy than hard.

For example, this one requires nothing but singles. Pappocom rates it as Medium, but I'm sure I could find one it would rate as Easy.

Code: Select all

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

Conversely, one might find the hardest part of a particular puzzle when it is 2/3's filled in. You could then consider this position as the starting point of a very difficult puzzle that has 54 givens.


As to your second point -- I doubt it.

[vidarino]

I would of course be interested to know what characteristics you believe make a sudoku puzzle easy, medium or hard.?

First, as many has stated, the number of clues isn't directly related to the difficulty of a puzzle. I will agree, though, that in many published (and possibly hand-made) puzzles, the two do appear to be related.

IMHO, the "real" measurement of difficulty is the number of solution paths a puzzle has, and which techniques each step requires. For argument's sake, assume we limit ourselves to the most basic techniques, naked and hidden singles.

If it is, at any given point in the solution process, possible to fill in at least 5 different numbers, the puzzle will probably be rated Easy. However, if there is only one number that is a naked or hidden single, and that opens up for another lonely single, etc., all the way to the end, it's probably going to be rated Hard or Fiendish or something thereabout.

So the number of single-solvable cells for a grid is actually quite unrelated to the number of clues your start with. As just above this post, the harder puzzles often doesn't get hard until about halfway into the solution, which would be illogical if there were a relationship.

One more thing, though... If you take a hard puzzle and add random, not-yet-deductable clues to it, you will also likely add solutions paths to the puzzle (unless you place them carefully in non-critical cells), and it will become easier. Hmm, perhaps that's what the publishers are doing. That would explain the correlation you noticed.

Vidar

[Cec]

I should point out, since no one else has, that Cec's grid has only 8 rows.
MCC

Thanks for that MCC. Well done! You succeeded in spotting my observation test I've corrected it above the best I can. Now 2AM and too tired. Will look again at this tomorrow after just noticing vidarino has replied to my request to tso to comment.
Cec

[vidarino]

... noticing vidarino has replied to my request to tso to comment.

Oops, I just took your remark as a general request for comments. Hope nobody minds that i threw in my few cents.

[tso]

Is a walking 100 yards on flat ground under sunny skies more difficult than walking 50 yards, all other conditions being equal? It certainly takes longer, but whether it is more difficult is subjective. If you are a 10 year old child in perfect health, you will probably not perceive any difference in difficulty. If you are an 80 year old multiple health issues, the 100 yards may not only be more difficult that the 50 -- it could even be impossible.

Two puzzles, both can be solved with nothing but singles. The first has singles every where you look, the second rarely has more than one cell that can be solved. The first will be solved much more quickly by most human solvers. Many people would rate it easier than the second (Pappocom certainly would) -- but to others, they differ only by 50 yards. What sort of help could and expert give a novice on one of these "hard" puzzles other than "only singles are needed"?

This distinction is even more noticable when using software that automates pencilmarks, filters for candidates or automatically highlights cells that contain singles. All singles-only puzzles, regardless of ratings, can be solved just as swiftly under these circumstances. But the software isn't giving any answers, it's just doing 'housekeeping'. Can we really say that these puzzles have different difficulty levels now?

Is solving two puzzles more difficult than solving one?

I find a puzzle that's type-set is *much* easier to solve than the same one if it is hand written.
I find a puzzle printed large is *much* easier to solve than the same one printed small.

Which is harder -- walking 10 miles on a paved road or walking 1 mile over mixed terrian, sand, mud, boulders, etc. How do you measure? Time taken? Or chance of failure? The 10 miles will take longer, but if you haven't prepared or if you make a mistake, you might never finish the short course. Learning from your first attempt, tomorrow the short course may be a breeze.

Which is "hotter" -- a loaf of bread taken from a 350 degree oven or a cup of coffee right out of the pot? You can hold the bread in your hands without danger because it lacks density, but the coffee will burn you.

[Cec]

... noticing vidarino has replied to my request to tso to comment.

Oops, I just took your remark as a general request for comments. Hope nobody minds that i threw in my few cents.

No problem Vidar. Your comments were interesting and today with a clearer head I can see I could have worded my above post better.

First, as many has stated, the number of clues isn't directly related to the difficulty of a puzzle. I will agree, though, that in many published (and possibly hand-made) puzzles, the two do appear to be related.

Well, because you're saying the "two" (viz. clues vs puzzle difficulty) appear to be related then perhaps this gives some support to my above views.

Thanks also to tso and others for the above comments which has given me more insight into the various factors that can influence the difficulty rating of puzzles. I guess newhere who asked the initial question of what are the characteristics that make a sudoku puzzle easy, medium or hard, would still be wondering what the answer is.

Cec

[Trainspotter]

One factor that I have not seen discussed is the difference between human and computer based perceptions of difficulty. For example, to a solver program, all sudokus that require finding a hidden triplet are likely to be rated at about the same difficulty level (at least for that step of the solution process). The difference in run time taken to find the triplet depends on the order in which the possible combinations of three cells are considered, but this is probably not going to be taken into account in the rating formula. For me, finding a hidden triplet is very much easier if the three cells are grouped in a bunch, e.g. adjacent in the same row or column. It would be rather unnatural for a programmed search to look for all such possibilities before considering the more widely spread triplet possibilities, let alone rate the puzzle accordingly.

I expect that at least some solvers would agree that bunched triplets are easier to spot, but I would not expect any two human solvers to agree 100% about the rating of puzzles. I therefore do not regard rating the difficulty of sudoku puzzles as a problem with an exact solution. (I do think that a rating formula which takes into account the complexity of the steps required to solve a puzzle, as well as the number of steps, is useful as a general guide.)

Jeff