Is there any mathematical measure to determine the complexity of a SuDoku puzzle?

easy sudoku
Kads asked:

I love solving sudoku puzzles ranging from easy to hard. I have observed that easier ones have >30 digits pre-filled, while harder ones have <26 digits pre-filled. However, this is more of an observation than a rule. e.g. Hard puzzles still appear difficult at times, even when I have managed to fill in 5-6 blank spaces. Of course, there comes a point when the sparseness is substantially reduced, and it looks trivial thereafter. Naturally, there is more to the complexity of a sudoku than just the # of pre-filled digits. Perhaps the arrangement or pattern?



Comments (6)    Posted in Mathematics    

Subscribe RSS 2.0 feed. Leave a response, or Trackback from your own site.




6 Responses to 'Is there any mathematical measure to determine the complexity of a SuDoku puzzle?'

  1. kayla - May 31st, 2009 at 9:08 pm

    Just enjoy the Sudoku. Why do you have to analyze it?

  2. Jenae - June 3rd, 2009 at 8:36 am

    the arrangement make s a whoooole lot of difference

  3. ettezzil - June 6th, 2009 at 11:26 am

    i think the position of the numbers makes the difference cause even you’re left with two numbers, you still can’t decide where to put it \, to the first or second slot :)

  4. pablodiablo1981 - June 8th, 2009 at 3:40 am

    I think the difficulty level classifications are based on the maximum amount of logic that will be required to solve that particular puzzle. An easy puzzle will never require forward-thinking, and the hardest puzzles may require you to think a few steps ahead. That is to say, on the hard ones, you will always reach a point where you cannot proceed any further unless you are able to solve multiple parts of the grid simultaneously.

    You are correct that both the number of pre-filled digits, and their arrangement dictate the difficulty. You will always be given at least enough digits to ensure that there is one and only one solution. The mathematics involved are actually much more complex than it might seem.

    The wiki on this subject is quite excellent (see link below). It says in that article that 17 is the absolute minimum number of digits that must be supplied to ensure a unique solution. Also, there are more than 6*10^21 possible ways of filling a standard Sudoku grid.

  5. Ariel - June 10th, 2009 at 10:25 pm

    sudoku is not considered a mathematical problem by prominent mathematicians!

  6. David D - June 10th, 2009 at 11:41 pm

    The answer may be here.


Leave a Reply