Grade Sudoku difficulty level

Question

I am building a Sudoku game for fun, written in Javascript.
Everything works fine, board is generated completely with a single solution each time.

My only problem is, and this is what's keeping me from having my project released to public
is that I don't know how to grade my boards for difficulty levels. I've looked EVERYWHERE,
posted on forums, etc. I don't want to write the algorithms myself, thats not the point of this project,
and beside, they are too complex for me, as i am no mathematician.

The only thing i came close to was is this website that does grading via JS
but the problem is, the code is written in such a lousy undocumented, very ad-hoc manner,
therefor cannot be borrowed...

I'll come to the point -
Can anyone please point me to a place which offers a source code for Sudoku grading/rating?

Thanks

Update 22.6.11:
This is my Sudoku game, and I've implemented my own grading system which relies
on basic human logic solving techniques, so check it out.

Unprofitable

I don't do Sudoku, so I don't really know these terms, but a simple google search has led me to some decent concepts for WHAT to grade. Dunno if that helps? sudokuessentials.com/grading-sudoku-puzzles.html – Stateroom

The site you are refering to has a nice list of strategies. You code could check if the puzzle is solvable with only easy strategies. It could also check how many simultanious cell can be filled in at any time. If a lot of times there is only one cell that can be filled in, you have a more difficult puzzle. – Pile

Good question. I'm sure it's been asked before but, regardless, I'm looking forward to reading the answer. – Tungstate

The solver from Simon Tatham’s implementation tells you which techniques it used and grades the puzzle based on that. – Erik

Answer 1

I have considered this problem myself and the best I can do is to decide how difficult the puzzle is to solve by actually solving it and analyzing the game tree.

Initially: Implement your solver using "human rules", not with algorithms unlikely to be used by human players. (An interesting problem in its own right.) Score each logical rule in your solver according to its difficulty for humans to use. Use values in the hundreds or larger so you have freedom to adjust the scores relative to each other.

Solve the puzzle. At each position:

• Enumerate all new cells which can be logically deduced at the current game position.
• The score of each deduction (completely solving one cell) is the score of the easiest rule that suffices to make that deduction.
• EDIT: If more than one rule must be applied together, or one rule multiple times, to make a single deduction, track it as a single "compound" rule application. To score a compound, maybe use the minimum number of individual rule applications to solve a cell times the sum of the scores of each. (Considerably more mental effort is required for such deductions.) Calculating that minimum number of applications could be a CPU-intensive effort depending on your rules set. Any rule application that completely solves one or more cells should be rolled back before continuing to explore the position.
• Exclude all deductions with a score higher than the minimum among all deductions. (The logic here is that the player will not perceive the harder ones, having perceived an easier one and taken it; and also, this promises to prune a lot of computation out of the decision process.)
• The minimum score at the current position, divided by the number of "easiest" deductions (if many exist, finding one is easier) is the difficulty of that position. So if rule A is the easiest applicable rule with score 20 and can be applied in 4 cells, the position has score 5.
• Choose one of the "easiest" deductions at random as your play and advance to the next game position. I suggest retaining only completely solved cells for the next position, passing no other state. This is wasteful of CPU of course, repeating computations already done, but the goal is to simulate human play.

The puzzle's overall difficulty is the sum of the scores of the positions in your path through the game tree.

EDIT: Alternative position score: Instead of completely excluding deductions using harder rules, calculate overall difficulty of each rule (or compound application) and choose the minimum. (The logic here is that if rule A has score 50 and rule B has score 400, and rule A can be applied in one cell but rule B can be applied in ten, then the position score is 40 because the player is more likely to spot one of the ten harder plays than the single easier one. But this would require you to compute all possibilities.)

EDIT: Alternative suggested by Briguy37: Include all deductions in the position score. Score each position as 1 / (1/d1 + 1/d2 + ...) where d1, d2, etc. are the individual deductions. (This basically computes "resistance to making any deduction" at a position given individual "deduction resistances" d1, d2, etc. But this would require you to compute all possibilities.)

Hopefully this scoring strategy will produce a metric for puzzles that increases as your subjective appraisal of difficulty increases. If it does not, then adjusting the scores of your rules (or your choice of heuristic from the above options) may achieve the desired correlation. Once you have achieved a consistent correlation between score and subjective experience, you should be able to judge what the numeric thresholds of "easy", "hard", etc. should be. And then you're done!

Anceline

I would also include that for a professional product, a nice touch might be to keep time-to-solve statistics for individual puzzles and users. Ultimately, the users' own performances in solving each puzzle will better rate its human difficulty. – Doublefaced

I don't agree with The minimum score at the current position, divided by the number of 'easiest' deductions (if many exist, finding one is easier) is the difficulty of that position. For example, lets say there is one available move with a difficulty of "1" and 5 moves with a difficulty of "2". By your calculations it would ignore the 5 moves and call the difficulty of that position 1/1 = 1. However, if you removed the easier decision, which should make it harder, you'd get a difficulty of 2/5 = .4. – Talebearer

I would suggest instead that the difficulty should be calculated for each square that is left, and then divide the hardest difficulty by the sum of the hardest difficulty / each square's difficulty. For my example above, it would be 2 / (2/1 + 2/2 + 2/2 + 2/2 + 2/2 + 2/2) = 2/7 = .286 < .4 – Talebearer

Different heuristics are of course possible. But unlike a minimax engine, where the heuristic is for the purpose of strategy, here the purpose is to guess how hard the puzzle is to a human. If a human considers the rules in easiest-first order, and looks for cells that can be solved using each rule, then I see no reason to count any but the easiest cells to solve in the heuristic. In your example, the human player will never perceive the 5 harder deductions. Having found the single easy deduction, the player will move on. The other five may be the only ones in the next position. – Anceline

My point is that it is easier to find 1 of the 20 needles in a haystack than it is to find the 1 safety pin, though the safety pin by itself is easier to find than the needle. You play the first move you see, not the first easiest move you see. – Talebearer

@Talebearer Your criticism is well considered but should be alleviated by choosing higher, non-sequential scores for the rules. Suppose the really easy rule is 50 and the next hardest rule is 400. You would need eight next-hardest to get the same low score. This should be OK for a heuristic. Maybe you calculate all and pick the minimum instead of excluding harder rules (i.e. the player might not see a single easy one and find one of many next-easiest deductions). – Anceline

Answer 2

Donald Knuth studied the problem and came up with the Dancing Links algorithm for solving sudoku, and then rating the difficulty of them.

Google around, there are several implementations of the Dancing Links engine.

Orectic

I am already using Dancing Links, but it doesn't implement any grading system. and it's a brute force solution as far as I know, so how can it grade if it doesn't use human-like strategies? – Unprofitable

The implementation I have solves it many times, and counts the average number of independent pathways to the solution. – Orectic

can you please provide a link to the ported version you posses of DLX? – Unprofitable

There are two: one is a port of a Java impl packaged into a WPF app; cid-842434ebe9688900.office.live.com/self.aspx/Games/…. Another is a separate implementation. cheeso.members.winisp.net/srcview.aspx?dir=Sudoku – Orectic

Answer 3

Perhaps you could grade the general "constrainedness" of a puzzle? Consider that a new puzzle (with only hints) might have a certain number of cells which can be determined simply by eliminating the values which it cannot contain. We could say these cells are "constrained" to a smaller number of possible values than the typical cell and the more highly constrained cells that exist the more progress one can make on the puzzle without guessing. (Here we consider the requirement for "guessing" to be what makes a puzzle hard.)

At some point, however, the player must start guessing and, again, the constrainedness of a cell is important because with fewer values to choose between for a given cell the easier it is to find the correct value (and increase the constrainedness of other cells).

Of course, I don't actually play Sudoku (I just enjoy writing games and solvers for it), so I have no idea if this is a valid metric, just thinking out loud =)

Cavernous

I never guess, ever..that makes the fun out of the game. there are strategies available to solve most cases, it's only a matter how good an eye you have for seeing the patterns..but I also never play Hard games because i don't want to end up in a mental hospital :) – Unprofitable

Answer 4

I have a simple solver that looks for only unique possibilities in rows, columns and squares. When it has solved the few cells solvable by this method, it then picks a remaining candidate tries it and sees if the simple solver then leads to either a solution or a cell empty of possibilities. In the first case the puzzle is solved, in the second, one possibility has shown to be infeasible and thus eliminated. In the third case, which leads to neither a final solution nor an infeasibility, no deduction can be reached.

The primary result of cycling through this procedure is to eliminate possiblities until picking a correct cell entry leads to a solution. So far this procedure has solved even the hardest puzzles without fail. It solves without difficulty puzzles with multiple solutions. If the trial candidates are picked a random, it will generate all possilbe solutions.

I then generate a difficulty for the puzzle based on the number of illegal candidates that must be eliminated before the simple solver can find a solution.

I know that this is like guessing, but if simple logic can eliminated a possible candidate, then one is closer to the final solution.

Mike

Sloshy

Answer 5

I've done this in the past.

The key is that you have to figure out which rules to use from a human logic perspective. The example you provide details a number of different human logic patterns as a list on the right-risde.

You actually need to solve the puzzle using these rules instead of computer rules (which can solve it in milliseconds using simple pattern replacement). Every time you change the board, you can start over from the 'easiest' pattern (say, single open boxes in a cell or row), and move down the chain until you find one the next logical 'rule' to use.

When scoring the sodoku, each methodology is assigned some point value, which you would add up for every field you needed to fill out. While 'single empty cell' might get a 0, 'XY Chain' might get 100. You tabulate all of the methods needed (and frequency) and you wind up with a final weighting. There are plenty of places that list expected values for those weightings, but they are all fairly empirical. You're trying to model human logic, so feel free to come up with your own weightings or enhance the system (if you really only use XY chains, the puzzle is probably easier than if it requires more advanced mechanisms).

You may also find that even though you have a unique sodoku, that it is unsolvable through human logic.

And also note that this is all far more CPU intensive than solving it in a standard, patterned way. Some years ago when I wrote my code, it was taking multiple (I forget exactly, but maybe even up to 15) seconds to solve some of the generated puzzles I'd created.

Baron

Donald Knuth's DancingLinks engine can solve solvable sudoku fairly quickly, 1s or less on modern processors. This includes even "very hard" sudoku that might be ranked unsolvable by human experts. – Orectic

Will it score it? That's the point here... It is trivial to solve if the computer gets to guess. : ) – Baron

DLX (dancing links) don't score and cannot score, because it uses brute force. that's why its so fast, and i'm using it to determine if my generated board has only a single solution. – Unprofitable

and as I wrote, most these human-like strategies are very time consuming to code, and I really don't want to do it. it blows my mind there are no available algorithms on the web for each method.. this game is very popular. – Unprofitable

@Unprofitable - Yeah, I took at a look at Stuart's code. It is fairly ridiculously bad... or at least ill-planned. If there's a problem it is that people just want to solve it, and generally don't care how they solve it. It looks like Stuart is the de-facto guy for this (wrote the paper referenced in Rob P's answer below mine). I'd guess that you're looking to automatically generate and score sodoku's for user consumption, which is what I was looking to do. It was at least 8 years and a different house ago that I wrote my javascript algorithms. If I can dig them up, I'll hand them to you. – Baron

check out my end result, I've updated my question with the link – Unprofitable

Answer 6

Assuming difficulty is directly proportional to the time it takes a user to solve the puzzle, here is an Artificially Intelligent solution that approaches the results of the ideal algorithm over time.

1. Randomly generate a fixed number of starting puzzle layouts, say 100.
2. Initially, offer a random difficulty section that let's a user play random puzzles from the available layouts.
3. Keep an average random solution time for each user. I would probably make a top 10/top X leaderboard for this to generate interest in playing random puzzles.
4. Keep an average solution time multiplier for each puzzle solution (if the user normally solves the puzzle in 5 minutes and solves it in 20 minutes, 4 should be figured in to the puzzles average solution time multiplier)
5. Once a puzzle has been played enough times to get a base difficulty for the puzzle, say 5 times, add that puzzle to your list of rated puzzles and add another randomly generated puzzle to your available puzzle layouts.
   Note: You should keep the first puzzle in your random puzzles list so that you can get better and better statistics on it.
6. Once you have enough base-rated puzzles, say 50, allow users to access the "Rated Difficulty" portion of your application. The difficulty for each puzzle will be the average time multiplier for that puzzle.
   Note: When users choose to play puzzles with rated difficulty, this should NOT affect the average random solution time or average solution time multiplier, unless you want to get into calculating weighted averages (otherwise if a user plays a lot of harder puzzles, their average time and time multipliers will be skewed).

Using the method above, a solution would be rated from 0 (already solved/no time to solve) to 1 (users will probably solve this puzzle in their average time) to 2 (users will probably take twice as long to solve this puzzle than their average time) to infinity (users will take forever to find a solution to this puzzle).

Talebearer

actually, a Sudoku difficulty is measured not by time, but by simple-to-advanced techniques needed to be used in order to solve the puzzle. if more advanced needed, the puzzle is graded harder. – Unprofitable

@Unprofitable That is one way of defining Sudoku difficulty. However, I would argue that advanced techniques take longer for a human to find and apply than simple ones, thus time to solve is proportional to your definition of Sudoku difficulty, and thus my solution is still a good measure of difficulty in your terms. However, if you are looking for difficulty exactly as "This problem has level 3 difficulty moves in it" this solution is not for you. – Talebearer

from my experience, what patterns my eyes spots in 5-10 seconds, will require a tremendous amount of code development.. the advanced techniques sometimes are quite easy once you get the point, so your brain actually gets quicker solving using them with time. – Unprofitable

@Unprofitable I agree, but you also get quicker at recognizing the simple patterns too. My guess is that even Sudoku pros will take a longer to find advanced patterns than simple ones. However, I will concede the point that this approach will stop being useful for users whose brains find solutions faster than their hands can enter them with a mouse, thus blurring the lines between easy, medium, and even hard. – Talebearer