Mô tả bài toán

Bảng ảo phương kích thước N × N là một ma trận chứa các số nguyên liên tiếp từ 1 đến N² sao cho tổng các phần tử trên mọi hàng, mọi cột và hai đường chéo chính luôn bằng nhau. Khi kích thước N là số lẻ, việc lấp đầy ma trận này có thể được thực hiện tự động bằng một quy tắc dịch chuyển tọa độ chặt chẽ.

Phân tích thuật toán

Thay vì kiểm tra từng điều kiện biên riêng lẻ, quy trình điền số có thể được tối giản nhờ phép toán modulo (chia lấy dư). Các bước thực hiện như sau:

1. Khởi tạo ma trận với toàn bộ giá trị bằng 0.
2. Đặt số 1 tại tọa độ bắt đầu: hàng 0, cột N / 2 (làm tròn xuống).
3. Với mỗi số tiếp theo từ 2 đến N², ta luôn ưu tiên di chuyển theo hướng lên một hàng và sang phải một cột so với vị trí của số vừa điền.
4. Sử dụng phép modulo để xử lý việc vượt khỏi biên bảng: chỉ số hàng âm sẽ quay về hàng cuối cùng, chỉ số cột vượt quá giới hạn sẽ quay về cột đầu tiên.
5. Nếu ô đích theo hướng dịch chuyển đã bị chiếm giữ, ta sẽ bỏ qua quy tắc chéo và thay vào đó di chuyển thẳng xuống dưới một hàng từ vị trí hiện tại.

Định dạng dữ liệu

Đầu vào: Một số nguyên dương lẻ N (1 ≤ N ≤ 39).

Đầu ra: In ra N dòng, mỗi dòng chứa N số nguyên cách nhau bằng một dấu cách, biểu diễn ma trận ảo phương hoàn chỉnh.

Ví dụ minh họa

Nhập: 3

Xuất:

8 1 6
3 5 7
4 9 2

Triển khai mã nguồn

Dưới đây là giải pháp bằng ngôn ngữ C++, sử dụng mảng tĩnh và phép toán modulo để xử lý logic điều hướng tọa độ một cách gọn gàng:

#include <cstdio>

int main() {
    int size;
    if (scanf("%d", &size) != 1) return 0;

    int grid[40][40] = {0};
    int r = 0, c = size / 2;

    for (int val = 1; val <= size * size; ++val) {
        grid[r][c] = val;

        // Tính toán tọa độ tiếp theo theo hướng lên-phải
        int nextR = (r - 1 + size) % size;
        int nextC = (c + 1) % size;

        // Nếu ô dự kiến đã bị chiếm, dịch chuyển thẳng xuống dưới
        if (grid[nextR][nextC] != 0) {
            r = (r + 1) % size;
        } else {
            r = nextR;
            c = nextC;
        }
    }

    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size; ++j) {
            printf("%d%c", grid[i][j], (j == size - 1) ? '\n' : ' ');
        }
    }
    return 0;
}