Magic Square of Doubly Even Order

Problem

Given an integer n (where n % 4 == 0), construct a normal magic square of order n that contains the integers 1..n^2 exactly once, such that every row, every column, and the two main diagonals sum to the same magic constant M = n * (n^2 + 1) / 2.

Examples

Example 1

Input: n = 4
Output: a 4x4 magic square such as:
16  2  3 13
 5 11 10  8
 9  7  6 12
 4 14 15  1
Explanation: Each row/column/diagonal sums to 34 (M = 4*(16+1)/2 = 34).

Example 2

Input: n = 8
Output: 
64 63 3 4 5 6 58 57
56 55 11 12 13 14 50 49
17 18 46 45 44 43 23 24
25 26 38 37 36 35 31 32
33 34 30 29 28 27 39 40
41 42 22 21 20 19 47 48
16 15 51 52 53 54 10 9
8 7 59 60 61 62 2 1

Notes

• This file focuses on doubly-even (4k) orders. Singly-even (4k+2) and odd-order (2k+1) constructions use different techniques and are listed under related problems.
• For n not divisible by 4, Method 1 below is not applicable; use other known constructions instead.

Solution

We show a standard and efficient method for doubly-even (n % 4 == 0) magic squares based on complementing selected cells.

Method 1 — Complementation

Intuition

Fill the square left-to-right, top-to-bottom with 1..n^2. Certain positions form a repeating 4x4 pattern; for those positions we replace the value x with its complement n*n + 1 - x. Complementing in this pattern produces the required symmetric distribution so that every row, column and diagonal sums to the magic constant.

Approach

1. Create an n x n matrix arr and fill it with arr[i][j] = n*i + j + 1 for 0 <= i,j < n.
2. For every cell (i, j), compute r = i % 4 and c = j % 4.
3. If (r == c) || (r + c == 3) then replace arr[i][j] with n*n + 1 - arr[i][j].
   • This condition marks the cells that must be complemented in every 4x4 block.
4. Return arr as the magic square.

Edge cases / notes:

• The method requires n % 4 == 0. If n is not divisible by 4, this method does not produce a valid magic square.
• The algorithm is deterministic and produces the classical doubly-even magic square pattern.

Dry run (n = 4)

We illustrate Method 1 on n = 4. Start with the filled matrix (left-to-right, top-to-bottom):

The complement rule flips values in cells that match the 4x4 pattern (positions where r==c or r+c==3). We'll show the changes step by step; complemented cells are shown in red.

1. Top-left cell (position (0,0)) is complemented: replace 1 with 16 (since n*n+1 - 1 = 16):

1. Top-right cell (position (0,3)) is complemented: replace 4 with 13:

1. Bottom-left cell (position (3,0)) is complemented: replace 13 with 4:

1. Bottom-right cell (position (3,3)) is complemented: replace 16 with 1:

1. Now complement the central 2x2 block positions that match the pattern (positions (1,1), (1,2), (2,1), (2,2)). Each value x is replaced by 17 - x:

This final matrix is the standard 4x4 doubly-even magic square (each row, column and diagonal sums to 34).

Code

C++

// Produces a doubly-even (n % 4 == 0) magic square.
#include <vector>
using namespace std;

class Solution {
 public:
    static vector<vector<int>> generate(int n) {
        vector<vector<int>> ans(n, vector<int>(n));
        int cnt = 1;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                ans[i][j] = cnt++;

        int total = n * n + 1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                int r = i % 4, c = j % 4;
                if (r == c || r + c == 3) ans[i][j] = total - ans[i][j];
            }
        }
        return ans;
    }
};

Go

package main

// generate returns an n x n magic square when n%4==0
func Generate(n int) [][]int {
    ans := make([][]int, n)
    for i := 0; i < n; i++ {
        ans[i] = make([]int, n)
    }

    cnt := 1
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            ans[i][j] = cnt
            cnt++
        }
    }

    total := n*n + 1
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            r := i % 4
            c := j % 4
            if r == c || r+c == 3 {
                ans[i][j] = total - ans[i][j]
            }
        }
    }
    return ans
}

Java

class Solution {
    public static int[][] generate(int n) {
        int[][] ans = new int[n][n];
        int cnt = 1;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                ans[i][j] = cnt++;

        int total = n * n + 1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                int r = i % 4, c = j % 4;
                if (r == c || r + c == 3) ans[i][j] = total - ans[i][j];
            }
        }
        return ans;
    }
}

Python

class Solution:
        @staticmethod
        def generate(n: int) -> list[list[int]]:
                ans = [[0] * n for _ in range(n)]
                cnt = 1
                for i in range(n):
                        for j in range(n):
                                ans[i][j] = cnt
                                cnt += 1

                total = n * n + 1
                for i in range(n):
                        for j in range(n):
                                r, c = i % 4, j % 4
                                if r == c or r + c == 3:
                                        ans[i][j] = total - ans[i][j]
                return ans

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.