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.

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

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.

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.

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

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

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

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.

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.