11/25/2013

Algorithm of Kakuro Solver

Actually the algorithm I used for the Kakuro Solver is nothing special. I just implemented the solving techniques I use when I solve a kakuro myself. The slover applies the techniques completely, thoroughly and fast if you implement them properly.

I use terminology used in Wikipedia to explain the algorithm.

  1. First, set up solution sets for each entry. For example, a 8-in-two entry have 3 solution sets, {1, 7}, {2, 6}, and {3, 5}. The union of the solution sets - 1, 2, 3, 5, 6, and 7 in this exapmle - is the possible solutions for white cells in the entry.
  2. A white cell belongs to a vertical entry and a horizontal entry. For each white cell, calculate the intersection of the possible solutions of  both entries. This intersection is the possible solutions for the white cell.
  3. Using the possible solutions of the white cell, updates the entries which the white cell belongs to:
    1. if the possible solutions of the cell have no common values with a solution set of an entry, the solution set cannot be the solution. So remove the set from the entry.
      For example, if it turned out a white cell in a 8-in-two entry can take only 2, 3, 5, or 6, there is no common value with the solution set {1, 7}. So eliminate {1, 7} from the entry.
    2. calculate the union of possible values of all the cell in an entry. If any of values in a solution set of the entry are not in the union, the solution set cannot be the solution. So remove the set from the entry.
      For example, assume a white cell in a 8-in-two entry can take 1, 2, or 3, and the other white cell can take 5 or 7. The union of the white cells is 1, 2, 3, 5, and 7. The solution set {3, 6} will be removed because the union doesn't contain 6.
    3. if the possible solution value of the cell is only one left, that is, the solution of the cell is determinted, removes the value from the possible solutions for the entries. This is because no other cell can take the value.
    4. Re-calculate the possible solutions for the entries.
  4. Repeat step 2. and 3. Most of easy problems are solved with these steps. Still these are not enough for more difficult ones. For such difficult ones, applies step 5 below.
  5. For each entry, calculate the intersection of (remaining) solutions sets. If it is not empy, the values in the intersection must be a solution in one of white cells. For each one of the values, find how many white cell can take the value. If only one white cell can take the value, the white cell's solution is the value.
  6. Repeat steps from 2 to 5 until the solution of the puzzle is found.
  7. If no solution is found, do backtracking. Pick up one of white cells which have no solution yet. Temporarily set one of the possible values to the white cell and repeat the steps from 2 to 6. When finished with the value, try the next possible values. When you are done with all the possible values, the problem is solved!

No comments:

Post a Comment