by crabmouse » Mon Nov 16, 2020 10:57 pm
Hi MM,
The fact that that each point in the Kakuro grid has two constraints, one vertical and one horizontal, is not a problem. In fact, it is perfectly normal.
In both Sudoku and Kakuro, each point belongs to multiple constraints.
Each constraint has its own independent columns in the Exact Cover matrix which are not shared by other constraints. There is one column for each value that can appear in the constraint. Suduko is more simple because each of the values appears exactly once in a constraint.
In Sudoku each point is shared by three constraints, one for the row, one for the column and one for the 3x3 box that contents it. Each row represents the assignment of a particular value to a particular square in the grid. The row will have 4 ones in the Exact Cover matrix. One for the column that relates to the point and ensures that only one value is assigned to the point. The second is one of the nine columns for the row constraint, which ensures that the value appears exactly once in the row. Similarly, the other values lie in one of the nine columns for the column constraint and in one of the nine columns for the relevant box constraint.
In Kakuro as well, the main rows each deal with the assignment of a specific value to a specific point. The row will have three ones in the Exact Cover matrix, one in the column that ensures that the point is assigned only one value, one to ensure that its value appears exactly once in the horizontal clue and one column that ensures that its value appears only once in the vertical clue. The complication with Kakuro is that, unlike Sudoku, values sometimes do not appear in the answer. That is why we have to add extra rows to the Exact Cover matrix to supply the missing 1's so that the column has a total of one when the correct rows are selected.
For example, if a clue has three elements totalling 8 it can be satisfied by {1,3,4} or {1,2,5) and it will have five columns for each of the values 1,2,3,4,5 and one column to indicate which of the two solution sets was used. We have to add two rows to the Exact Cover matrix, one for {1,2,5} and one for {1,3,4}.
The row for {1,3,4} will have 1's in the columns representing 2 and 5. If the solution for the problem uses the values {1,3,4} the columns for the values 1, 3, 4 will be satisfied by the rows that assigned 1,3,4 to the specific points. The columns for values 2, 5 will be satisfied by the extra row for {1,3,4} which supplies the missing ones.
I have written a program to solve and compose Kakuro problems and I use this exact cover to check problems as they are entered. It runs instantaneously on smaller Kakuro problems, but the Exact Cover DLX algorithm doesn't scale well for larger problems. Problems of the size 24x14 are around the critical size. Sometimes they are solved quickly, but sometimes they use so much time that I lose patience.