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

enter image description here

(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).

  • 1
    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. – syntagma Nov 4 '12 at 17:13
  • @Asaf, I know it can be done using BF but I'm looking for something more sophisticated. – syntagma Nov 4 '12 at 17:14
  • 1
    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.

| improve this answer | |
  • 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.