UVa 10775

From Algorithmist
Jump to navigation Jump to search

10775 - Mystical Matrix[edit]

Summary[edit]

There are many ways to do this problem. One method is to write a naive solution for small N and then figure out a pattern.

Explanation[edit]

There are no solutions for even N. Why? Try to figure out row/column sums. The N = 3, the 3x3 matrix is simply the given magic square. You can use a brute force way to generate it, and find the patterns.

Another way is the following analytical method. Given N, we can first put the 3x3 magic square and the subsequent magic squares side by side: (Shown for N = 9)

8 3 4 17 12 13 26 21 22
1 5 9 10 14 18 19 23 27
6 7 2 15 16 11 24 25 20

Note that the column sums are not the same, but the row sums already is. This observation allow us to swap elements of the same row freely - the row sum will remain the same.

Since we will try to match block to block, we can visualize it as such:

1 2 3
1 2 3
1 2 3

and thus, trying to get the balanced:

1 2 3
2 3 1
3 1 2

Notes[edit]

  • There are more than one solution for each input.

Input[edit]

3
6
9
12
15
0

Output[edit]

8 3 4
1 5 9
6 7 2
IMPOSSIBLE
8 3 4 17 12 13 26 21 22
10 14 18 19 23 27 1 5 9
24 25 20 6 7 2 15 16 11
IMPOSSIBLE
8 3 4 17 12 13 26 21 22 35 30 31 44 39 40
19 23 27 28 32 36 37 41 45 1 5 9 10 14 18
42 43 38 24 25 20 6 7 2 33 34 29 15 16 11