Square-Sum Puzzle
January 16, 2018
The text of the problem gives a clue to a possible solution: “Rearrange the numbers …” sounds like a permutation, so one solution is to create all the permutations of the numbers from 1 to 15, then check each permutation for the square-sum property. But that sounds dreadfully slow, as there are n! permutations of a list of n items, and each requires a linear-time check for the square-sum property, so the time complexity of that solution is O(n n!).
Our algorithm builds a graph through the list of possible square-sum pairs, then performs depth-first search through the graph to find the solution. Here we build the graph:
(define (adjacent n k) (filter (lambda (i) (and (not (= i k)) (square? (+ i k)))) (range 1 (+ n 1))))
(define (make-graph n) (map (lambda (k) (cons k (adjacent n k))) (range 1 (+ n 1))))
The result of (make-graph 15)
is this adjacency matrix:
((1 3 8 15) (2 7 14) (3 1 6 13) (4 5 12) (5 4 11) (6 3 10) (7 2 9) (8 1) (9 7) (10 6 15) (11 5 14) (12 4 13) (13 3 12) (14 2 11) (15 1 10))
From this point, finding a solution is easy. It is obvious that the endpoints of the path are at 8 and 9. Starting from 8 we have either 8 1 3 or 8 1 15, but 8 1 3 leads to a dead end at 8 1 3 6 10 15 or 8 1 3 13 12 4 5 11 14 2 7 9 (which misses 6 and 10), so we take 8 1 15 and the remaining steps through the path are forced: 8 1 15 10 6 3 13 12 4 5 11 14 2 7 9. Here’s the depth-first search:
(define (square-sum n) (let ((graph (make-graph n))) (call-with-current-continuation (lambda (return) (do ((node n (- node 1))) ((zero? node) (list)) (let dfs ((node node) (neighbors (assoc node graph)) (path (list node))) (when (= (length path) n) (return path)) (do ((neighbors neighbors (cdr neighbors))) ((null? neighbors)) (when (not (member (car neighbors) path)) (dfs (car neighbors) (assoc (car neighbors) graph) (cons (car neighbors) path))))))))))
And here we see the solution:
> (square-sum 15) (8 1 15 10 6 3 13 12 4 5 11 14 2 7 9)
You can run the program at https://ideone.com/3KjpNC.
In Python. It is easy to solve this by hand, as there are not many possibilities. A brute force solution should do the trick. There appears only 1 solution.
@Paul, there are two solutions. The one you listed and its reverse.
Here’s mine.
@kernelbob: it is indeed more correct to say that there are 2 solutions, but the are essentially the same.
Finding a path to 15 is pretty easy, it only takes 48 tries for my depth-first search. However, the Numberphile2 channel says they searched up to 299. What sort of pathfinding algorithm did they use? 42 my laptop does in a second with 945,000 calls, but even the short jump to 45 takes a long time with over 43,000,000 calls. There must be a smarter way to start winding your way through the paths. Any ideas?
A little more digging shows Charlie used Sage and its hamiltonian_path() function which found a path through 150 nodes in 90 ms. (Bang fist on table) There must be a better way.
In Python using DFS. Function count and takewhile are from the itertools module. This code needs 69 ms for 299 for the first solution. I got an enormous speed up by searching first the nodes that have least amount of successors left (last line of the code).
Hi Luke,
There are some options for pruning in your algorithm. On line 53 you have already constructed a full path, but you can check along the way.
For example, add a check on line 23 that does something like: if we have used an even amount of nodes, check if the last 2 numbers add up to a square.
Here’s a solution in C++ that generates all possible paths, using Algorithm X from TAOCP 7.2.1.2 to itereate over permutations (constructing only permutations with valid prefixes).
I started writing it in C, then switched to C++ for the STL.
Example: