SHD Ratings |
© Copyright Greg Shalless 2006 The Sudoku-Help Difficulty (SHD) Rating is an attempt to assign a meaningful numeric value to each Sudoku Puzzle that reflects the difficulty in solving that particular puzzle relative to other puzzles. As a puzzle is solved using the Sudoku-Help+Solver, SHD Points are accumulated according to the Solving Rules deployed and how many iterations of those Rules were required as shown in the table below. A puzzle's SHD Rating is the total of those points (if Looping is always turned on) once the puzzle is solved for either the most efficient (ie lowest SHD Rating achievable) or the most obvious set of Rule selections leading to the solution (sometimes the most obvious path is not the most efficient). The Sudoku-Help+Solver only implements those Rules one could reasonably expect a human using some form of candidate mark-up (with a newspaper puzzle and a non-erasable ballpoint pen) to spot. Consequently a method is also required to assign a value to puzzles which the Sudoku-Help+Solver cannot solve (Master Class puzzles) and this is also shown below. I invite others to use this algorithm to rate their own puzzles (even if it is using their Solvers) provided they refer to it as the puzzle's SHD Rating and give me credit for the algorithm or link to my Website or at least this page of it. If enough Puzzle creators adopt the SHD Rating algorithm we will be able to compare the difficulty of everybody's puzzles with a standard figure to which human solvers can relate. Testing by human solvers has shown a reasonable correlation between a puzzle's SHD Rating and the time it takes them to solve it. Sudoku-Help+ itself has 84 puzzles rated as follows: 26 Novice (SHD: 57 - 82), 30 Player (SHD: 76 - 131), 27 Expert (SHD: 93 - 238) & 1 Master (SHD: 163) This means the SHD Rating can usually be displayed within the puzzle itself, which is a nice feature. See examples below. The Ratings above are based on the original (pre Version 3.0 of Sudoku-Help-Plus) SHD Ratings algorithm but the descriptions below describe the new algorithm (introduced in Version 3.0), where they are now rated as follows: 26 Novice (SHD: 57 - 82), 30 Player (SHD: 71 - 128), 27 Expert (SHD: 79 - 220) & 1 Master (SHD: 149) The new algorithm is very simple. 1 SHD Point for every solved cell and every iteration of a Novice Class Solving Rule, and for all the elimination strategies it's simply 1 SHD Point for every cell in the Rule Defining pattern, plus 1 for each Player Class elimination, plus 2 for each Expert Class elimination and 3 for each Master Class elimination. Then if the puzzle remains unsolved plus 1 for each unsolved cell, and 1 for each still valid candidate. Then there's my totally arbitrary factors as described below, which basically mean plus 2, for no logical reason other those dictated by Puzzle No. 7, which by the way I made Puzzle No. 69 when it was published in mX Newspaper. But what does it all mean? How long should it take to solve a puzzle with a particular SHD Rating? Well the fact is I have no idea how long it will take you, but I do have a very good idea how long it takes me, which is about one minute for each SHD Ratings point over 50. So subtract 50 from the SHD Rating and that's about how many minutes it takes me. If you do it in less time than that, there's a good chance you're better at solving Sudoku than me. |
||
Suduku-Help+ Solving Rules | SHD Points per solved cell | SHD Points per Rule Iteration | Reason (what makes it Harder) |
Novice Class | 1 | 1 | More to solve + Longer to do it = Harder |
Only Spot Boxes | |||
Only Spot Rows | |||
Only Spot Cols | |||
Only Value | |||
Suduku-Help+ Solving Rules | SHD Points per elimination performed | SHD Points = # cells in rule defining pattern | Reason (what makes it Harder) |
Player Class | 1 | More to find = Harder | |
Locked Pairs | 2 | 2 Values in 2 Cells (in the same Constraint Region) | |
Locked Triples | 3 | 3 Values in 3 Cells (in the same Constraint Region) | |
Locked Quads | 4 | 4 Values in 4 Cells (in the same Constraint Region) | |
Intersect Reject | (2 or 3) | 1 Value in up to 3 Cells (in 2 intersecting Constraint Regions) | |
Expert Class | 2 | More to find = Harder (Expert Rules harder than Player) | |
2x2 Gridlock (X-Wings) |
4 | 1 Value in 4 Cells | |
3x3 Gridlock (Swordfish) |
9 | 1 Value in 9 Cells | |
4x4 Gridlock (Jellyfish) |
16 | 1 Value in 16 Cells | |
XY-Zap (XY-Wings) |
3 | = 2-link Multi-Value-Chain | |
Pair Chains (Remote Pairs) |
chain-length + 1 | The longer the chain the harder it is to find | |
Single Value Chains | chain-length + 1 | The longer the chain the harder it is to find | |
Multi Value Chains (XY Chains) |
chain-length + 1 | The longer the chain the harder it is to find | |
Hidden Pairs | 2 | 2 Values not in n-2 Cells (n = No unsolved in Constraint Region) | |
Hidden Triples | 3 | 3 Values not in n-3 Cells (n = No unsolved in Constraint Region) | |
Hidden Quads | 4 | 4 Values not in n-4 Cells (n = No unsolved in Constraint Region) | |
Master Class | 3 | More to find = Harder (Master Rules harder than Expert) | |
XYZ-Wings | 3 | 3 Values in 3 Cells (not really any harder than XY-Zap) | |
Hinge (Empty Rectangle) | 7 | 2 for the Single-Value-Pair + 5 for the 5 cells comprising the Hinge | |
nxn Blocked Gridlock (Finned Fish) | nxn + (1 or 2) | Same as for nxn Gridlock + 1 for each blocking cell | |
Blocked Single Value Chains | chain-length + 1 + (1 or 2) | Same as for Single-Value-Chains + 1 for each blocking cell | |
Unsolved Cell | 1 | More to solve = Harder | |
Each still valid Candidate | 1 | More options to choose from = Harder | |
Arbitrary Factors | Because its my algorithm! | ||
Puzzle No 7 | +1 | Because of its arrangement of the givens it was imperative that Sudoku-Help+ Puzzle No 7 had an SHD Rating of 69. | |
Final unnecessary Iteration of the Solver | The Sudoku-Help+Solver loops on each Rule until it has an iteration with no changes, including once unnecessarily when a puzzle is solved. Whilst the puzzle remains unsolved a null iteration is akin to the human solver approach of continuing with a successful strategy until it yields no results, but the human solver is never going to do this when the puzzle is already solved. However the effect of this on Puzzle No 7 is that it is solved with 6 iterations of Only-Spot-Boxes and 9 iterations of Only-Value, which I couldn't bring myself to throw away. | ||
Processing Order | The order in which the Sudoku-Help+Solver processes values, rows, columns and boxes is as you might expect from 1 to 9. A different order might result in more or less iterations being required to get to the same end point. This means values can be exchanged using the Convert Puzzle feature or the puzzle transformed (eg. by turning it upside down), to achieve a slightly different SHD Rating, a feature which I have frequently exploited to ensure I could visibly display the SHD Rating within the puzzle itself. |
Sudoku-Help+ Example Puzzles | |
These sample puzzles from Sudoku-Help-Plus show the SHD Rating visible in the puzzle itself (encircled). It should also be clear why Puzzle No 7 (which should really be Puzzle No 69, I guess) was allowed to exert such influence over the SHD Rating algorithm. The astute amongst you will notice a striking resemblance between Puzzle No 60 and the Example puzzle on the Sudoku-Help Main Page. That's because it is the same puzzle with its values rearranged to show the SHD Rating of 109. You might also observe that I have realised through the course of developing Sudoku-Help-Plus that this particular puzzle is solvable by pure logic and, contrary to my initial thoughts, does not require trial and error. |