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