Since the Kakuro Explainer tool is based on a Kakuro Solver, finding a good solver was

an important process at the beginning of the project. To make sure the tool can benefit

as much as possible from the solver it should meet the following

requirements: To make sure the tool has a good performance, the solver

should be effective and avoid unnecessary long computations. In

addition, it would be good if it was possible to reuse parts of the

solver to generate some of the hints. The solver should also be

intuitive and have a comprehensible logic behind its algorithm. This is

especially important for reusing parts of the solver. The programming

language of the solver is also an important issue. Since it should be

compatible with the Kakuro Explainer tool, the solver should be written

in a language were constraint problem solver libraries are available and

that is suitable to program the tool.

The solver finds the right numbers for the cells by eliminating all

impossible numbers for a cell until only one possible number remains.

This number then must be the solution for this cell.

To do so, it tries the numbers from 1 to 9 for all cells of a sequence

and marks the numbers that lead to a contradiction During simple

iteration it performs this step for only one sequence. During level

1-iteration, it performs this step on all sequences of the puzzle.

To fasten up the solving process, the solver selects the sequences from a

priority queue. This priority queue contains the sequences the

algorithm has to solve and sorts them in ascending order according to

their number of possibilities for building the required sum. Therefore,

sequences with less possible combinations for the sum, where the solver

might find a solution with fewer iterations, are considered earlier than

sequences with a larger number of possible combinations.

The queue not only determines the order in which the algorithm considers

the sequences but also what type of iteration it should use on the

sequence. Sequences in the queue can have a “use level 1-iteration”

flag, that is denoted by a “T” following the sequence in the status bar.

There are some rules regarding the “use level 1-iteration” flag:

• If a sequence without a flag is removed from the queue, it will be added to the queue again with the flag set.

• If a sequence without a flag is added to the queue, any flagged version of this sequence will be removed from the queue.

• All sequences that have not been considered with level 1-iteration and

have not been solved yet are in the queue, either with or without the

flag.