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

  • Thread starter jobyts
  • Start date
  • #1
210
53
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?
 

Answers and Replies

  • #2
286
0


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
 
  • #3
210
53


To elaborate on the second question,

Is there a sudoku puzzle that no solution exists?
 
  • #4
359
0


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.
 
  • #5
Borek
Mentor
28,825
3,343


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".
 
  • #6
uart
Science Advisor
2,797
21


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.
 
  • #7
359
0


true
 
  • #8
210
53


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?
 
Last edited:
  • #9
uart
Science Advisor
2,797
21


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)
Code:
 1 2   | 3     |
       |       |
 4 5 6 |       |
       |       |
 7 8 9 |       |
---------------
 
  • #10
367
1


Another example:

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


The number in the upper left corner needs to be both one and 2.
 
  • #11
210
53


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?
 
  • #12
DavidSnider
Gold Member
502
143


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.
 
  • #13
Borek
Mentor
28,825
3,343


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.
 
  • #14
drizzle
Gold Member
379
57


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 | . . . | . . .
 
  • #15
210
53


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?
 
Last edited:
  • #16
367
1


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.
 
  • #17
Borek
Mentor
28,825
3,343


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: [Broken]

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

Sounds reasonable.
 
Last edited by a moderator:
  • #18
216
1


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:
 
  • #19
286
0


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
 
  • #20
drizzle
Gold Member
379
57


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 :tongue:
 
  • #21
867
0


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?
 
  • #22
286
0


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
 

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

Replies
35
Views
33K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
8
Views
1K
  • Last Post
Replies
9
Views
3K
Replies
2
Views
2K
Replies
1
Views
2K
  • Last Post
Replies
10
Views
1K
  • Last Post
Replies
6
Views
4K
  • Last Post
Replies
13
Views
2K
Top