Kakuro - puzzle with numbers . The name Kakuro comes from the Japanese abbreviation kasan kurosu (加 算 ク ロ ス, cross addition); in the USA, the puzzle is also known as Cross Sums .
Game Rules
The field consists of black and white cells. Several white cells running in a row horizontally or vertically are called a block . For each block, the sum of the digits that must be in this block is known. For horizontal blocks, this amount is usually written directly to the left of the block, and for vertical blocks directly on top.
In all white cells you need to enter one digit from 1 to 9 so that, firstly, the sum of the digits in each block matches the indicated number, and secondly, so that all digits in each block are different.
Computational complexity
Kakuro's problem is NP-complete . The problem of Hamiltonian subgraphs of a planar mixed graph with degrees of vertices of at most 3 is reduced to it (see the Proof of the NP-completeness of the kakuro problem ).