Identifying Features in Trouble Sudoku Puzzles: Techniques for Classification

[WWGD]

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.

 

[fresh_42]

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/polymath/htmlS/Studenti/Tesi/SudokuGame/tesi_Mancini_Simona%20SUDOKU.pdf

 

[WWGD]

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/polymath/htmlS/Studenti/Tesi/SudokuGame/tesi_Mancini_Simona%20SUDOKU.pdf

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)?

 

[fresh_42]

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)?

At least the Italians discuss it although I don't find their paper very clear.

 

[mfb]

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.

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.

 

[jedishrfu]

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.

 

[mfb]

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.

I don't know if you can arbitrarily select 17 clue squares and be assured of a unique and solvable puzzle.

You cannot. See above: Even with 77 the solution doesn't have to be unique.

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.

Sure.

 

[WWGD]

<Snip>). 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.

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.

 

[mfb]

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.

 

[WWGD]

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.

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.

 

[mfb]

How so, for a 3x3 block?

As I said: It does not.
You have 9! options to fill a 3x3 block.

 

[WWGD]

As I said: It does not.
You have 9! options to fill a 3x3 block.

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.

 

[mfb]

It does not follow.
As I said twice already.

 

[WWGD]

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.

 

[mfb]

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.

Right.

But we have more possible Sudokus.

 

[WWGD]

Right.

But we have more possible Sudokus.

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.

 

[mfb]

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.

 

[WWGD]

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.

 

[mfb]

Then, given a selection on the first row, there are 8 choices for the first space to be filled in a contiguous row

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.

 

[WWGD]

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.

Ouch, good point, I missed that. How careless..

 

[WWGD]

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.

I was counting Latin Squares, which is what I was first considering : (.

 

[WWGD]

Ok, I guess things got of-track. Any other idea on how I can identify features that differentiate the ones I can solve from the ones I cannot ( I have cases of each type)?

 

[TheSlovakEngineer]

Hello, I am writing a sudoku solver/generator and the way I see it is you classify the sudokus by the steps taken to solve them. If you want, I can help you out once I am finished with my human solver. So far, it is very rudimentary, but it can still solve most sudokus in the newspapers. I think that is because most of those are easy even if classified as very hard. I have a probability random solver ready if you just want the solution. I need the sudokus in string form like this:
4...8.5.3...7...2...6...8.4...1...6.3.7.5..2...1.4...
Or you can replace the dots with zeroes.

 

[TheSlovakEngineer]

Ok, I guess things got of-track. Any other idea on how I can identify features that differentiate the ones I can solve from the ones I cannot ( I have cases of each type)?

I wrote how I can help you out. If you don't want to write the sudokus just give them to me in the form you have and I will figure something out.

 

[WWGD]

I wrote how I can help you out. If you don't want to write the sudokus just give them to me in the form you have and I will figure something out.

Thank you Slovak, I am interested in solving but also in classifying. I will maybe PM you an attachment with the ones I cannot solve.

 

[TheSlovakEngineer]

Thank you Slovak, I am interested in solving but also in classifying. I will maybe PM you an attachment with the ones I cannot solve.

Well, there are a lot of algorithms to solve a puzzle and as far as I know the way to classify it is by the algorithms used to solve it. Maybe there is a mathematical way, but I am rather lost there.