# Filling array with numbers from given range so that sum of adjacent numbers is square number

Problem: Fill all the cells using distinct numbers from <1,25> set, so that sum of two adjacent cells is a square number.

(source: http://grymat.im.pwr.wroc.pl/etap1/zad1etp1213.pdf; numbers 20 and 13 have been given)

I've already solved this problem analytically and now I would like to approach it using an algorithm.

I would like to know how should I approach these kind of problems in general (not a solution, just a point for me to start).

-
i'm curious: why are the cells arranged with two bumps but not in a horizontal straight line? – mauris Nov 4 '12 at 16:45
When in doubt just bruteforce it. Try every combination and test that it satisfies your condition. You could speed things up by testing adjacent cells as you produce the combinations. – Asaf Nov 4 '12 at 17:11
@mauris - I'm guessing it's because the cells better fit the A4 page layout this way. – ΔλЛ Nov 4 '12 at 17:13
@Asaf, I know it can be done using BF but I'm looking for something more sophisticated. – ΔλЛ Nov 4 '12 at 17:14
20 + 21 = 41, that's not square. He could use 5 or 16 there. – DeadMG Nov 5 '12 at 12:00

The key is to recognize that this is actually another problem- the Travelling Salesman.

Each number between 1-25 is a vertex. If x + y = square, then there is an edge between x and y. For n numbers, you can build this graph in O(n^2). Now visit each node so that no node is visited more than once. This is NP-Complete and the essence of TSP.

Once you recognize this variant, you can start by adapting solutions to TSP to your specific instance of it.

-
TSP requires you to return to the original point, this doesn't. TSP is equivalent to finding a Hamiltonian cycle, this is equivalent to finding a Hamiltonian path (of course the difference is really just superficial). – Austin Nov 5 '12 at 23:50