Constraint solving using back tracking

1

I am learning a bit about constraint solving using back tracking.

Back tracking is a general algorithm to solve problems where you have partial information about the solution. The algorithm I am using is deterministic and guaranteed to find a solution (if any).

quickbacktrack is a generic library that lets you debug and customize the search for solution.

Examples:

  • Sudoku
  • Knapsack
  • 8 Queens

What I like about this method is the similarity to game level design. One could start with a rough design and use constraint solving to generate additional details. Then you could hand tune the result to your taste.

There is no need to tell specifically where to put things. Instead you can program the constraints such that a tree can not be closer to a building than 4 m, but you still want at least 200 trees in the area.

One problem can be the time required to find a solution. I made the search for next position customizable with the hope that there is an efficient heuristic for a typical game level.

2

Currently I am running through different sizes of 8 queens to see how these compares in performance:

  1. select next empty slot
  2. select the minimum amount of choices

So far, option 1 has managed to solve up to size 33, while option 2 has solved up to 114.

Some takes a few hundred or a few thousand, and then suddenly it takes many millions. Option 2 seem be better than option 1 on most sizes.

However, because 2 is more expensive to evaluate, it means those taking many millions move to solve takes also much longer time. Therefore, it looks like option 2 has better average performance while option 1 has better worst case performance.

Such constraint solving problems are known to be hard to predict because there is an exponential running time. Maybe one could try solving using different strategies on multiple cores and improve the worst case performance significantly that way.

3

I’m done collecting data about the 8 queens puzzle. Tested 4 different search heuristics, logged number of iterations to solve. Here are the 4 strategies:

  1. Get the next empty row
  2. If all rows can be assigned a queen, get next empty slot
  3. Find the empty row with least amount of possibilities
  4. If all rows can be assigned a queen, find empty row with least amount of possibilities

Interestingly, 2 is better than 1, but 4 is no different than 3. This is because N-1 queens on a N chess board can not cover all squares. Might work better on a different puzzle.

Link https://github.com/bvssvni/quickbacktrack/blob/master/stats/queens.txt