Puzzle Programming - Impossible to optimize?

Question

I've been writing programs to solve various number puzzles, but I'm constantly designing unreasonably complex search algorithms that I can't optimize.

For example, in one puzzle, you are given a 3x3 grid of numbers 1 through 9 below:

123
456
789

You're allowed to cycle the numbers in any row or column in any direction. Below is an example of shifting the top row of numbers to the right. The numbers will loop if they are at the edge of the grid.

123 -> 312
456    456
789    789

You must move the numbers in this manner until you create a magic square in which the sum of the numbers in each column, row, and diagonal is 15.

I've written a DFS brute-force algorithm to test all possible sequences of moves, though the number of available moves at each turn increases exponentially (approx. 12 ^ [current turn]), rendering it useless.

It seems a BFS would be optimal to find the correct moves, but that would require me to store hundreds if not thousands of copies of the grid in order to backtrack!

---

I run into these kinds of problems all the time. Both BFS and DFS algorithms use too much memory and time, respectively. I need help optimizing algorithms like these so they run faster and efficiently. Maybe recognizing patterns and relations of the numbers or giving the algorithm logic to work towards a goal would help? (I don't know what that would entail).

EDIT:

My fixed algorithm works like a charm. Learning how to number my permutations was essential. Thank you all!

Answer 1

I'd suggest looking up memoization (caching the results of a function call based on the inputs so that the function is not recomputed for identical subsequent calls). Having understood memoization, I'd look up dynamic programming (still saving the results of the function, but also reordering computations to eliminate unnecessary calls). Some explanations of dynamic programming use a recursive definition of fibonacci, then fibonacci + memoization, and finish with computation reordering.

For DFS and BFS problems in general, the technique known as Branch and Bound might be of interest. The bounding part can give you substantial gains in some problems. Trimming a subtree one generation higher than with a less sophisticated bound eliminates many new branches in your search tree (alternate wording: since trees grow exponentially with depth, pruning your search early is important).

For your particular problem, I believe that optimizations are possible.

First, let's consider the DFS. I believe that all permutations of your board are reachable from any configuration of the board. As a consequence. DFS can be implemented without backtracking (though I'm guessing you knew that). Depth only search? (EDIT: per Daniel Fischer, this is wrong. Half of states are reachable, though it doesn't impact the no-backtracking statement since backtracking won't help you reach your unreachable states)

But, you might find that you don't want to move through many permutations simply to find that you haven't yet solved the problem. Backtracking might actually help. Or...

Consider looking at your end goal. Magic squares have some particular properties that you might exploit to choose your operations more carefully. For example, since the rows and columns must sum to 15, you know 9, 8, and 7 cannot share a row or a column with each other. Neither can 9 and 6. 6 can go with 8 and 1 or 7 and 2. 6 cannot share a column/row with 5 and 4 even though they sum to 15 because of the pigeon-hole principle (each row/column contains either 9, 8, or 7). In fact, you might find that your problem has a unique solution, modulo some sort of cyclic permutation in all-rows, all-columns, reflection, and transposition. The diagonal requirement further constrains the valid solutions.

Aside: the logic used in the previous paragraph is not unlike constraint-based-programming. It's not really an optimization technique (though it might be considered an optimization on implementation time if not run time), but might be of interest to you as well (also note that magic squares and sudoku are frequently used to illustrate constraint-based programming).

Now you have a goal:

1. Describe a solution state.
2. Reach one of the known solution states with the fewest moves.

This is a fundamentally different approach than searching the various permutations until the problem is solved. I'd try to find a dynamic programming solution. For a slightly easier dynamic programming problem that moves from a start state to a goal state with incremental operations, take a look at the Levenshtein edit distance problem.

Answer 2

A few remarks in addition to ccoakley's nice answer and stubbscroll's comment, concerning the specific example and a few general principles.

Regarding stubbscroll's remark that this particular problem has only 9! = 362880 different states:
One (fairly easy) way to encode permutations as numbers is indexing the permutations by lexicographic ordering. For example

0 1 2 3  -->  0
0 1 3 2  -->  1
0 2 1 3  -->  2
...
1 0 2 3  -->  6
1 0 3 2  -->  7
...
3 1 2 0  --> 21
3 2 0 1  --> 22
3 2 1 0  --> 23

The trick is writing the index in factorial base,

n = a_1 * 1! + a_2 * 2! + a_3 * 3! + a_4 * 4! + ...

where 0 <= a_k <= k. If you have s symbols, the indices range from 0 to s!-1, so you have s-1 coefficients in the factorial-base expansion of n, (a_1,a_2,...,a_(s-1)). The permutation with index n is then found as follows

 for i = 1 to s-1
    the i-th symbol becomes the (a_(s-i)+1)-th smallest unused symbol
 the last symbol is the left over one

Since that's not particularly clear, an example. Say we look for the permutation with index 4231 of {1,2,3,4,5,6,7,8}. First we expand 4231 in factorial base

4231 = 1 + 2*2115 :  a_1 = 1
2115 = 0 + 3* 705 :  a_2 = 0
 705 = 1 + 4* 176 :  a_3 = 1
 176 = 1 + 5*  35 :  a_4 = 1
  35 = 5 + 6*   5 :  a_5 = 5
   5 = 5 + 7*   0 :  a_6 = 5

all further coefficients (here just a_7) are 0. It's better to follow writing the a_i in reverse order, (a_7,a_6,...a_1), so

 coefficients      symbols       choice
0,5,5,1,1,0,1  1,2,3,4,5,6,7,8     1
 5,5,1,1,0,1    2,3,4,5,6,7,8      7
  5,1,1,0,1      2,3,4,5,6,8       8
   1,1,0,1        2,3,4,5,6        3
    1,0,1          2,4,5,6         4
     0,1            2,5,6          2
      1              5,6           6
      -               5            5

Result: 17834265.

Find the index of 246351:

symbols     count     perm    index(head)
1,2,3,4,5,6   6   2,4,6,3,5,1    1         a_5 = 1
 1,3,4,5,6    5    4,6,3,5,1     2         a_4 = 2
  1,3,5,6     4     6,3,5,1      3         a_3 = 3
   1,3,5      3      3,5,1       1         a_2 = 1
    1,5       2       5,1        1         a_1 = 1

index is `1*5! + 2*4! + 3*3! + 1*2! + 1*1! = 187.

So now we have a fairly simple way of converting between permutations and their indices. The conversion isn't super fast (O(s^2)), but you get easy and fast comparison and lookup (have I seen the state before?). Whether it's a gain remains to be decided in each case.

Now, for the particular case at hand, we have some further restrictions reducing the search space.

• Each move is a cyclic permutation of three elements, thus an even permutation.

Hence all combinations of such moves are also even permutations, meaning half of the possible states are unreachable. We are left with (at most) 9!/2 = 181440 reachable states. Indexing even permutations by lexicographic ordering is only slightly more complicated. The crucial point is that a permutation is even if and only if the sum of the coefficients a_k in the factorial-base expansion of its index is even.

Reduce the search space using constraints and symmetries. If you're employing a search strategy using a structure with all possible states, this will reduce the memory requirements by a corresponding factor. If your search strategy only touches reachable states, the constraints don't reduce the number of steps, but they can still speed up the search due to the lower memory footprint. The use of symmetries can reduce the number of steps by identifying equivalent states.

In the example problem, we have the further nice situation that the 5 is already in the correct place, and that an optimal solution doesn't move it ever. So we need only consider even permutations of 8 symbols, reducing the search space to 8!/2 = 20160 possible states. (Though that is not obvious.)

In general, however, it is difficult to prove that an optimal solution never leaves a particular subset of the possible states, so you can rarely directly impose such a restriction to your search.
But it is often the case that you can find a good solution of the problem using such a restriction and then use the good solution to prune early in your search for the optimal solution in the unrestricted search space.

A variant one can often use is finding an approximation by a greedy strategy and using this as a bound to prune early in an exhaustive search.