Kakuro rating system

For fans of Kakuro

Kakuro rating system

Postby Mathimagics » Fri Aug 19, 2016 12:18 am

I've come up with a reasonably reliable rating system for Kakuro puzzles. It gives a profile of a puzzle with some vital statistics.

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.
Last edited by Mathimagics on Sun Sep 04, 2016 7:52 pm, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Small doesn't necessarily mean easy

Postby Mathimagics » Fri Aug 19, 2016 12:38 am

A rating of 1 doesn't necessarily mean easy, as demonstrated above. But typically ratings will be < 2 for even the hardest puzzles one is likely to see in published form. My rating value tends to be like the Richter scale, ie. a 2 is likely to be 4 times as hard as a 1 on the same grid layout.

With this in mind, I present what is possibly the most diabolical Kakuro puzzle yet devised.

Kakuro_Rating_Example.jpg
Kakuro_Rating_Example.jpg (49.17 KiB) Viewed 190 times


Here are the profiles for these 2 puzzles:
Code: Select all
PID: KT0707_MF_Easy (7 x 7)
     MRL =      6
    ACRL =     10
   NCELL =     34 (94%)
   fixed =     14 (USI)
 implied =     20 (domain test)
   total =     34 (100%)
  Rating = 1.0000 (avg cell NPV)

PID: KT0707_MF_Hard (7 x 7)
     MRL =      6
    ACRL =     10
   NCELL =     34 (95%)
   fixed =      0 (USI)
 implied =      0 (domain test)
   total =      0 (0%)
  Rating = 6.2059 (avg NPV)


As you can see, the one on the left is a doddle, while the one on the right is, for all practical purposes, impossible. And yet it is a genuine puzzle with a unique solution. It did take several hours (days in fact) of CPU time to find.

A rating of 6.2, it just staggers the imagination!

And that's just a small grid - I can well imagine even more horrendous cases on larger grids. The point here is that there is no such thing as the "World's Hardest Kakuro Puzzle"!

By the way, this grid layout is, I believe, the absolute maximum density (NCELL) for its size. It has the bare minimum of black cells (well, I show them as grey, I do believe in saving toner!) that allow uniqueness of puzzle solutions.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015


Return to Kakuro