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...
When designing a search algorithm it pays to observe the search constraints.
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.
and reflects and rotates like:
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.
We can take this further by making a co-ordinate system. Simply label each octant. Now each pick is
a:x:1 is the
x cell in octant
The best part is that now we can formally show that certain sequences of co-ordinate values do not need to be retried.
is the same as
is the same as:
//reflected and rotated
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.
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.
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.
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.