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).
11
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.
1