Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

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

1 Answer 1

up vote 2 down vote accepted

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.

share|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

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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