Magic Square of Odd Order

Problem

Given a positive odd integer n, generate a magic square of order n (an n x n grid) that contains the integers 1..n^2 exactly once, such that every row, every column, and both main diagonals sum to the same value — the magic constant M.

Because the square uses each integer from 1 to n^2 exactly once, M depends only on n and equals:

M = n * (n*n + 1) / 2

Examples

Example 1

1
2
3
4
5
6


Input: n = 3
Output: a 3x3 magic square (one valid solution):
8 1 6
3 5 7
4 9 2
Explanation: Each row/column/diagonal sums to 15 (M = 3*(9+1)/2 = 15).

Example 2

1
2
3
4
5
6
7
8


Input: n = 5
Output: a 5x5 magic square (one valid solution):
17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9
Explanation: Each row/column/diagonal sums to 65 (M = 5*(25+1)/2 = 65).

Notes

This file focuses on odd-order magic squares (n % 2 == 1) and presents the classical Siamese (de la Loubère) method for constructing them. Doubly-even (n % 4 == 0) and singly-even (n % 4 == 2) constructions use different techniques and are covered in related problems listed above.
The magic constant M is always an integer for integer n because n*(n^2+1) is even for every integer n.

Solution

For odd n, the classical and simple method is the Siamese (de la Loubère) algorithm. It constructs the magic square by placing successive integers while moving in a fixed pattern (up and right) and wrapping around the grid, with a single rule to resolve collisions.

Method 1 — Siamese (de la Loubère) method

Intuition

Did you find any pattern in which the numbers are stored? In this Siamese variant the first number (1) is placed at (i = n/2, j = n-1). Each subsequent number is placed by moving one row up and one column to the right (treating rows and columns as circular so they wrap around).

Two special corrections ensure correctness:

If the tentative move goes off both the top (i == -1) and beyond the right edge (j == n), reset to (0, n-2).
If the tentative target cell is already occupied, instead move one row down from the previous position and two columns left from the tentative position (equivalently: i += 1; j -= 2) and place the same number there.

These simple rules ensure every cell is filled exactly once and produce a valid odd-order magic square.

Approach

Follow these steps exactly:

Create an n x n grid mat initialized to zeros. Set i = n/2, j = n - 1, and num = 1.
While num <= n*n:
- Tentatively set i = i - 1 and j = j + 1 (the up-right move).
- If i == -1 && j == n then set i = 0 and j = n - 2.
- Else if only one index is out of range, wrap it: if i < 0 set i = n - 1; if j == n set j = 0.
- If mat[i][j] != 0 (cell already filled), undo the tentative move and set i = i + 1, j = j - 2 and try placing num there (do not increment num).
- Otherwise set mat[i][j] = num and increment num.
When finished, return mat.

Edge cases / notes:

This variant starts at (n/2, n-1); it’s equivalent up to rotation/reflection to the common (0, n//2) start.
Works for all odd n (3,5,7,…). Time and space are both O(n^2).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> oddMagicSquare(int n) {
        vector<vector<int>> mat(n, vector<int>(n, 0));
        int i = n / 2;
        int j = n - 1;
        int num = 1;

        while (num <= n * n) {
            if (i == -1 && j == n) {
                j = n - 2;
                i = 0;
            } else {
                if (j == n) j = 0;
                if (i < 0) i = n - 1;
            }

            if (mat[i][j] != 0) {
                j -= 2;
                i += 1;
                continue;
            } else {
                mat[i][j] = num++;
            }

            j++;
            i--;
        }

        return mat;
    }
};

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


import java.util.Arrays;

public class Solution {
    public int[][] oddMagicSquare(int n) {
        int[][] mat = new int[n][n];

        int i = n / 2;
        int j = n - 1;

        int num = 1;
        while (num <= n * n) {
            // If row becomes -1 and column becomes n, wrap to (0, n-2)
            if (i == -1 && j == n) {
                j = n - 2;
                i = 0;
            } else {
                // wrap single out-of-bounds
                if (j == n) j = 0;
                if (i < 0) i = n - 1;
            }

            // If the cell is already filled, move left two columns and down one row
            if (mat[i][j] != 0) {
                j -= 2;
                i += 1;
                continue;
            } else {
                mat[i][j] = num++;
            }

            // move to next candidate: up one row and right one column
            j++;
            i--;
        }

        return mat;
    }
}

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


class Solution:
    def oddMagicSquare(self, n: int) -> list[list[int]]:
        mat = [[0] * n for _ in range(n)]
        i = n // 2
        j = n - 1
        num = 1

        while num <= n * n:
            if i == -1 and j == n:
                j = n - 2
                i = 0
            else:
                if j == n:
                    j = 0
                if i < 0:
                    i = n - 1

            if mat[i][j] != 0:
                j -= 2
                i += 1
                continue
            else:
                mat[i][j] = num
                num += 1

            j += 1
            i -= 1

        return mat

Complexity

⏰ Time complexity: O(n^2), because we fill the n x n grid once and then visit each cell once more to complement selected positions.
🧺 Space complexity: O(n^2), to store the n x n magic square.

Problem#

Examples#

Example 1#

Example 2#

Solution#

Method 1 — Siamese (de la Loubère) method#

Intuition#

Approach#

Code#

Complexity#