# How do they determine the difficulty rating of sudoku puzzles?

Discussion in 'Highly Technical' started by Muse, May 7, 2010.

1. ### Muse Lifer

Joined:
Jul 11, 2001
Messages:
18,433
87
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.

#1
Last edited: May 7, 2010

2. Similar Threads - determine difficulty rating Forum Date
Difficulties Magnetizing Plain Steel Highly Technical Feb 16, 2013
Relativistic Determinism Highly Technical Oct 25, 2012
How to determine if videos are playing via Hardware acceleration or not? Highly Technical Jul 10, 2012
Determining Sample Sizes Highly Technical Nov 18, 2011
How soon after a sine wave reaches the eardrum can the brain determine what its frequency is? Highly Technical Feb 25, 2009

3. ### uclabachelor Senior member

Joined:
Nov 9, 2009
Messages:
448
0

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.

#2
4. ### Cogman Lifer

Joined:
Sep 19, 2000
Messages:
10,135
19
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.)

#3
5. ### Muse Lifer

Joined:
Jul 11, 2001
Messages:
18,433
87
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

#4
Last edited: May 8, 2010
6. ### Mr. Pedantic Diamond Member

Joined:
Feb 14, 2010
Messages:
5,040
0
Wish they actually described the techniques instead of giving them stupid and useless names.

#5
7. ### Cogman Lifer

Joined:
Sep 19, 2000
Messages:
10,135
19
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.

#6
8. ### silverpig Lifer

Joined:
Jul 29, 2001
Messages:
27,710
1
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.

#7
9. ### Muse Lifer

Joined:
Jul 11, 2001
Messages:
18,433
87
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:

#8
10. ### JTsyo Lifer

Joined:
Nov 18, 2007
Messages:
10,382
61
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.

#9
11. ### DyslexicHobo Senior member

Joined:
Jul 20, 2004
Messages:
703
0
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.

#10
12. ### Muse Lifer

Joined:
Jul 11, 2001
Messages:
18,433
87
It's funny. I sail through some 5 star puzzles but I got stuck on a 2 star yesterday!

#11

Joined:
Mar 19, 2008
Messages:
25