## Square-Sum Puzzle

### January 16, 2018

I don’t watch a lot of television, but the YouTube channel *Numberphile* is one of the places I am careful not to miss. *Numberphile* recently had an episode called “The Square-Sum Puzzle” that makes a good exercise:

Rearrange the numbers from 1 to 15 so that any two adjacent numbers must sum to a square number.

Your task is to write a program to solve the *Numberphile* square-sum puzzle. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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: