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

[jobyts]

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?

 

[Elucidus]

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

 

[jobyts]

To elaborate on the second question,

Is there a sudoku puzzle that no solution exists?

 

[redargon]

To elaborate on the second question,

Is there a sudoku puzzle that no solution exists?

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.

 

[Borek]

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

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

2. For every valid Sudoku puzzle, there exist at least one valid solution. True or false? Proof?

Define "valid Sudoku puzzle".

 

[uart]

if there aren't enough numbers on the grid, then yes, there are unsolvable sudoku puzzles.

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.

 

[redargon]

true

 

[jobyts]

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

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.

Define "valid Sudoku 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?

 

[uart]

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?

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)

 1 2   | 3     |
       |       |
 4 5 6 |       |
       |       |
 7 8 9 |       |
---------------

 

[Moo Of Doom]

Another example:

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

The number in the upper left corner needs to be both one and 2.

 

[jobyts]

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?

 

[DavidSnider]

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.

 

[Borek]

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.

Different solver may give different results, so it is still ambiguous.

 

[drizzle]

Another example:

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

The number in the upper left corner needs to be both one and 2.

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

 

[jobyts]

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.

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?

 

[Moo Of Doom]

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

Neither of those are valid, since a row or column contains two 1's.

 

[Borek]

The less number of paths means it's a harder puzzle.

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:

The primary factor which determines difficulty is the number of cells which can be solved at a given point.

Sounds reasonable.

 

[njama]

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.

 

[Elucidus]

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

 

[drizzle]

Neither of those are valid, since a row or column contains two 1's.

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

Another example:
The number in the upper left corner needs to be both one and 2.

here's where I misunderstood you

 

[Bohrok]

Elucidus,
I remember once doing a sudoku puzzle that had only one solution (given on the back), but at some point while solving it, I had to make a guess somewhere. I redid the puzzle a few times over several days, writing in each possibility in each box that hadn't been ruled out and came to the same "dead end." I tried doing it with the "wrong" guess and it didn't work out, and that was a really disappointing puzzle to me. Have you come across puzzles like this one?

 

[Elucidus]

Elucidus,
I remember once doing a sudoku puzzle that had only one solution (given on the back), but at some point while solving it, I had to make a guess somewhere. I redid the puzzle a few times over several days, writing in each possibility in each box that hadn't been ruled out and came to the same "dead end." I tried doing it with the "wrong" guess and it didn't work out, and that was a really disappointing puzzle to me. Have you come across puzzles like this one?

I own a Sudoku book, "Sudoku Master Class" by Tom Sheldon, where each puzzle supposedly is solvable without guessing. So far I have done 34 of the 144 puzzles, all without resorting to guessing (it is one of these that took seven hours). But, yes, early on I would occasionally run into a puzzle where no guesses seemed to work. Invariably I would start over and discover that I had made a minor error early on that lead to an impossible (and incorrect) grid.

--Elucidus