Next target - slitherlink solver

I am satisfied with my Kakuro solver. There are a few possible improvements for the Kakuro solver as I mentioned in the previous post, it wouldn't be very visible. So I want to try a solver for a different puzzle.

Sudoku (Wiki) is, of course, a candidate. It is one of the most popular puzzles in the world. But I don't want to make a Sudoku solver because:

1. There are already a lot of good solvers.
2. It is less challending than Kakuro. Sudoku can be solved by the same tricks as Kakuro. In a sense, Sudoku is a varation of Kakuro; a 9x9 Kakuro with no black cells except the top and leftmost cells, and with exposed solution values for some cells to guarantee a unique solution.
3. Actually I create a solver before - in Microsoft Basic (no, it was not Visual Basic. It was a Basic with line numbers). It ran on a Z80 machine. The machine was very slow at that time but the Sudoku solver still ran fairly fast.

So what's the next? I am considering Slitherlink (Wiki/nikoli.com). It seems more challenging than Kakuro.

I am also considering C# as a language instead of C++. I have been using C++ for many years but I want to try something new. It should be a fun!

Kakuro Solver - Ideas for improvement

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;

1. Bitwise calculation
2. 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.

1. 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}.
   
2. 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.

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.