How do they determine the difficulty rating of sudoku puzzles?

[Muse]

I was introduced to sudoku a couple of months ago by my cousin and her husband. In their San Diego newspaper there were published what I think are garden variety sudoku rated from one to five stars in difficulty. These are 9x9 grids with 9 3x3 sub-grids, and every row and column of 9 squares must contain the digits 1-9. Each 3x3 sub-grid must also contain all nine digits 1-9.

I've taken to doing the puzzles published in my local paper, the Oakland Tribune. They appear to be the same type as those I saw in San Diego, rated from one to five stars in difficulty. I'm wondering how they determine the difficulty of these puzzles. My cousin's husband said that some of the puzzles are only solvable if you do a "what if" scenario, and we gave up on the puzzle we were trying, a five star. I'm not willing to resort to "what if" tactics. I've solved some 5 star puzzles pretty easily and been stumped by a couple of 4 star puzzles. I had to wonder if they misjudged the difficulty.

 

[uclabachelor]

I was introduced to sudoku a couple of months ago by my cousin and her husband. In their San Diego newspaper there were published what I think are garden variety sudoku rated from one to five stars in difficulty. These are 9x9 grids with 9 3x3 sub-grids, and every row and column of 9 squares must contain the digits 1-9. Each 3x3 sub-grid must also contain all nine digits 1-9.

I've taken to doing the puzzles published in my local paper, the Oakland Tribune. They appear to be the same type as those I saw in San Diego, rated from one to five stars in difficulty. I'm wondering how they determine the difficulty of these puzzles. My cousin's husband said that some of the puzzles are only solvable if you do a "what if" scenario, and we gave up on the puzzle we were trying, a five star. I'm not willing to resort to "what if" tactics. I've solved some 5 star puzzles pretty easily and been stumped by a couple of 4 star puzzles. I had to wonder if they misjudged the difficulty.

With no prepopulated spaces in an MxM grid, you have N0 solutions.

With 1 populated space in an MxM grid, you have N1 solutions.

... with x populated spaces, you have Nx solutions,

Where N0 >= N1 >= Nx.

There's also the total possible configurations, lets call it Z, given x populated spaces.

The most difficult puzzles would be where Z is maximum and Nx is minimum.

 

[Cogman]

With no prepopulated spaces in an MxM grid, you have N0 solutions.

With 1 populated space in an MxM grid, you have N1 solutions.

... with x populated spaces, you have Nx solutions,

Where N0 >= N1 >= Nx.

There's also the total possible configurations, lets call it Z, given x populated spaces.

The most difficult puzzles would be where Z is maximum and Nx is minimum.

For a sudoku puzzle to be valid, there is can only be 1 solution.

http://www.spiritustemporis.com/sudoku/difficulty.html
http://www.playr.co.uk/sudoku/ratings.php

Modern puzzles are ranked according to the difficulty of the techniques needed to solve the puzzle. Early puzzles were ranked by the number of "given" cells/values (IE, they can be quickly deduced from the given values.)

 

[Muse]

For a sudoku puzzle to be valid, there is can only be 1 solution.

http://www.spiritustemporis.com/sudoku/difficulty.html
http://www.playr.co.uk/sudoku/ratings.php

Modern puzzles are ranked according to the difficulty of the techniques needed to solve the puzzle. Early puzzles were ranked by the number of "given" cells/values (IE, they can be quickly deduced from the given values.)

Yes, well, I'm pretty new at it. I got a few tips from the couple who introduced me to it. I've worked at and solved most of the 50 or so puzzles I've encountered and in doing so have worked up some techniques. I'm not sure I'm using all the techniques necessary. However, I suspect that they don't always correctly identify the difficulty of the puzzles, based on my experience.

The second link above indicates techniques but I don't understand what they're talking about, except for the last being "brute force," to which I have never resorted. However, I understand what they're getting at there.

Level 1 techniques

These techniques are used for filling in cells.

* Cell only has one number in it
* Number only appears as candidate once in a row, column or block

Level 2 techniques

These techniques are used for removing candidate numbers from cells.

* Number appears in a specific row or column within a block
* Number only appears in one block in a row or column
* Number appears in two blocks, twice, in the same row or column
* Number pairs
* Number chains
* Hidden number pairs
* Hidden number chains

Level 3 techniques

These techniques are used for removing candidate numbers from cells but the techniques themselves are more complicated than level 2 techniques.

* X-Wing
* Y-Wing
* Swordfish
* Fishy Cycles
* Colouring

Level 4 techniques

These candidate removal techniques are very powerful, and can solve complicated puzzles with very few clues, but they are quite hard for human solvers to handle.

* Forcing chains
* Nishio

Level 5 techniques

These techniques are extremely complex for humans to attempt, but that is not to say that puzzles with these ratings are impossible, but they may be very time consuming for human solvers.

* Tabling
* Templating
* Brute force trial and error

 

[Mr. Pedantic]

Wish they actually described the techniques instead of giving them stupid and useless names.

 

[Cogman]

Wish they actually described the techniques instead of giving them stupid and useless names.

Its called google, if you are really interested look it up (they aren't just pulling these names out of nowhere)

I don't want every document addressed to me to go into in-depth descriptions about every thing named in it. IE I don't want a full description of the shell sort each time I read about it in a document.

 

[silverpig]

Once you've done enough of them, you'll find that all puzzles are solvable with a strategy you employ. I've pretty much stopped doing them because I don't think I've come across one I can't do now, so it's kind of a pointless exercise.

Yeah there are a few where you get to a point where there's no other technique besides a guess and check, and those are just annoying.

 

[Muse]

Once you've done enough of them, you'll find that all puzzles are solvable with a strategy you employ. I've pretty much stopped doing them because I don't think I've come across one I can't do now, so it's kind of a pointless exercise.

Yeah there are a few where you get to a point where there's no other technique besides a guess and check, and those are just annoying.

It would be nice if you knew in advance with those. One of the sites I've check the last couple days (either linked here or Wikipedia's treatment, don't remember) said that the newspapers usually don't print those, but that's no guarantee and I've been doing a few from WebSudoku:

http://www.websudoku.com/?level=2

I did a couple medium, but started doing Hard. Don't want to mess with Evil. :twisted: The Hard ones are pretty hard. I solved a couple, am stumped on the one I started yesterday. It's hard to know if it's impossible without guessing or I'm just missing something. I figure that I'll get tired of these and give it up. I've got too many priorities. D:

 

[JTsyo]

I do it by filling in all 9 digits into each box and then crossing out options. This makes some boxes more obvious and can point out chains near the end.

 

[DyslexicHobo]

I do it by filling in all 9 digits into each box and then crossing out options. This makes some boxes more obvious and can point out chains near the end.

I use the same strategy. I like to include a 3x3 mini-grid in each cell, marking a small circle for each number that it can be (so if there can be a 5, I put a dot right in the middle of a cell, if a 9 is possible I put a small dot in the bottom right corner of the cell, etc). As I eliminate certain numbers from cells I'll put a slash through the dot. It makes it much easier to visualize some otherwise harder-to-see pairs.

This isn't really viable to start out with on a 5-star board because it can become quite cluttered, but it's a nice strategy to use if you get stuck.

 

[Muse]

... but it's a nice strategy to use if you get stuck.

It's funny. I sail through some 5 star puzzles but I got stuck on a 2 star yesterday!

 

[mckickflip]

i know this very well may not be the optimal solution, but if i were to implement such a feature i would probably do a depth-limited search and then use a fitness function to determine how much of the puzzle the depth-limited search solved and assign it a fitness value accordingly. something along those lines.