Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A "Classifying" Sudoku Puzzles

Tags:
  1. Apr 20, 2017 #1

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    Hi All,
    I am trying to identify features in Sudoku puzzles that separate the "trouble" ones that are hard for me from the ones that are not. But I am having trouble finding techniques to do this.
    I have been a fan of solving the standard 9x9 Sudoku puzzles, specially the "Evil" type from http://www.websudoku.com/ . I can solve many but there always seems to be some I cannot solve. I have kept copies of those I cannot solve ( as screenshots) . The number of blank cells at the beginning is the same for all, at 55 out of 81. What kinds of techniques can I use to find common traits in these "trouble" ones? I am thinking factor analysis, but I cannot come up with any factors to start with. I can maybe find a metric on Sudokus ## S_i, S_j ## dealing with the number of filled squares after 10 minutes and set ##d(S_i,S_j)=0 ## if the number of filled squares in each, after 10 minutes is the same , say ## \pm 2 ## (with some adjustments, to allow for the solved ones, etc.) to obtain classes and this may allow me to find some common variables (factors/components) within classes. Any other ideas? Sorry if this is simple, I labeled it as Graduate+ , maybe it is not?
    EDIT: Note that 55 blanks out of 81 subsquares is not , by itself, enough to solve a generic Sudoku, but supposedly the ones I am referring to are solvable in the sense that there is a unique solution satisfying the initial conditions.
     
  2. jcsd
  3. Apr 20, 2017 #2

    fresh_42

    Staff: Mentor

    Is there a conspiracy underway?

    In the end it's an equation system with unknowns so you can always count the unknowns and the equations. As an NP-complete problem, I think the difficulty goes approximately with ##O(n^3)## but that's a wild guess. Worst case is ##O(9^m)## and somewhere I found ##O(n^2)## in time which I find a little bit low.

    Wikipedia is pretty comprehensive:
    https://en.wikipedia.org/wiki/Mathematics_of_Sudoku
    https://en.wikipedia.org/wiki/Sudoku_solving_algorithms

    Also interesting:
    http://areeweb.polito.it/didattica/...esi/SudokuGame/tesi_Mancini_Simona SUDOKU.pdf
     
  4. Apr 20, 2017 #3

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    Thanks for the links , but my classification scheme, for the ones I have trouble doing may not be the same as the one described in the links you gave. I read but did not see, e.g., what type of Sudokus with 55 empty cells are "allowable" , i.e., have a unique solution. Or did I miss this ( Sorry if I did)?
     
  5. Apr 20, 2017 #4

    fresh_42

    Staff: Mentor

    At least the Italians discuss it although I don't find their paper very clear.
     
  6. Apr 20, 2017 #5

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    You can have multiple solutions even with 77 out of 81 cells fixed.

    You could try to determine how many "mental steps" you need to find a number.

    - Is there a field where you can directly rule out 8 of 9 numbers based on the row/column/3x3 square? If yes, that is easy.
    - Is there are row, column or 3x3 square where a number can be ruled out for all places but one? If yes, that is pretty easy, but not as easy as the previous rule
    - Is there a group of 2 or 3 squares where you can find all numbers that will go there (e. g. "these fields are 3 and 5")? If yes, try to apply the previous two rules again. More interesting.
    - Do you need multiple steps of "if this is an 8, then the 6 has to be there, then ..."? That is difficult.

    Did you look how Sudoku solvers do this? At least some programs don't use brute force, but solve it human-like.


    For Minesweeper, there is Chocolate Sweeper: Minesweeper puzzles where you never have to guess - but some of the puzzles are extremely complex. Have a look at the tweets for not-so-difficult (!) examples. The app has an internal evaluation how difficult each move was. You can reduce Minesweeper to a set of linear equations, basically counting mines: x+y+z=1 means either x, y or z is a mine, and so on. The app calculates how many linear equations you have to solve to find the spot you uncovered, and awards you points for that. A similar approach could work for Sudoku. I guess you can ask the App author how exactly he did that.
     
  7. Apr 20, 2017 #6

    jedishrfu

    Staff: Mentor

    One question I had was how many unique sudoku maps are there once you take into account all the symmetries.

    Is it just one or more than one?

    By symmetry I mean interchanging any two minor rows in a group, any two minor columns in a group column, any two row groups, and any two column groups.

    This is a trick you can do for computer generated sudoku puzzles starting with a known solution and applying one or more symmetries to produce a new and unique sudoku puzzle. You have to still preserve the clue squares I suspect as you apply the transforms. I don't know if you can arbitrarily select 17 clue squares and be assured of a unique and solvable puzzle.

    This brings up another interesting question, if you have an unsolved sudoku where you can transform it somewhat without touching any of the clue squares then perhaps that puzzle has multiple solutions.
     
  8. Apr 20, 2017 #7

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Yes, there are many different Sudoku maps, even if we consider more symmetries (exchanging all X with Y, or rotating/mirroring the board, or making 3x3 cells out of rows, for example). I'm sure the Wikipedia article has the number.
    You cannot. See above: Even with 77 the solution doesn't have to be unique.
    Sure.
     
  9. Apr 20, 2017 #8

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    Is that why the total number of 9x9 Sudokus is not 9!8!7!...3!2!1! (According to Wiki it is around ## 6.67x 10^{21} ##? The count works for the very trivial case of the 4x4 Sudokus. Kind of typical that one example is too small, trivial and the next one is way too big and complex.
     
  10. Apr 21, 2017 #9

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    If that would be the total number, then giving a single row, column or 3x3 block would lead to a unique solution (not looking at symmetries now). It does not.
     
  11. Apr 21, 2017 #10

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    How so, for a 3x3 block? A column below the block by itself can be completed in 6! ways, same for a row intersecting the block. EDIT: Notice that 9!*8!*7!...*2*1 is ## 1.83 \times 10^{21}## , between 1/3 and 1/4 of the total amount of ## 6.67 \times 10^{21} ## so it is not that far off, just by a factor of around 3.65. And knowing a single row still allows for 8! arrangements in the next row, etc. I don't see how you have reached your conclusions.
     
    Last edited: Apr 21, 2017
  12. Apr 21, 2017 #11

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    As I said: It does not.
    You have 9! options to fill a 3x3 block.
     
  13. Apr 21, 2017 #12

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    And plenty of options to fill in the remainders, according to my method so I don't see how it follows that by my count, knowing a 3x3 block fully determines the rest.
     
  14. Apr 21, 2017 #13

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    It does not follow.
    As I said twice already.
     
  15. Apr 21, 2017 #14

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    You can say it as many times as you wish, I have no idea of what you are saying. I understood you to say that if the total count of 9x9 Sudokus is 9!8!7!..2!1! then knowing a full 3x3 fully determined the rest of the puzzle. Is that what you said/meant? Otherwise I have no clue of what you are saying. We may as well call off this exchange.
     
  16. Apr 21, 2017 #15

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Right.

    But we have more possible Sudokus.
     
  17. Apr 21, 2017 #16

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    Well, I just don't see how your contention that [if the total is 9!8!..2!1 then knowing a 3x3 sub-square uniquely determines the rest] follows. I think I showed this contention within the brackets is false. You only made that assertion but I did not see any supporting argument and I believe your assertion ( within the brackets in this post) is false. EDIT: If you cannot provide an argument for it that I can find clear, let's drop it, it seems to be going nowhere.
     
  18. Apr 21, 2017 #17

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Wait, where did the additional factorials come in. I read that as 9*8*...=9!.

    Why 9!8!..2!1 ? If we fill it row by row, the first row has 9! options. The first cell in the second row has 6 options (3 are blocked by the 3x3 block), the second one has 5 options, the third one has 4 options. The options for the following entries depend on the choices we made for the previous numbers.
     
  19. Apr 21, 2017 #18

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    I was assuming we fill in one row/column at a time, to sort-of standardize the question. Say row for definiteness. Then, given a selection on the first row, there are 8 choices for the first space to be filled in a contiguous row, 7 choices for the second square to be filled-in, for the third row, we have 7! choices, etc. Filled this way, I think the total is 9!8!7!...3!2!1! . A similar argument for the simple case for the 2x2 Sudoku holds; there are 288=4!3!2!1! possible Sudokus.
     
  20. Apr 21, 2017 #19

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Only if you start in a separate 3x3 block, something you cannot do more than 3 times in total. Otherwise you have to take the blocks into account.

    Assuming we have a new 3x3 block: The second choice in the second row can have 7 or 8 options, the third option can have 6 or 7 options, and so on, it depends on what you put in the row already.
     
  21. Apr 21, 2017 #20

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    Ouch, good point, I missed that. How careless..
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: "Classifying" Sudoku Puzzles
  1. Probability puzzle (Replies: 27)

  2. Hat puzzle (Replies: 4)

Loading...