Started using subversion

A revision control system for personal projects may sound too much but it is really useful. Sometimes you want to revert some changes. Sometimes you want to refer to the old code. You could use backup files but it is very cumbersome. So I decided to use a revision control system for the kakuro solver project.

I have been using Rational ClearCase for my job. It is really powerful and I love it but obviously I cannot afford. I did some research on it and subversion looked great for my purpose.

Subversion is a client-server type RCS. I didn't want to administer the server myself, so I need a free repository ('free' is important). There are many services out there and I chose assembla. The client is, of course, TortoiseSVN.

I imported the current Kakuro solver files and made some changes (I actually had a bug to fix). The UI is different from ClearCase but it is easy to find how to do what I want to do. I found it interesting that I don't need to check out files before I make change. On ClearCase, I need to check out files even when they are in a private branch.

Used the graphical diff tool. It's really similar to the ClearCase one. Found no problem in using.

So far, so good.

Kakuro Solver - how to create database of solution sets

I created the database of solution sets programatically. I used the code below to enumerate {number of cells, clue} pairs:
 

typedef std::bitset<9> valueSet_t;
typedef std::list<valueSet_t> result_t;
const unsigned NumToBit[] = {
 0, 1, 2, 4, 8, 16, 32, 64, 128, 256,
};
void iterLevel(size_t begin, size_t level, size_t sum, valueSet_t & set, result_t & result)
{
 if(sum < begin)
  return;
 if(--level == 0) {
  if(sum <= 9) {
   set |= NumToBit[sum];
   result.push_back(set);
   set &= ~NumToBit[sum];
  }
  return;
 }
 for(size_t i = begin; i <= 9; i++) {
  set |= NumToBit[i];
  iterLevel(i + 1, level, sum - i, set, result);
  set &= ~NumToBit[i];
 }
}

void kakkuroSums()
{
 valueSet_t set;
 result_t result;
 for(size_t level = 2; level <= 9; level++) {
  for(size_t sum = 3; sum <= 45; sum++) {
   set.reset();
   result.clear();
   iterLevel(1, level, sum, set, result);
   if(result.size() > 0) {
    // generate the database here
  }
 }
}

The idea is, when I calculate solution sets for an entry with 5 white cells, call iterLevel() recursively 5 times. Each call picks up a solution value for a white cell.
For example, assume we want to find solution sets for 13-in-three. The first call of iterLevel() picks up "1" as a solution value. The second call picks up "2". The last call finds a set {1, 2, 10} but this is not a valid set, so just returns. Back to the second call, it picks up "3" next. The last call finds a set {1, 3, 9} and this is valid, so remember the result and returns. And so on.

But after I made the database, I realized that I could find all solution sets by simply finding all combinations of 1 through 9. And it is easy to get all the combinations by checking values from 3 to 511.
For example, 3 - 0b11 in binary. If you interprete the least bit as "1" and the second least bit as "2", 3 is interpreted as a solution set {1, 2} for 3-in-two. 4 has only one bit set, so skip it. 5 is interpreted as  {1, 3}. 6 as {2, 3}, 7 as {1, 2, 3}, and so on.
The result is not sorted, so you need to sort it in the order you want but it looks faster than what I actually did.

Kakuro solver - data structure

To solve a puzzle fast, algorithm is crucial. and the data structure is important to implement the algorithm properly. Here, I am going to explain the data structure I used for the kakuro solver.

Representation of solution sets and possible solutions
Values in solution sets and possible solution values are represented as bits. The least bit in an integer represents the value "1", the 5th least bit represents "5", and so on. This way, you can easily calculate union and intersection by bitwise logic operations.
Actually I used the bitset container of the C++ STL. I would create a custom class for solution sets if it weren't fast enough but it is really fast!

White cells
A white cell has three properties. The first one is possible solution values. The second one is pointers to the two entries which the white cell belongs to. The last one is the position or coordinate in the problem board.

Entries
An entry has four properties. The first one is possible solution values which its white cells can take.

The second one is a list of solution sets. I used an STL list container because

1. I don't need random access. I sequentially access the list
2. A white cell can be removed from the list in constant time.

The third one is a list of white cells which don't have a unique solution yet. When a white cell get a unique solution, the cell gets removed from the list and the solution value is stored in the last property.

List of white cells without a solution
When you iterate the calculation of possible solution values of white cells, you want to skip white cells which already have a solution. I used a list container to store white cells which don't have a solution yet.
I used a list container because of the same reason as the solution sets for entries.

Database of solution sets for an entry
I need the initial solution sets database for entries to initialize an entry. I could calculate an initial solution sets each time I initialize an entry but apparently it is a waste of time. I store the database in a form of const static variable like:

const static valueSet_t CAND2_3_12(0x3);
const static valueSet_t CAND2_4_13(0x5);
const static valueSet_t CAND2_5_14(0x9);
const static valueSet_t CAND2_5_23(0x6);

valueSet_t is a class to represent solution sets in bits; derived from the bitset container.

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!

A kakuro solver - Kakkuro

Kakuro is one of my favorite puzzles. As a programmer, I always wanted to make a software to solve kakuro. I knew there were already a few good solvers out there but I couldn't help making my own. If you are interested in the kakuro solver, you can get it here.

Goals:

• Solves kakuro fast, really fast
• Finds all solutions if a problem has multiple solutions
• Shows how it is solving - which cells have a solution, how it is backtracking

Technical:

• Language: C++
• Tool: Visual Studio 2012 Express
• Platform: Windows 8.1 (haven't tried on older Windows but it should work)

Here are some snapshots:

This is really easy.

A problem with multiple solutions;
Over 2 million solutions!

Shows the 1019520th solution

The solver is backtracking.

It takes about 90 seconds on my machine to solve the problem above with 2 million solutions.