Jump to content
• Advertisement

# Sudoku : determining difficulty level

This topic is 3711 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

## Recommended Posts

Hi All, I've recently implemented a Sudoku generator and solver. The puzzles are generated randomly, but now I would like to categorize them into easy, medium, and difficult. Is there any way to do that... I mean other than just counting the number of initial clues? Thanks.

Advertisement

#### Share this post

##### Share on other sites
Yeah thanks, I had already seen that... but I was thinking more of a mathematical formula to help me out.

#### Share this post

##### Share on other sites
I'd say difficulty is rather subjective. I've solved easy "easy puzzles" and hard "easy puzzles" and I'd think that there are many possible difficulty metrics.

I once wondered about the same problem and the only way to do it that makes sense to me is actually to use something that's very similar to the way I solve sudokus. There are different little "tricks" I use: first I consider square after square, writing down little bars indicating which digits are allowed where. Some cells will only have one bar, meaning I can immediately fill in those cells. Let's say that's a level 1 trick (i.e. it is easy and quick).
A harder trick would be looking for some sort of partitions in the same row/column/square, which is more difficult to do. That could be a level 3 trick.
Then, I would implement a solver :). First, it would try to solve the sudoku with exclusively level 1 tricks. If it succeeds, it means the puzzle was easy. If there are still cells unfilled, it will try with level 2 tricks, etc. The highest level of trick that was necessary to solve the puzzle is then its difficulty rating.

Yes, it's again very elaborate :) But I doubt there exists a simple mathematical formula for determining difficulty.

#### Share this post

##### Share on other sites
for the mma math modeling competition last year this was the exact question. your given a weekend to do figure it out. if you google mma math modeling competition you may be able to find the winning papers.

#### Share this post

##### Share on other sites
Thanks SamLowry, but here's the thing : I have generetaed n thousand text files of puzzles and solutions of unknown difficulty. Is there no way to add a difficulty level withuot having to re genarate and try to solve them again ?!

ibebrett, the mma modelling thing is tooooo complicated for what i need :)

#### Share this post

##### Share on other sites
Quote:
 Original post by prinzessinThanks SamLowry, but here's the thing : I have generetaed n thousand text files of puzzles and solutions of unknown difficulty. Is there no way to add a difficulty level withuot having to re genarate and try to solve them again ?!

You won't have to regenerate them, just solve them :)

Well, theoretically it's possible to find a mathematical formula that will nicely compute a puzzle's difficulty, but finding this formula is certainly going to be quite difficult.

Maybe someone else on this forum will have some great idea, I'm fresh out of ideas (well, pragmatic ideas).

#### Share this post

##### Share on other sites
Why not run those puzzles through a solver and see how many steps it takes to solve it, the longer then the harder it is. I'm sure there are solvers for Sudoku and using a solver as a metric is as good as any. It's more consistent and provides a baseline measure from which you can extrapalate human difficultly levels.

Good Luck!

-ddn

#### Share this post

##### Share on other sites
Thanks all for your replies.

I decided to simplify the approach and here is what Ive done:

I have divided the grid into 9 separate parts, what I call quarters. Each quarter is a 3 by 3 grid
--- --- ---

Q1 Q2 Q3

--- --- ---

Q4 Q5 Q6

--- --- ---

Q7 Q8 Q9

--- --- ---

Here is the difficulty level algorithm I've implemented:

- very difficult: at least 4 quarters have at most 2 values AND q5 has less than 3 values
- difficult: at least 2 quarters have at most 2 values
- medium: at least 4 quarters have exactly 3 values
- easy: at least 2 quarters have at least 8 values
- very easy: at least 4 quarters have at least six values AND q5 has at least 4 values.

#### Share this post

##### Share on other sites
I haven't read those papers but I did write a solver.

I'd base the difficulty on the types of rules necessary to solve a puzzle. For example, in my solver I have a simple loop that goes across rows / columns / sub-grids using the simple rule of elimination. If it can't solve the puzzle with that strategy it tries the next check on the difficulty scale -- checking rows / columns / sub-grids simultaneously. If it can't make progress with that rule then it moves to inference rules. For example, if a column has two cells left with (2 9) (2 9 4) you can eliminate 4 from the grouping.

Thus the difficulty would be set when a particular loop / rule is used.

#### Share this post

##### Share on other sites

• Advertisement
• Advertisement

• ### Popular Contributors

1. 1
Rutin
29
2. 2
3. 3
4. 4
5. 5
• Advertisement

• 13
• 13
• 11
• 10
• 13
• ### Forum Statistics

• Total Topics
632955
• Total Posts
3009450
• ### Who's Online (See full list)

There are no registered users currently online

×

## Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!