Solve the famous “square sum” problem with an elegant searching method.
Find a permutation of sequence [1...N], where every two adjacent numbers sum to a square number.
For example, when N=15, we have:
[9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8]
I have tried backtracking algorithm, but it will always stuck at searching 100+, even with heuristic methods and some technics like "branch and cut".
So I design a new approach:
We define an array as "valid", when every two adjacent numbers of the array sum to a square number.
We always maintain two valid arrays named A and B, where concat(A, B) is a permutation of sequence [1...N]. This serves as our invariant in all iterations.
Supposed we have find a solution array to sequence [1...(N-1)]. By definition, this array is valid, so we assign it as inital value of A. This solution can be found with brute-force algorithm when N is small enough.
Then we assign singleton [N] as inital value of B, to satisfy the invariant.
Next, here comes the loop:
Obviously, we can do zero or more operations as follows.
1. swap A and B or not
2. reverse A or not
3. reverse B or not
and won't break the invariant. After a random combination of that, we
4. split A into C, D, where the last number of C and the first number of B sum to a square number.
Thus, let A' = concat(C, B), B' = D, we got a new pair of valid arrays. After this operation, we keep the invariant.
Finally, check if any endpoint of A and any endpoint of B can sum to a square number. If so, concatenate them accordingly, and return the result. if not, go on for the next iteration.
At step 4, chances are there is no valid move, e.g., A is too small. In that case, we can do another combination of step 1/2/3. In most situations, there are many valid moves at step 4, and we just pick one randomly.
After several iterations, we can always grow the valid permutation of [1...(N-1)] into a valid permutation of [1...N].
Applying this algorithm repeatedly, we can get the solution to an arbitarily large N.
Though in theory termination of the algorithm is not guaranteed, in practice it is surprisingly fast. Benchmark results show that we can grow N into 40000 in seconds, way faster than backtracing algorithms.