Sign in to follow this  
prinzessin

Sudoku : determining difficulty level

Recommended Posts

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

Share this post


Link to post
Share on other sites
SamLowry    1865
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


Link to post
Share on other sites
ibebrett    205
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


Link to post
Share on other sites
prinzessin    122
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


Link to post
Share on other sites
SamLowry    1865
Quote:
Original post by prinzessin
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 ?!

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


Link to post
Share on other sites
ddn3    1610
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


Link to post
Share on other sites
prinzessin    122
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


Link to post
Share on other sites
Cosmic314    2002
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


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this