2

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

Improve this question
11
  • 1
    i'm curious: why are the cells arranged with two bumps but not in a horizontal straight line?
    – mauris
    Commented Nov 4, 2012 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
    Commented Nov 4, 2012 at 17:11
  • @mauris - I'm guessing it's because the cells better fit the A4 page layout this way.
    – syntagma
    Commented Nov 4, 2012 at 17:13
  • @Asaf, I know it can be done using BF but I'm looking for something more sophisticated.
    – syntagma
    Commented Nov 4, 2012 at 17:14
  • 1
    20 + 21 = 41, that's not square. He could use 5 or 16 there.
    – DeadMG
    Commented Nov 5, 2012 at 12:00

1 Answer 1

Reset to default
2

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
1
  • 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
    Commented Nov 5, 2012 at 23:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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