如何用 C 语言求解 3×3 幻方谜题 Python
陈莎拉
什么是幻方？
幻方是一种数字排列特殊的方阵。它的数值排列使得每一行、每一列以及两条主对角线上的数字之和都保持不变。幻方是一种简单的逻辑谜题，常用于趣味数学游戏中。
魔方示例：
上图所示为一个 3 阶幻方。每条对角线、每行和每列的和都等于 15。下一节将解释这个常数总和是如何产生的。
幻方是如何运作的
n阶幻方是一个n×n矩阵，其中包含n²个正整数。矩阵的行数或列数称为矩阵的阶数。
典型的幻方谜题具有奇数阶，并使用 1 到 n² 的整数。由于每一行、每一列和每一条对角线上的数字之和都必须相同，因此这个值被称为幻和或幻常数。该常数仅取决于 n。n 阶幻和的公式为：
考虑一个 3 阶幻方。那么它的幻和为：
这个公式解释了其中的算术原理，但这个谜题有着悠久的文化历史，也正是这段历史赋予了它令人难忘的名字。
为什么它们被称为魔法？
古代数学家对有趣的数字组合着迷，幻方就是其中之一。最早的证据可以追溯到公元前190年左右的中国。
研究表明，古代日本、印度和阿拉伯地区都存在幻方谜题。传说将这些图案与魔法世界联系起来，这个名称也由此而来。除了民间传说之外，数学家们也定义了正式的范畴来区分不同的幻方。
魔方类型
数学中存在几种幻方变体：
- 普通魔方： 包含前 n² 个自然数。
- 半魔方： 只有行和列的总和等于这个神奇的常数。
- 简单魔方： 行数、列数和两条主对角线的总和等于神奇常数。
- 最完美魔方： 这是一个普通的幻方，但有两个额外的性质。矩阵中每个 2×2 子方格的和都等于 2(n²+1)，并且相距 n/2 个单元格的任意两个数字之和都等于 n²+1。
根据其他属性，还有更多分类。本教程中凡未加限定地使用“幻方”一词，均指奇数阶、正规的简单幻方。
生成幻方的算法
生成奇数阶幻方的经典算法，称为孪生法，如下：
- 第一个数字（1）存储在位置（n/2，n-1），其中第一个坐标是行索引，第二个坐标是列索引。在后续步骤中，将此位置称为（x，y）。
- 下一个数字放置在 (x-1, y+1) 处。如果该位置无效，则应用以下规则：
- 如果行索引为 -1，则将其回绕到 n-1。如果列索引为 n，则将其回绕到 0。
- 如果计算出的位置已经包含一个数字，则将行加 1，将列减 2。
- 如果行是 -1，列是 n，则新位置为 (0, n-2)。
注意： 该算法仅生成奇数阶的有效幻方。结果是一个包含前 n² 个自然数的普通幻方。对于同一个 n，可能存在多个有效解。
通过一个使用数字 1 到 9 的 3 阶小例子，规则会变得更加清晰。
它在 3x3 方格上的工作原理
应用 算法 以上步骤如下：
步骤1） 第一个数字（1）放置在（3/2，3-1）或（1，2）处。在后续步骤中，设置 x = 1 和 y = 2。
步骤2） 其余数字的位置计算如下。
2号的位置：
下一个数字应该填入 (x-1, y+1) 或 (0, 3)，但这不是有效位置。根据规则 (a)，该列会循环到 0，得到 (0, 0)。令 x = 0，y = 0。
3号的位置：
数字 3 应该位于 (x-1, y+1) 或 (-1, 1)，但这不是有效位置。根据规则 (a)，该行会循环到 n-1（即 2）。因此，数字 3 应位于 (2, 1)。令 x = 2，y = 1。
4号的位置：
数字 4 应该位于 (x-1, y+1) 或 (1, 2)，这是有效的，但其中已经包含 1。根据规则 (b)，新位置是 (1+1, 2-2) 或 (2, 0)。令 x = 2，y = 0。
5号的位置：
数字 5 应该位于 (x-1, y+1) 或 (1, 1)，这是一个有效的空位。令 x = 1，y = 1。
6号的位置：
数字 6 应该位于 (x-1, y+1) 或 (0, 2)，这是一个有效的空位。令 x = 0，y = 2。
7号的位置：
数字 7 应该位于 (x-1, y+1) 或 (-1, 3)，但这不符合规则。根据规则 (c)，新位置为 (0, n-2) 或 (0, 1)。令 x = 0，y = 1。
8号的位置：
第 8 个数字应该位于 (x-1, y+1) 或 (-1, 2)，但这不符合规则。根据规则 (a)，该行会循环到第 2 个数字，得到 (2, 2)。令 x = 2，y = 2。
9号的位置：
数字 9 应该位于 (x-1, y+1) 或 (1, 3)，但这不符合规则。根据规则 (a)，该列会循环到 0，因此结果为 (1, 0)。
每填入一个单元格，同样的逻辑就可以直接转换成伪代码。
魔方伪代码
Begin Declare an array of size n*n Initialize the array to 0 Set row = n/2 Set column = n-1 For all number i: from 1 to n*n If the row = -1 and column = n row = 0 column = n-2 Else If row = -1 row = n-1 If column = n column = 0 If the position already contains a number decrement column by 2 increment row by 1 continue until the position is not 0 Else put the number i into the calculated position increment i Increment column value Decrement row value End
伪代码可以直接映射到编译型语言和解释型语言，如下所示。 C++ 和 Python.
C++ Code 魔方
输入：
/* A C/C++ program for generating odd order magic squares */ #include <bits/stdc++.h> using namespace std; void GenerateMagicSquare(int n) { int magic[n][n]; //initializing the array for(int i=0; i<n; i++) for(int j=0; j<n; j++) magic[i][j] = 0; //setting row and column value int i = n / 2; int j = n - 1; for (int k = 1; k <= n * n;) { //checking condition (c) if (i == -1 && j == n) { j = n - 2; i = 0; } else { //checking condition (a) if (j == n) j = 0; if (i < 0) i = n - 1; } //checking condition (b) if (magic[i][j]) { j -= 2; i++; continue; } else { //placing the number into the array magic[i][j] = k; k++; } //for the next number setting (i-1, j+1) j++; i--; } //printing the matrix for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) cout << magic[i][j] << " "; cout << endl; } } int main() { //This code works for only odd numbers int n = 7; cout<<"The magic sum is " << n*(n*n+1)/2 <<endl; GenerateMagicSquare(n); return 0; }
示例输出：
The magic sum is 175 20 12 4 45 37 29 28 11 3 44 36 35 27 19 2 43 42 34 26 18 10 49 41 33 25 17 9 1 40 32 24 16 8 7 48 31 23 15 14 6 47 39 22 21 13 5 46 38 30
此 Python 以下版本使用相同的行和列规则。
Python Code 魔方
def GenerateMagicSquare(n): #initializing the array magic = [[0 for x in range(n)] for y in range(n)] #setting row and column value i = n // 2 j = n - 1 k = 1 while k <= (n * n): #checking condition (c) if i == -1 and j == n: j = n - 2 i = 0 else: #checking condition (a) if j == n: j = 0 if i < 0: i = n - 1 #checking conditon (b) if magic[i][j]: j = j - 2 i = i + 1 continue else: #placing the number into the array magic[i][j] = k k = k + 1 #for the next number setting (i-1, j+1) j = j + 1 i = i - 1 #printing the matrix for i in range(0, n): for j in range(0, n): print('%2d ' % (magic[i][j]),end='') if j == n - 1: print() #This code works for only odd numbers n = 7 print("The magic sum is ",n * (n * n + 1) // 2, "\n") GenerateMagicSquare(n)
示例输出：
The magic sum is 175 20 12 4 45 37 29 28 11 3 44 36 35 27 19 2 43 42 34 26 18 10 49 41 33 25 17 9 1 40 32 24 16 8 7 48 31 23 15 14 6 47 39 22 21 13 5 46 38 30
两种实现方式的行为完全相同，因此很容易比较它们的成本。
复杂度分析
- 空间复杂度： 幻方存储在 n×n 数组中，因此空间复杂度为 O(n²)。
- 时间复杂度： 生成器使用两个嵌套循环。外层循环运行 n 次，内层循环也运行 n 次，因此总时间复杂度为 O(n²)。
