How my Kakuro Solver works ?

In this page I will explain the steps my Kakuro Solver uses to solve Kakuro Boards and gives examples.
This explanation is will show basic algorithm but it uses few optimizations in order to short the computation time like check only parts that got changed last step or choose the best number to guess and where and so on.


Step 1 Find sequences

Go over the board and for each number in the Diagonal part (orange color with diagonal line on them) count the amount of Number parts (yellow color) it points to and according to that amount find the possible sequences of numbers can be place.

Example:
If the number in the Diagonal is 5 (mark in blue) and it have two Number part, the possible sequences are {1, 4} {2, 3} {3, 2} {4, 1}.

Step 2 Write notes

For each Number part (yellow color) get all possible numbers according to the vertical Diagonal part and the horizontal Diagonal part. Do AND between them.

Example:
If the Number part is the first Number part in vertical Diagonal part that have the following possible sequences: { {1,5} {2,4}, {4, 2} {5,1} } then the possible vertical numbers are { 1, 2, 4, 5 }.
If the Number part is the second Number part in horizontal Diagonal part that have following possible sequences: { {1, 3} {3, 1} } } then the possible vertical horizontal numbers are { 1, 3}.
Do AND between { 1, 2, 4, 5 } and { 1, 3} so the possible numbers in this Number part is { 1 }

Step 3 Place numbers

Go over the board and for each Number part (yellow mark) check if there is only one possible number, place the number.

Example

Step 4 Remove not possible sequences

Go over the board and for each number in the Diagonal part check which of the sequences are not possible (according to the Number parts value / notes) and remove them.

Example a:
If the number in the Diagonal is 4, it have two Number parts and the possible sequences are { {1, 3} {3, 1}} but the second number must be 1 (the second Number part value is 1) then the only possible sequence left is {1, 3}.
Example b:
If the number in the Diagonal is 7, it have two Number parts and the possible sequences are { {1, 6} {2, 5} {3, 4} {4, 3} {5, 2} {6, 1}} but according to the Number parts' notes the first number can be only {1, 2, 3, 4} and the second number can be only {1, 2, 4, 5}
then the only possible sequences left are { {2, 5} { 3, 4} }.

Step 5 - go back to step 2

As long there was a change in steps 2,3,4 the algorithm will go back to step 2 and try again. If there weren't any changes after running steps 2,3,4 it will continue to Step 6 (assumes the board isn't already full and no errors were found).

Step 6 Guess a number

It is simple as it sound. Choose an empty Number part (a Number part with no value in it) and according to the notes it got guess the number. Keep using the algorithm until board is full or got error. If board is full and don't got error the solution is right if there is an error go back and guess different number in the Number part chose. If all the numbers in the parts will give an error so it is impossible to find a solution to that board.