My kakuro solver is fast and actually I am really satisfied with the result. But there are kakuro problems with a unique solution which the solver needs to backtrack to solve. In general, the backtracking is costly and there is room for improvement.
There are two ways to improve backtracking; one is to improve the backtracking itself and the other is to avoid the backtracking.
Improving backtracking
Roughly speaking, the solver does two things;
- Bitwise calculation
- Picking up a cell without solution and try all possible solutions
What to pick up at the step is very important. For example, let's assume the solver already knows the solutions for the gray cells below and is about to start backtracking.
The current implementation searches for a cell without solution from left to right and then from top to bottom. In this case, the solver picks up cell 1 and try the first possible solution. The solution of cell 2 is determined easily. If the solver fails to find a solution of the problem soon, it picks up another cell for the next level backtracking and that will be cell 3.
The issue here is, the backtracking at cell 3 may do the same thing again and gain for each possible solutions because cell 1 and 3 are far away from each other and their results of backtracking may not affect each other.
If the solver picks up a cell for the second backtracking based on the result of the first backtracking, it could backtrack more efficiently.
Avoiding backtracking
I may be able to reduce the chance of backtracking by adding other deduction rules. There are two rules I didn't use.
- I already use the rule "if a cell has only one possible solution value, the value is the solution for the cell and the other cells in the same entry cannot use the solution value". This rule can be extended for multiple cells, that is, "if N cells in an entry have the same set of N possible solutions, the other cells in the entry cannot have the possible solutions."
For example, let's assume we have a 15-in-five entry. If the first and second cells in the entry have only two possible solutions {1, 2}, then the other three cells cannot have {1, 2}. If the third cell have the solution "1", then the first two cells have the only one solution "2". One of them has no solution!
Another example is, again, we have a 15-in-five entry. This time, the first cell's possible solutions are {1, 2}, the second's are {2, 3}, and the third's are {1, 3}. Each of these cells has two solutions but if you look at these three cells as a whole, they have the common three possible solutions {1, 2, 3}. So the other two cells cannot have {1, 2, 3}.
- I already use the rule "if a solution value in an entry must be the solution in a cell and only one cell in the entry can have the solution value, the cell's solution is the solution value and cannot have other values". This rule also can be extended for multiple cells: "if N solution values in an entry must be the solutions and only N cells in the entry can have the solution values, the cells' solutions are one of the solution values and cannot take any other values."
For example, let's assume we have a 17-in-five entry. The possible solution sets are {1, 2, 3, 4, 7} and {1, 2, 3, 5, 6}. {1, 2, 3} are common, so they must be a solution of a certain cell in the entry. If each cell in the entry currently have possible solution values like this; the first {1, 2, 3, 4, 5, 6, 7}, the second {1, 2, 3, 4, 5, 6, 7}, the third, fourth and fifth {3, 4, 5, 6, 7}. Now the two possible solution values "1" and "2" appear in the first two cells only. So the first two cells cannot take other values.
These two rules probably work but they look costly because you need to enumerate combinations of cells or solution values to use these rules. As the current solver can solve most of Kakuros without backtracking, if I apply these rules carelessly, the total solution can easily get worse.
