MarioYC's blog

5 x 5 Magic Square
By MarioYC, 14 years ago, In English

I've come across the following task from z-trening (http://www.z-trening.com/tasks.php?show_task=5000000148). First I thought it would be easy with backtracking since sides where small. But I'm getting TLE in two cases, and when trying to solve a 5x5 square with all its squares empty it takes forever to solve it.

Is there a more efficient way to solve it or any useful heuristic?


This code passed 17/20 cases: http://pastie.org/2073017

This code passed 16/20 cases: http://pastie.org/2073028

AC solution: http://pastie.org/2073682

  • Vote: I like it
  • +5
  • Vote: I do not like it

14 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You can google an algo for constructing magic square of any size in O(N^2).

For this problem - since part of the square may be filled, it seems that bruteforce is the only possible way. Try to trim nodes which are definitely not solutions for your problem as early as possible.
For example, you know sum of the numbers in any row or column ("magic number") - use this information to detect whether it is necessary to continue, or it worth to stop at this branch and go back (if you completely filled a row/column and sum of the numbers in it doesn't conicide with the magic number). And don't forget about diagonal sums - this narrows search space further.
Also, for empty squares you can just precalculate the answers.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
@MarioYC: Please give link to your TLE code, So that anyone can see what method actually gave tle. (backtracking is not conclusive )
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Now I've posted to approaches I tried, in the first one I go from the top to the bottom and from left to right choosing a number for every position and check all necessary sums. In the second one, I also check the sums, but I put the greatest number possible.
→ Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Just for fun I solved the problem with the abovementioned approach (0.675 sec. for all tests). The only thing you should add to get AC is intelligent traverse order. For example, suppose you're given test like:
    0 0 0 X 0
    X X X 0 X
    0 0 0 X 0
    0 0 0 X 0
    0 0 0 X 0
    Of course, not to get stuck, first of all you should find the number for the cell (2,4), and only then bruteforce all the rest. Good test to test your solution is:
    5
    1 0 0 0 0
    0 0 0 0 0
    0 0 2 0 0
    0 0 0 0 0
    0 0 0 0 13
    Possible answer is:
    1 9 22 16 17 
    14 24 12 4 11 
    20 10 2 15 18 
    7 19 8 25 6 
    23 3 21 5 13 

    → Reply