## Introduction

Kakuro is an absorbing logic game. Please refer to Figure 1. The player is presented with a rectangular grid of 3 types of squares: sum squares, solve squares and spacers. The solve squares are arranged into intersecting horizontal and vertical strips with sum squares at their ends. Sum squares contain numbers relating to their adjacent strips of solve squares. The object of the game is to place the digits 1-9 in the solve squares so that the sum of these digits is equal to the number in the sum square at the end of the strip. Each digit can only occur once in each strip.

## Kakuro Example

Figure 1. is a screenshot from kakuro. The strips of squares to be solved are shown in white with their possible answers written in tiny numbers around their edges. The sum squares at the ends of the strips contain the numbers that the strip's answers must make when added together. Here the player has clicked on the 21 at the left end of the horizontal strip of 3, and the program has popped up a list of the 3 combinations of three digits which sum to 21.

## Summary

The program starts by displaying a randomly selected puzzle. The sum for each strip is shown at its end and the 9 possible candidate answers are written in the unsolved squares. These candidate numbers are buttons: left-clicking will delete a candidate, middle-clicking on its position will rewrite it, right-clicking will set it as the answer. These actions are sufficient to finish a puzzle. But, if stuck, players can request various forms of help from the program. Left-clicking on a strip sum will pop-up a list of the possible combinations for that strip (See Figure 1). These lists are kept up-to-date as answers are set. Shading can be used to show which squares have the fewest number of possible answers. Hints can be requested by clicking on the wand icon in the Toolbar.

Hints include: Simple Filter, Possible Combinations(PC), Candidate Bounds(CB), Hidden Single(H1), Naked Pairs(N2), Naked Triples(N3), Naked Quads(N4), Hidden Pairs(H2), Hidden Triples(H3), Impossible Combinations(IC), Unmatched Candidates(UC), Isolated Necks(IN), Possible Permutations(PP).

All of the program's 5000 built-in puzzles can be solved by the algorithms listed above: none require guessing. When an external puzzle is read in the program will try to solve it using its standard algorithms, but may need to guess in order to find the correct solution. In this case, if the player requests a hint and none can be found, the program (knowing the answers) will simply set the answer for a random square and the 2-letter hint code ** will be displayed. A left click on the hint button will request a single hint. Hints are shown by highlighting the candidates that can be deleted in red and where appropriate the reasons in green. While the hint is active (shown by the wand icon leaning backwards) clicking on the wand with the middle mouse button will cause a pop-up to appear containing a short explanation of the hint. A further left click will delete the red candidates and unhighlight the green candidates. Right-clicking on the hint button will apply Simple Filter exhaustively and so can save a lot of tedious deletion.

At the top of the display is a Toolbar. The jigsaw piece button at the left is a menu which has options for entering puzzles, reading them from files or saving them to disk. The menu includes options for configuring the display and saving the current settings. Next to the jigsaw icon is a grid-like icon which is used for selecting a random puzzle from the programs built in puzzles; a wand for selecting and executing hints; a thumb for checking and correcting errors, and a sad smiley for showing the solution. To the right of this are 3 numbers. The first is the puzzle number, the next the puzzle difficulty and the next a clock which ticks every 5 seconds. The puzzle number display is also an input box: players can position the cursor over this area and type in a number between 0 and 4999 followed by "Enter" to load the corresponding puzzle. When a hint is requested the clock display is used to show a 2-letter abbreviation for the name of the hint found. The program will not report errors until the player clicks on the thumb or requests a hint. Errors are reported by the thumb turning down and the incorrect squares being highlighted. A further click on the thumb will correct the error(s) and undo all subsequent changes. At any time, hitting "Enter" will restart the current internal puzzle.

## Kakuro Worked Example

A video from kakuro. To get started the player is looking for rows or columns which have few choices of candidates. Experienced players will know these by heart, but for the beginner each sum has a pop-up showing the possibilities. She finds that the sum 11 only has one combination of digits and so she deletes the others using right clicks. Then she checks for mistakes by clicking on the thumb. Deleting all those candidates is rather tedious so she resorts to using the hint button which will apply the equivalent algorithm first. She gets a bit carried away with using the hint button but eventually starts to think for herself and sets some answers in the bottom left hand corner. Finally she hits the show solution button to finish the game.

## Shading

The puzzle menu has an option which requests that the program analyse the intersecting combinations for each square and shade the background according to the number of possible solutions there are. Please see the adjacent Figure.

## Shading

Optional shading can be used to show which squares have the fewest possible solutions: the lighter the shade the fewer the possible solutions. Here the white square below the popped up list of combinations must be 3: the sum across is 4 which can only be made with 1 and 3, and none of the down combinations contains a 1, but one has a 3.

## Colours

Using an option in the puzzle menu players can set the colours of the boxes, the text, and the various highlights. The gaudy adjacent screenshot serves as a warning.

## Playing

Each of the squares which have yet to be given a value contain tiny "candidate" numbers 1-9. These are buttons which can be left clicked for removal or middle clicked for setting the number for the square. A right click will replace a deleted candidate. In this way they can be used as a simple notepad while working towards the solution for each square. If the player cannot make progress, hints are available.

## Using Hints

Hints are requested using the wand icon in the Toolbar. Two modes can be set via the "Hint Mode" option in the puzzle menu: either the program will find the "Simplest" hint or it will find the one which removes the most candidates ("Most Effective"). The simplest hint is the one with the lowest difficulty score. In both cases, if the Exclusion algorithm can operate, it will be given priority (this is because the coding of the other algorithms requires that all Exclusion operations are performed first).

When a hint is requested the program highlights, in red, the candidates which can be deleted and, when possible, in green, the reason. For example, in the adjacent Naked Pairs screenshot the 1 and 2 candidates highlighted in red can be deleted because 1 and 2 must be the answers for the squares where they are highlighted in green. Note that for several algorithms it is not possible to show the "reason" for a hint; only the hint two-letter code and the candidates that can be deleted.

When a hint is requested the wand icon flips to its mirror image. If the player clicks on it while it is in that configuration the program will automatically remove all the candidates highlighted in red, unhighlight those in green, and the wand will revert to its normal orientation. Otherwise the player can delete the red candidates using mouse clicks.

## Naked Pairs

In row 6 there are two squares which contain only 2 different candidates (1,2, shaded green). As they are the only remaining candidates in these squares, they must be their answers. Therefore the other 1,2s in the row (shaded red) can be deleted.

Of course, use of the hint option is not obligatory and purists can work out everything for themselves and simply use the candidate buttons as a notepad for each square.

## Checking for Errors

Clicking on the hand button causes the program to check the puzzle for errors (which can occur due to the player removing incorrect candidates). If errors are detected the hand will flip to the thumbs down position. A further click on the hand will reverse all moves made by the player, back to the last time the puzzle was error free. Note that when a hint is requested the program always checks the puzzle for errors first. If errors are detected no hint search will be performed, the hand will flip to thumbs down and the squares with errors will be highlighted.

## Difficulty Score

The Difficulty Score is the middle of the three numbers at the top of the games window. Because puzzles can be solved in many different ways, and players may find harder or easier ways than those the program used when it calculated the score, the Difficulty Score can only provide a rough indication of the difficulty. Nevertheless it does give a useful indication of the relative difficulty of puzzles.

Algorithm | Score(D) |
---|---|

Candidate Bounds | 1 |

Possible Combinations | 1 |

Hidden Singles | 2 |

Naked Pairs | 4 |

Naked Triples | 5 |

Hidden Pairs | 7 |

Hidden Triples | 8 |

Naked Quads | 8 |

Impossible Combinations | 9 |

Unmatched Candidates | 9 |

Isolated Necks | 9 |

Possible Permutations | 9 |

The score for a puzzle is calculated as follows. Let D_{i} be the
difficulty score for algorithm i, and N_{i} be the number of squares
algorithm i was successfully applied to in solving the puzzle.
The difficulty score for the puzzle is then the sum
of N_{i} x D_{i} for all i. During this analysis the program always uses the algorithm with the lowest difficulty score which is effective when applied to the current state of the grid.
The algorithms are explained by examples below.

## Saving Puzzles

Partially completed puzzles can be saved. They can be loaded and worked on at a later time. By default they will be kept in the game's SAVES directory.

## Loading Puzzles

Puzzles can be read from files or entered using an interactive Puzzle Editor.

The "Read puzzle" option in the puzzle menu can be used to read grids stored in files. The files must be in one of the formats shown here or have previously been saved by the program.

When a new puzzle is entered the program will attempt to solve it. In rare cases, particularly when the puzzle has multiple solutions (and hence is not a true puzzle) this can take an appreciable time. To deal with this, the program uses a time limit and the solver will give up after trying for this amount of time. The limit can be set using the "Max solve time" in the menu. Also, as loaded, the puzzle may contain errors.

If the puzzle data is found to contain errors or the solver runs out of time the program will automatically load up a Puzzle Entry window to allow the user to make corrections. In the first case the Entry Window will contain the message "Unable to solve puzzle" and in the latter "Unable to solve the puzzle in time".

Note that you can make sure that the entered puzzle has only one solution by using the Check puzzle option in the puzzle menu.

## Entering Puzzles

The "Enter New Puzzle" option in the puzzle menu can be used to enter puzzles interactively. The puzzles must be in one of the formats shown here.

If the puzzle data is found to contain errors the program will automatically reload up a Puzzle Entry window to allow the user to make corrections.

Note that you can make sure that the entered puzzle has only one solution by using the Check puzzle option in the puzzle menu.

## Bad Puzzles

If a player enters an incorrectly specified puzzle from a file or the Enter Puzzle option, the program will attempt to draw the grid specified so that the player can locate the mistake. A puzzle Entry window is also displayed to allow the correction to be made. This is shown by an example in the Figures entitled "Bad Entry Window 1", "Bad Entry Window 2", "Bad Entry Window 3".

## Bad Entry Window 2

A puzzle with an error. The player has typed an extra * after the 33 on line 4 and it shows in the grid as an isolated white square at the right of the grid. This is clearly an error.

## Bad Entry Window 3

The player has deleted one of the *'s following the 33 on line 4 and the program has solved the puzzle, deleted the two error windows and draw the puzzle in the normal way ready for the player to play.

## Checking Puzzles

If the player reads a puzzle from a file or enters a puzzle by hand it is possible that the puzzle has more than one solution (all the built-in puzzles have only a single solution). Most would consider puzzles with more than one solution incorrect and obviously the program's ability to monitor mistakes cannot function when this is the case. To cater for the possibility that such a puzzle has been entered the program has an option "Check puzzle" in the File menu which tests the current puzzle to see if it has more than one solution. On some machines this test can take several seconds to complete. While this is happening the puzzle cannot be altered. When it is finished a window will appear reporting the outcome. This window must be closed via its "OK" button before the program can continue.

The check puzzle function uses the same time limit as the solver and will stop trying after the limit is reached.

## Tool Tips

Players can click on the Toolbar with the middle mouse button to get a reminder of the function of each button.

## Terminology

A **strip** is a set of adjacent squares - across or down - preceeded by a sum square and terminated by a spacer square or a sum square. A **sum square** is one containing the required sum for the squares to its right or the squares below. A **solve square**, or square to be solved, is one requiring a solution. A **spacer square** functions only as padding to give the required shape to the overall grid. The **square count** is the number of squares in a strip. A solving **combination** is a subset of the digits 1-9 in any order which sum to the required total for a strip. Typically there will be several such combinations for each strip - i.e. for each sum and square count. A **permutation** is a particular ordering of the digits in a combination. For example, the sum 12 and square count 4 is satisfied by two combinations: [1,2,3,6] and [1,2,4,5]. If the first of these combinations is the solving combination, there are 4! = 24 possible permutations: [1,2,3,6], [1,3,2,6],..., [6,3,2,1].

## Algorithms

The algorithms used by Kakuro are explained using examples. In the explanations, rows and columns are numbered from the bottom left hand corner of the grid, starting at 1,1. Candidates highlighted in green are the "reasons" that the candidates highlighted in red can be removed.

## Exclusion Rule

Exclusion Rule: each digit can only appear once in each strip of cells. The answer to column 6, row 8 is set to 3. Only one 3 can occur in each column, so all others 3s in column 6 can be deleted.

## Hidden Pairs

Hidden Pairs: if a pair of digits are required for all combinations which satisfy a strip and those two digits only occur in two cells, they must provide the answers for those cells and all other digits in those cells can be deleted. In a strip in row 5 only two squares still have candidates 1,3. If 1 and 3 are required for all the combinations for this row they must be the answer for these squares and all other candidates in them can be deleted.

## Hidden Single

Hidden Single: if a digit is required for all combinations which satisfy a strip and that digit only occurs in one cell, it must provide the answer for that cell and all other digits in that cell can be deleted. The square at column 4, row 3 contains the only remaining candidate 1 in row 3 and column 4. If 1 is required for all the combinations for either this row or this column it must be the answer for this square and all other candidates in the square can be deleted.

## Hidden Triples

Hidden Triples: if three digits are required for all combinations which satisfy a strip and those three digits only occur in three cells, they must provide the answers for those cells and all other digits in those cells can be deleted. In column 8 only three squares still have candidates 6,8,9. If 6,8,9 are required for all the combinations for this row, as they are the only remaining candidates in these squares, they must be their answers. Therefore the other 6,8,9s in the row (shaded red) can be deleted.

## Naked Pairs

Naked Pairs: if a pair of digits are required for all combinations which satisfy a strip and those two digits are the only digits still possible in two cells, they must provide the answers for those cells and all other occurrences of those digits in the strip can be deleted. In row 6 there are two squares which contain only 2 different candidates (1,2, shaded green). If 1 and 2 are required for all the combinations for this row, as they are the only remaining candidates in these squares, they must be their answers. Therefore the other 1,2s in the row (shaded red) can be deleted.

## Naked Triples

Naked Triples: if three digit are required for all combinations which satisfy a strip and those three digits are the only digits still possible in three cells, they must provide the answers for those cells and all other occurrences of those digits in the strip can be deleted. In column 6 there are three squares which between them contain only 3 different candidates (7,8,9, shaded green). If 7,8,9 are required for all the combinations for this row, as they are the only remaining candidates in these squares, they must be their answers. Therefore the other 7,8,9s in the row (shaded red) can be deleted.

## Candidate Bounds

Candidate Bounds: the solution for a strip is generally contained in one of several combinations. If L is the lowest value in these combinations and H the highest, any digit lower than L or higher than H can be deleted. The sum 9 can be formed from 3 combinations of 3 digits: (1,2,6), (1,3,5) and (2,3,4). No value above 6 can be used, so 7,8 and 9, shaded red can be deleted.

## Impossible Combinations

Impossible Combinations: the solution for a strip is generally contained in one of several combinations. Any digits which do not occur in a satisfiable combinations can be deleted. The sum 11 can be formed from 4 combinations of 2 digits: (2,9), (3,8), (4,7) and (5,6). The digit 3 requires an 8, but there is no 8; The digit 5 requires a 6 but there is no 6. Therefore these digits can be deleted.

## Possible Combinations

Possible Combinations: the solution for a strip is generally contained in one of several combinations. Any digits which do not occur in a satisfiable combinations can be deleted. The sum 11 can only be formed from 1 combination of 4 digits: (1,2,3,5). This combination does not include 4, so all 4s in the row can be deleted.

## Unmatched Candidates

Unmatched Candidates: the solution for a strip is a particular permutation of one of several combinations. If the remaining digits in a strip do not permit any permutations of a combination, some of its digits may be deleted from the strip. The sum 13 can be formed from 3 combinations of 4 digits: (1,2,3,7), (1,2,4,6), (1,3,4,5). The digit 7 only occurs in one combination and requires 1,2 and 3 in the other squares. Neither of the two 7s shaded red can be matched with these digits as a least one has been deleted from the other squares. Therefore the 7s can be deleted.

## Isolated Necks

Isolated Necks: A "neck" is a square made special by a particular type of grid layout. This form of layout sometimes makes it possible to solve the square at the neck by simply adding and subtracting the sums across and down. Here we see a neck with solution 7. Because the block of squares to the left of the neck are completely isolated from the rest of the grid, the solution for the neck square is the sum of the sums across minus the sum of the sums down: 19+28+4+3-(21+19+4+3)=7.

## Possible Permutations

Possible Permutations: the solution for a strip is a particular permutation of one of several combinations. If the remaining digits in a strip do not permit any permutations of a combination, some of its digits may be deleted from the strip. The sum 11 can be formed from 4 combinations of 2 digits: (2,9), (3,8), (4,7), (5,6). The value 5 only occurs in one combination. Possible permutation are (5,6) and (6,5). However, for one of these there is no 6 remaining, so the corresponding 5 can be deleted.