1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Determine if a Sudoku puzzle is easy, medium, hard, or evil

  1. Aug 27, 2009 #1
    I can't find a solution to these questions. Can someone help?

    1. An algorithm to determine if a Sudoku puzzle is easy, medium, hard, or evil.

    2. For every valid Sudoku puzzle, there exist at least one valid solution. True or false? Proof?
     
  2. jcsd
  3. Aug 27, 2009 #2
    Re: Sudoku

    I do not know if there is an answer to (1). In my opinion a Sudoku puzzle is "valid" only when it is solvable. However, less than scrupulous publishers print puzzles with two or more consistent solutions. This just isn't cricket in my book. Any good provider of Sudoku subscribes to the Rule of Uniqueness, that there is exactly one solution to a puzzle.

    Does there exist an algorithm to determine if an initial tableau is a valid (and uniquely solvable) puzzle? That I do not know, but would be interested in learning more.

    --Elucidus
     
  4. Aug 28, 2009 #3
    Re: Sudoku

    To elaborate on the second question,

    Is there a sudoku puzzle that no solution exists?
     
  5. Aug 28, 2009 #4
    Re: Sudoku

    if there aren't enough numbers on the grid, then yes, there are unsolvable sudoku puzzles. Like Elucidus said, I assume that if it is a valid puzzle, then it is solvable and not all valid puzzles have unique solutions.

    An algorithm for difficulty would probably consist of the number of numbers given and the amount of similar numbers. More difficult puzzles being those that contain less numbers and also less common numbers.
     
  6. Aug 28, 2009 #5

    Borek

    User Avatar

    Staff: Mentor

    Re: Sudoku

    Define "easy", "medium", "hard" and "evil".

    Define "valid Sudoku puzzle".
     
  7. Aug 28, 2009 #6

    uart

    User Avatar
    Science Advisor

    Re: Sudoku

    I think that the opposite would be true, if there were too many initial numbers given on the grid then it could be inconsistent (no solution). Not enough initial given numbers is more likely to lead to a multiple possible solution situation.
     
  8. Aug 28, 2009 #7
    Re: Sudoku

    true
     
  9. Aug 28, 2009 #8
    Re: Sudoku

    That's the puzzle here. Let's say I created a software program to generate a Sudoku puzzle. Now I need the same software to tell me to tell the difficulty of the puzzle.
    By valid, I simply mean, there is no initial numbers that contradict itself (same numbers in the same row/column/box). I define a puzzle with no initial numbers is the one that has the highest number of solutions. When we add initial numbers, the number of solutions reduce. At some point we get only one solution. But can I make it one with no possible solution, by strategically placing the numbers?
     
    Last edited: Aug 28, 2009
  10. Aug 28, 2009 #9

    uart

    User Avatar
    Science Advisor

    Re: Sudoku

    With that definition of "valid" then yes there most certainly are "valid" initial numbers which give rise to a puzzle with no solutions.

    Here is a trivial example (shows the two upper left cells only, all other cells are blank)
    Code (Text):

     1 2   | 3     |
           |       |
     4 5 6 |       |
           |       |
     7 8 9 |       |
    ---------------
     
     
  11. Aug 28, 2009 #10
    Re: Sudoku

    Another example:

    . . . | . . . | . . .
    . . . | . 2 1 | . . .
    . . . | . . . | . 2 1
    ------+-------+------
    . . . | . . . | . . .
    . 2 . | . . . | . . .
    . 1 . | . . . | . . .
    ------+-------+------
    . . . | . . . | . . .
    . . 2 | . . . | . . .
    . . 1 | . . . | . . .


    The number in the upper left corner needs to be both one and 2.
     
  12. Aug 28, 2009 #11
    Re: Sudoku

    Ah...Thanks uart and MooOfDoom. I should have found it myself :(.

    I was trying to think of a possible variation of sudoku - 2 people play, start with no initial numbers, each player adds a number alternately: player A tries to solve the puzzle and win, player B aims to prevent player A from winning.

    From your examples, the game seems to be always favoring player B. (I need to think another variation of it.)

    As Elucidus asked,
    Does there exist an algorithm to determine if an initial tableau is a uniquely solvable puzzle?
     
  13. Aug 28, 2009 #12

    DavidSnider

    User Avatar
    Gold Member

    Re: Sudoku

    The way you rate how hard a sudoku puzzle is by writing a sudoku solver and setting thresholds for the number of lookups it has to do.
     
  14. Aug 28, 2009 #13

    Borek

    User Avatar

    Staff: Mentor

    Re: Sudoku

    Different solver may give different results, so it is still ambiguous.
     
  15. Aug 28, 2009 #14

    drizzle

    User Avatar
    Gold Member

    Re: Sudoku

    would it be like this
    2 1 . | . . . | . . .
    . . . | . 2 1 | . . .
    . . . | . . . | . 2 1
    ------+-------+------
    . . . | . . . | . . .
    . 2 . | . . . | . . .
    . 1 . | . . . | . . .
    ------+-------+------
    . . . | . . . | . . .
    . . 2 | . . . | . . .
    . . 1 | . . . | . . .


    or this

    2 . . | . . . | . . .
    1 . . | . 2 1 | . . .
    . . . | . . . | . 2 1
    ------+-------+------
    . . . | . . . | . . .
    . 2 . | . . . | . . .
    . 1 . | . . . | . . .
    ------+-------+------
    . . . | . . . | . . .
    . . 2 | . . . | . . .
    . . 1 | . . . | . . .
     
  16. Aug 28, 2009 #15
    Re: Sudoku

    Can a sudoku generator determine the complexity, without trying to solve it?

    [EDIT] Probably not. My thinking is as follows.

    A puzzle may have different paths to reach the unique solution. The less number of paths means it's a harder puzzle.

    Make any sense?
     
    Last edited: Aug 28, 2009
  17. Aug 29, 2009 #16
    Re: Sudoku

    Neither of those are valid, since a row or column contains two 1's.
     
  18. Aug 29, 2009 #17

    Borek

    User Avatar

    Staff: Mentor

    Re: Sudoku

    Not necesarilly. There are several simple methods of checking what the next digits can be (see http://theory.tifr.res.in/~sgupta/sudoku/algo.html for example). Simple puzzle is the one where you can find out each next digit using always the same simple method. More complicated one requires use of different methods in each next step.

    Form http://sudokuplace.com/sudoku_scoring.asp: [Broken]

    Sounds reasonable.
     
    Last edited by a moderator: May 4, 2017
  19. Aug 29, 2009 #18
    Re: Sudoku

    1. Yes, it can determine the complexity of the sudoku game, but first it need to solve it. Also before solving it, you must "define" the levels: easy, medium, hard, evil etc... Maybe "hard" have two or three valid solutions, "evil" ten etc... Also you may define the level by cycles i.e how many cycles should program made to solve the sudoku game or how much time it needs to solve the game. You got too many factors for defining the levels.

    2. One sudoku game could have one, two, three or more solutions, or simply no solution. The prove is in the posts above. :smile:
     
  20. Aug 29, 2009 #19
    Re: Sudoku

    I find Sudoku puzzles that have more than one solution too be highly irritating (admittedly after several hundred puzzles, this has happened only a few times). I have made a point of only purchasing Sudoku books that state that the puzzles within are uniquely solvable.

    Rating the complexity of a puzzle on the number of different solutions it has seems to be inappropriate since a blank puzzle grid has zillions of solutions which are fairly easy to fabricate. Due to my bias against multiple solutions I would reject such a measure - but that's just me.

    I would think that the complexity of a puzzle would be determined by the most difficult method involved (and then by how many times it's used). Any Sudoku can be solved by sequential "what if" type tests (a very inelegant way IMO) and is not a very good measure of complexity.

    I have solved Sudoku puzzles in a little as 2 minutes, while the hardest took me seven hours. I would be very curious if there were a way to measure the complexity from the intial tableau.

    --Elucidus
     
  21. Aug 30, 2009 #20

    drizzle

    User Avatar
    Gold Member

    Re: Sudoku

    then what you meant is either 1 or 2 will fit in the top left corner cell

    here's where I misunderstood you :tongue:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Determine if a Sudoku puzzle is easy, medium, hard, or evil
  1. A puzzle (Replies: 3)

  2. A puzzle (Replies: 7)

Loading...