Go Back   AnandTech Forums > Hardware and Technology > Highly Technical

Forums
· Hardware and Technology
· CPUs and Overclocking
· Motherboards
· Video Cards and Graphics
· 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
· Merchandise and Shopping
· For Sale/Trade
· Hot Deals with Free Stuff/Contests
· Black Friday 2014
· Forum Issues
· Technical Forum Issues
· Personal Forum Issues
· Suggestion Box
· Moderator Resources
· Moderator Discussions
   

Reply
 
Thread Tools
Old 05-07-2010, 09:05 PM   #1
Muse
Lifer
 
Muse's Avatar
 
Join Date: Jul 2001
Location: Under the rainbow over Berkeley
Posts: 14,446
Default 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.
Muse is offline   Reply With Quote
Old 05-07-2010, 09:21 PM   #2
uclabachelor
Senior Member
 
uclabachelor's Avatar
 
Join Date: Nov 2009
Posts: 345
Default

Quote:
Originally Posted by Muse View Post
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.
uclabachelor is offline   Reply With Quote
Old 05-07-2010, 11:57 PM   #3
Cogman
Diamond Member
 
Cogman's Avatar
 
Join Date: Sep 2000
Location: A nomadic herd of wild fainting goats
Posts: 9,779
Default

Quote:
Originally Posted by uclabachelor View Post
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.)
Cogman is offline   Reply With Quote
Old 05-08-2010, 04:42 PM   #4
Muse
Lifer
 
Muse's Avatar
 
Join Date: Jul 2001
Location: Under the rainbow over Berkeley
Posts: 14,446
Default

Quote:
Originally Posted by Cogman View Post
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.
Muse is offline   Reply With Quote
Old 05-08-2010, 06:10 PM   #5
Mr. Pedantic
Diamond Member
 
Join Date: Feb 2010
Location: Auckland, New Zealand
Posts: 4,877
Default

Wish they actually described the techniques instead of giving them stupid and useless names.
Mr. Pedantic is offline   Reply With Quote
Old 05-08-2010, 06:58 PM   #6
Cogman
Diamond Member
 
Cogman's Avatar
 
Join Date: Sep 2000
Location: A nomadic herd of wild fainting goats
Posts: 9,779
Default

Quote:
Originally Posted by Mr. Pedantic View Post
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.
Cogman is offline   Reply With Quote
Old 05-09-2010, 01:42 PM   #7
silverpig
Lifer
 
silverpig's Avatar
 
Join Date: Jul 2001
Location: London, UK
Posts: 27,709
Default

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.
silverpig is offline   Reply With Quote
Old 05-10-2010, 09:14 AM   #8
Muse
Lifer
 
Muse's Avatar
 
Join Date: Jul 2001
Location: Under the rainbow over Berkeley
Posts: 14,446
Default

Quote:
Originally Posted by silverpig View Post
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!
Muse is offline   Reply With Quote
Old 05-12-2010, 02:12 PM   #9
JTsyo
Diamond Member
 
JTsyo's Avatar
 
Join Date: Nov 2007
Location: NJ
Posts: 9,110
Default

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.
JTsyo is offline   Reply With Quote
Old 05-12-2010, 04:53 PM   #10
DyslexicHobo
Senior Member
 
Join Date: Jul 2004
Posts: 702
Default

Quote:
Originally Posted by JTsyo View Post
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.
DyslexicHobo is offline   Reply With Quote
Old 05-13-2010, 10:45 AM   #11
Muse
Lifer
 
Muse's Avatar
 
Join Date: Jul 2001
Location: Under the rainbow over Berkeley
Posts: 14,446
Default

Quote:
Originally Posted by DyslexicHobo View Post
... 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!
Muse is offline   Reply With Quote
Old 05-22-2010, 11:32 PM   #12
mckickflip
Member
 
mckickflip's Avatar
 
Join Date: Mar 2008
Posts: 25
Default

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.
mckickflip is offline   Reply With Quote
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -5. The time now is 02:59 AM.


Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2014, vBulletin Solutions, Inc.