AnandTech Forums How do they determine the difficulty rating of sudoku puzzles?
 Register FAQ Calendar Mark Forums Read

Forums
 · Hardware and Technology · CPUs and Overclocking · Motherboards · Video Cards and Graphics · AMD Video Cards · Nvidia · Displays · Memory and Storage · Power Supplies · Cases & Cooling · SFF, Notebooks, Pre-Built/Barebones PCs · Networking · Peripherals · General Hardware · Highly Technical · Computer Help · Home Theater PCs · Consumer Electronics · Digital and Video Cameras · Mobile Devices & Gadgets · Audio/Video & Home Theater · Software · Software for Windows · All Things Apple · *nix Software · Operating Systems · Programming · PC Gaming · Console Gaming · Distributed Computing · Security · Social · Off Topic · Politics and News · Discussion Club · Love and Relationships · The Garage · Health and Fitness · Home and Garden · Merchandise and Shopping · For Sale/Trade · Hot Deals with Free Stuff/Contests · Black Friday 2015 · Forum Issues · Technical Forum Issues · Personal Forum Issues · Suggestion Box · Moderator Resources · Moderator Discussions
 05-07-2010, 09:05 PM #1 Muse Lifer     Join Date: Jul 2001 Location: Under the rainbow over Berkeley Posts: 17,076 How do they determine the difficulty rating of sudoku puzzles? 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. __________________ Quotations on happiness! Last edited by Muse; 05-07-2010 at 09:12 PM.
05-07-2010, 09:21 PM   #2
uclabachelor
Senior Member

Join Date: Nov 2009
Posts: 447

Quote:
 Originally Posted by 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.

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.

05-07-2010, 11:57 PM   #3
Cogman
Lifer

Join Date: Sep 2000
Location: A nomadic herd of wild fainting goats
Posts: 10,055

Quote:
 Originally Posted by uclabachelor 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.)

05-08-2010, 04:42 PM   #4
Muse
Lifer

Join Date: Jul 2001
Location: Under the rainbow over Berkeley
Posts: 17,076

Quote:
 Originally Posted by Cogman 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
__________________
Quotations on happiness!

Last edited by Muse; 05-08-2010 at 04:49 PM.

 05-08-2010, 06:10 PM #5 Mr. Pedantic Diamond Member   Join Date: Feb 2010 Location: Auckland, New Zealand Posts: 5,040 Wish they actually described the techniques instead of giving them stupid and useless names.
05-08-2010, 06:58 PM   #6
Cogman
Lifer

Join Date: Sep 2000
Location: A nomadic herd of wild fainting goats
Posts: 10,055

Quote:
 Originally Posted by Mr. Pedantic 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.

 05-09-2010, 01:42 PM #7 silverpig Lifer     Join Date: Jul 2001 Location: London, UK Posts: 27,710 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. __________________ wifitalk.ca - info on wifi phone apps - google voice / skype / fring
05-10-2010, 09:14 AM   #8
Muse
Lifer

Join Date: Jul 2001
Location: Under the rainbow over Berkeley
Posts: 17,076

Quote:
 Originally Posted by 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.
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. 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.
__________________
Quotations on happiness!

 05-12-2010, 02:12 PM #9 JTsyo Lifer     Join Date: Nov 2007 Location: NJ Posts: 10,009 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.
05-12-2010, 04:53 PM   #10
DyslexicHobo
Senior Member

Join Date: Jul 2004
Posts: 703

Quote:
 Originally Posted by 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.
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.

05-13-2010, 10:45 AM   #11
Muse
Lifer

Join Date: Jul 2001
Location: Under the rainbow over Berkeley
Posts: 17,076

Quote:
 Originally Posted by DyslexicHobo ... 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!
__________________
Quotations on happiness!

 05-22-2010, 11:32 PM #12 mckickflip Member     Join Date: Mar 2008 Posts: 25 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.