How do they determine the difficulty rating of sudoku puzzles?

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

  1. Muse

    Muse Lifer

    Joined:
    Jul 11, 2001
    Messages:
    17,260
    Likes Received:
    4
    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 Muse, May 7, 2010
    Last edited: May 7, 2010
  2. uclabachelor

    uclabachelor Senior member

    Joined:
    Nov 9, 2009
    Messages:
    447
    Likes Received:
    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.
     
  3. Cogman

    Cogman Lifer

    Joined:
    Sep 19, 2000
    Messages:
    10,086
    Likes Received:
    14
    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.)
     
  4. Muse

    Muse Lifer

    Joined:
    Jul 11, 2001
    Messages:
    17,260
    Likes Received:
    4
    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 Muse, May 8, 2010
    Last edited: May 8, 2010
  5. Mr. Pedantic

    Mr. Pedantic Diamond Member

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

    Cogman Lifer

    Joined:
    Sep 19, 2000
    Messages:
    10,086
    Likes Received:
    14
    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.
     
  7. silverpig

    silverpig Lifer

    Joined:
    Jul 29, 2001
    Messages:
    27,710
    Likes Received:
    0
    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.
     
  8. Muse

    Muse Lifer

    Joined:
    Jul 11, 2001
    Messages:
    17,260
    Likes Received:
    4
    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:
     
  9. JTsyo

    JTsyo Lifer

    Joined:
    Nov 18, 2007
    Messages:
    10,083
    Likes Received:
    8
    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.
     
  10. DyslexicHobo

    DyslexicHobo Senior member

    Joined:
    Jul 20, 2004
    Messages:
    703
    Likes Received:
    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.
     
  11. Muse

    Muse Lifer

    Joined:
    Jul 11, 2001
    Messages:
    17,260
    Likes Received:
    4
    It's funny. I sail through some 5 star puzzles but I got stuck on a 2 star yesterday! :eek:
     
  12. mckickflip

    mckickflip Member

    Joined:
    Mar 19, 2008
    Messages:
    25
    Likes Received:
    0
    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.
     
Loading...