Here's an example for an ATK "Easy" puzzle:
- Code: Select all
PID: ATK_E9831 (9 x 9)
MRL = 8
ACRL = 8
NCELL = 52 (81%)
fixed = 20 (USI)
implied = 32 (domain test)
total = 52 (100%)
Rating = 1.0000 (avg cell NPV)
- MRL is the maximum run length
- ACRL is the average cell run length (for each cell the lengths of the horizontal and vertical run are added together)
- NCELL is the number of white cells (with % of total cells). A 9x9 puzzle (on my scale) has 64 interior cells, so 52 is approx 81% of that)
- fixed: this number indicates the number of cells whose values are fixed by way of having a unique sum intersection (USI). Thus a 4-cell run with sum 30 (S30, L4) intersecting with an (S9, L3) fixes a value of 6 at the intersection.
This number also includes cells for which fixed values in other cells leave just one free cell in any run, which means that cell can also be fixed.
- implied: when all the fixed values have all been identified, we are left with multiple choices for the remaining cells. Some of these choices which might have been valid at the beginning can be eliminated by a simple process. Suppose D is an option for a given cell - is it still possible to form the corresponding H and V sums with a D in this position? The answer is "no" surprisingly often, it's just that computers are generally better at it. Any cells which become fixed after this domain shaving is repeated as often as possible are implied values.
- Rating: this score is a simple average taken on the number of possible values (NPV) for each cell at the end of domain shaving. If we have fixed + implied = NCELLS (100%) then this value will be 1.
Here is a comparison of some samples of the 3 puzzle grades used at ATK (Easy, Medium, and Hard):
- Code: Select all
(ATK samples)
E1 E2 M1 M2 H1 H2 H3
Size = 9 11 13 10 14 13 13
NCELL = 52 82 104 63 139 116 118
fixed = 20 33 25 5 23 2 8
implied = 32 49 79 58 78 105 76
Rating = 1.0 1.0 1.0 1.0 1.7 1.15 1.45
ATK's "Easy" puzzles tend to have smaller grids together with a high number of fixed cells, which are then easily finished off by the domain shaving process. "Medium" puzzles have larger grids and/or less fixed values. The domain shaving is typically a bit more involved, but normally is sufficient to complete the puzzle without T&E. "Hard"puzzles have larger grids, less fixed values, and the simple domain shaving does not lead to completion, so the rating is typically > 1.
This rating method doesn't attempt to take into account available strategies such as hidden/naked pairs, implied sums etc., all of which can be used to further reduce cell domains. It does give a reasonable guide to the relative computational complexity of the puzzle.
The rating value of 1 does not alone make a puzzle easy (or even medium). The size of the grid has a major impact on the difficulty of doing the elementary domain-shaving. Consider this example from Conceptis:
- Code: Select all
PID: CB049 (24 x 14)
MRL = 9
ACRL = 11
NCELL = 251 (84%)
fixed = 38 (USI)
implied = 213 (domain test)
total = 251 (100%)
Rating = 1.0000 (avg cell NPV)
Despite the 1 rating, there are some key indicators that this is not an easy puzzle for the human solver. With just 38 fixed cells, that leaves 213 cells whose implied values have yet to be deduced, and which are less likely to be obvious to you, even if your computer has no problems with it.
In fact this puzzle is taken from the Conceptis "Absolutely Nasty Kakuro - Level 4" book, and all of these puzzles are generally acknowledged as in the "Very Hard" category (to which I can also attest). So large grids + small % of fixed cells usually indicates a challenge.
The usefulness of such a rating/profiling system is of course less for puzzle-solvers than it is for puzzle-generators. Kakuro puzzle generation is a tricky business, and this rating system is a reasonable predictor of just where on the difficulty scale any generated puzzle is likely to fall.
Still, if anyone would like a profile done on any puzzle, just point me to it and I'll oblige.
