# Backtracking with big inputs

I'm doing a Magic Square problem, and I'm using backtracking tecnique for do it.

So, the magic square asks you for an input which is the size of the square, and you generate this square, and you need to fill the cells with integer numbers, and the sum of the rows and the columns must be exactly this: That is the magic number, and you can't use the same numbers, if you use one number, you can't use it again.

And the numbers you can use, are between 1 and the magic number itself

So, I don't have troubles when I try a 3x3 square, but with 5x5 it's need a lot of time for compute it.

Of course I think about it, the algorithm tries from number 1, to number 65 in this case. And checks some validations, like the number is not already used,the sum of the rows and columns are not greater than 65, and in the last column and last row, the both sums are exactly 65.

So that needs tons of time.

So the question is, backtracking is really a bad idea if the input is big, isn't?

Backtracking is a very general problem solving strategy, but it's also potentially very slow: if we have n choice points with k choices each, a backtracking algorithm will run in O(kn) worst case, i.e. exponential time.

On the other hand, many practical problems will usually be solved correctly on first try, leading to a best-case run time in the class O(n). That is very good.

For example, many regex engines (Perl, PCRE) use backtracking to match input strings. In practice this is fine most of the time, but it is possible to craft input/regex combinations that take a very long time to run. Other regex engines therefore prefer non-backtracking based implementations that are guaranteed to run in O(n), but they have to sacrifice advanced features for that.

To make a backtracking-based solution faster, we can attempt two general strategies:

• minimize the number of choices at each choice point
• memoize partial solutions to avoid evaluating them repeatedly

To minimize choices you can analyze the problem to determine constraints that let you rule out candidate solutions. For example in your magic square problem, every row/column with empty fields has a remaining part of the sum that must be filled. But the further you progress, the fewer remaining numbers can be combined to this sum. You can use this to quickly home in on the few possible choices.

Another approach to minimize choices is to start with big assumptions that can be quickly disproven. For example, given the choice between various numbers, you might want to start with the biggest or smallest remaining number first. Maybe the other numbers will effectively “fall into place” with that choice, or you might quickly encounter a contradiction and can continue with a different choice. Compare the greedy algorithm.

Memoizing partial solutions is a memory-time tradeoff: we can avoid recalculating the same result but need to set aside memory for a cache. Memoization helps with recursive problems, and backtracking problems have this recursive structure. It can then happen that two different choices would lead to the same calculation. In a magic square problem that ignores diagonal sums, two squares are effectively identical if rows or columns are permuted, so we can use that to eliminate double calculations.

If we can build the memoization cache “bottom up” so that we don't need to keep the entire cache around, that would be called dynamic programming. This can be tricky to pull off because we are essentially solving a recursive problem in reverse. However, dynamic programming does not lend itself to your magic square problem.

Back Tracking

Back tracking really is a very simple graph search mechanism. It works best when the first path to be explored also happens to be the most probable path, or the cost of back tracking is trivial.

To that end you need to construct the algorithm to explore the most probable path first, then the next etc...

Constraints

When designing a search algorithm it pays to observe the search constraints.

Symmetry

As it is a square, rotating it and reflecting it won't change the sums. Taking a bit of a leap we could imaginatively draw 4 lines though the square, two on the diagonals, one vertical, and the other horizontal going through the squares centre.

This would cut the square up into octants where through rotation and reflection the octant can be moved around the square.

If a line goes through the middle of a cell the cell is in both octants adjoining the line.

``````   z               z
xy              xy
uvw
``````

and reflects and rotates like:

``````  4x4           5x5

zyyz          zywyz
yxxy          yxvxy
yxxy          wvuvw
zyyz          yxvxy
zywyz
``````

Straight of the bat its apparent that the first pick, only needs to be tried in once in each location of one octant. All the other locations are simultaneously tried because they are a reflection/rotation of the original.

``````   1234
1 _yy_
2 y__x
3 y__y
4 _yy_
``````

We can take this further by making a co-ordinate system. Simply label each octant. Now each pick is `octant:cell:value`. ie `a:x:1` is the `x` cell in octant `a` containing `1`.

``````  _cb_
d__a
e__h
_fg_
``````

The best part is that now we can formally show that certain sequences of co-ordinate values do not need to be retried.

`````` a:x:1
``````

is the same as

`````` //reflected
b:x:1
c:x:1
d:x:1
e:x:1
f:x:1
g:x:1
h:x:1
``````

and

`````` a:x:1, b:x:2
``````

is the same as:

`````` //rotation
c:x:1, d:x:2
e:x:1, f:x:2
g:x:1, h:x:2

//reflected and rotated
b:x:1, a:x:2
d:x:1, c:x:2
f:x:1, e:x:2
h:x:1, g:x:2
``````

This allows the backtracking to derive the maximum amount of information from a failed prefix. We simply do not have to investigate these other squares.

Simultaneous equations

You can also see the problem as a set of simultaneous equations.

Each row is a sum, Each column a sum, and both diagonals are sums. Each shares with each cell in their equation with two other equations. All the equations are equal. And each cell uniquely contains one value from a set of values.

With that this becomes a set of `2N+2` Linear equations (rows + columns + diagonals).

The benefit here is that we can reject a particular search path, before completely exploring it.

Each linear equation here is monotonic so its value is atleast the sum of the filled cells. Then the remaining portion of the equation is some combination of `N - CellsFilled` values from the still available values.

So the largest sum of filled cells + the smallest sum of values not yet assigned, is the smallest magic number.

If at any point, any equation can not be atleast as large as the smallest magic number then the square cannot be completed. So we do not have to further explore that particular co-ordinate prefix and can backtrack.

Similarly if the largest magic number, picked by the smallest sum of filled cells + the largest sum of remaining values, then the square cannot be completed.

Guidance

This leads us to an interesting way to select the next cell for filling, it needs to be on the equation with the currently smallest filled cell sum.

Any other choice is more likely to invalidate the square.

Smarter Backtracking

By constructing the search paths to avoid obvious dead-ends, to ignore equivalent but different looking paths, and figuring out a heuristic for selecting the next cell the search is more likely to show good behaviour.

That being said, consider finite state machines particularly the non-deterministic sort for performing a breadth first search instead. Add the above heuristics to thin out duplicates. You may be surprised that it is way more efficient at larger scales.