玩玩幻方

那些年玩过的数字游戏

曾有一段时间，我疯狂的解幻方。
从三阶开始，一阶一阶慢慢往上解。
那时候甚至都不知道这个叫做幻方，反正是将1到n的平方填入到正方形的宫格中，
横竖以及对角线都相等。
当时的我没有任何资料，就随着自己的性子，一步步慢慢研究。
然后自己总结出n阶幻方的和公式，n阶幻方的解法，n阶幻方的小规律。
然而跟现在网上看到的各种规律完全不同。
那时，最简单的是3阶幻方，甚至有时候数学考试都会有这个题目。
直接把五填在中间，然后随便测试着摆一摆其它成对的数字，很容易算出来。
就这样，我找上了四阶幻方，四阶幻方是偶数阶，跟奇数阶又不同，
我还是偶然一次知道了要将1-16中间四个数字摆到中间四个格子，当然如何摆是有点小技巧的。
然后是五阶，那时，我灵机一动，直接把三阶幻方的解放到了五阶幻方的中间，
然后全部数字加上一个值，简单点说就是把1到9变成1-25中间的九个数字，这样，我要解的就只有最外一圈了，
然后最外一圈的数字慢慢试（都是成对的，例如1和25,2和24…）
最后我五阶解成功了，真是佩服自己的耐心。
最后六阶，七阶，八阶，九阶，十阶，是的，最终我解到了十阶，
连我自己都佩服当时的自己，最后我在一个笔记本上面，画下了所有的解。
我现在都还记得，那是我初中最喜欢的一本笔记本，
为了不让笔记本封面变脏，我买了透明胶布，手指宽的那种，然后一条一条，慢慢的将封面粘起来，
用了很久，当时我满意极了，有时候自恋的默默笔记本的封面，有点滑，
但是两个胶布之间还有一个小痕，摸起来感觉很不错。
我还记得首页那里我画了一个超大的龙珠贝吉塔图，那是我根据一张卡片，慢慢按照比例放大，然后描到笔记本上，
反正就摊开笔记本两页那么大。
嗯，好像话题偏了。
回到幻方，我一共十阶的幻方解，但是我只画了两个方格图，一个奇数阶幻方，一个偶数阶幻方，
但是，估计也只有我看的懂，因为从内到外，除了三阶和四阶是全解，其它一层层都只是最外层的解，
简单点说，两个图包含了3到10阶的幻方的所有解。
可惜，现在都成为回忆了。

如果用算法解幻方

网上百度了一下，那些算法好像都是根据幻方的规律来解的，
也许你很奇怪别人如何随便就可以解出上百阶的幻方，
我只能说，如果知道真相，你也可以做到。
至于具体的，还是贴个百度百科的链接吧：
关于幻方的由来和规律
是不是很简单，然后前几天，我不是说要研究一下回溯法，然后我用回溯法写了一个解幻方的算法。
三阶四阶都正常很快解出来了，五阶居然挂了，估计我写完这份博客都还没解出来。
好吧，是我天真的，五阶的计算量太大，估计已经陷入死循环，毕竟回溯法这种探路算法，
还是有点坑啊，也不知道自己是不是写的有点问题。

回溯算法解幻方代码

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
package test;
import java.util.Scanner;
public class MagicSquare {
	/** 幻方总数 */
	static int allNum = 0;
	/** 幻方阶数 */
	static int n = 0;
	/** 幻方最大下角坐标 */
	static int m = 0;
	/** 幻方行列对角和 */
	static int count = 0;
	
	/**
	 * 初始化幻方以及相关参数
	 * @return 
	 */
	public int[][] initMgSq(){
		n = (int) Math.sqrt(allNum);
		count = n*(n*n+1)/2;
		m = n-1;
		int[][] mgSq = new int[n][n]; 
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				mgSq[i][j] = 0;
			}
		}
		System.out.println("阶数："+n);
		System.out.println("行列对角和："+count);
		return mgSq;
	}
	/**
	 * 解幻方，并打印结果
	 */
	public void solve(int[][] mgSq) {
		if (this.solve(mgSq, 0, 0)) {
			printArray(mgSq);
		} else {
			System.out.println("没有找到相应的解法");
		}
	}
	/**
	 * 解幻方
	 */
	private boolean solve(int[][] mgSq, int row, int column) {
		/**
		 * 结束条件
		 */
		if (row == m && column == n) {
			return true;
		}
		/**
		 * 如果column == n, 那么需要换行，也就需要更新column和row的值.
		 */
		if (column == n) {
			column = 0;
			row++;
		}
		/**
		 * 如果当前位置上mgSq[row][column]的值为0, 尝试在1~allNum的数字中选择合适的数字
		 */
		for (int num = 1; num <= allNum; num++) {
			if (isSafe(mgSq, row, column, num)) {
				mgSq[row][column] = num;
				if (solve(mgSq, row, column + 1)) {
					return true;
				}
				mgSq[row][column] = 0;
			}
		}
		/**
		 * 回溯重置
		 */
		mgSq[row][column] = 0;
		return false;
	}
	
	/**
	 * 该数字是否已使用
	 */
	private boolean isNumSafe(int[][] mgSq, int value) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if(mgSq[i][j] == value){
					return false;
				}
			}
		}
		return true;
	}
	
	/**
	 * 某一行放置数据是否可以
	 */
	private boolean isRowSafe(int[][] mgSq, int row, int value) {
		int rowCount = value;
		for(int i : mgSq[row]){
			rowCount += i;
		}
		// 如果是行最后一个 ,判断这一行的和是否正确
		if(mgSq[row][m-1] != 0){
			if(rowCount != count){
				return false;
			}
		}else{
			if(rowCount >= count){
				return false;
			}
		}
		return true;
	}
	/**
	 * 某一列放置数据是否可以
	 */
	private boolean isColumnSafe(int[][] mgSq, int column, int value) {
		int columnCount = value;
		for(int i=0;i<n;i++){
			columnCount += mgSq[i][column];
		}
		// 如果是行最后一个 ,判断这一列的和是否正确
		if(mgSq[m-1][column] != 0){
			if(columnCount != count){
				return false;
			}
		}else{
			if(columnCount >= count){
				return false;
			}
		}
		return true;
	}
	/**
	 * 对角是否可以放该数据
	 */
	private boolean isOppositeSafe(int[][] mgSq, int row, int column, int value) {
		//左右对角线和
		int aCount = 0;//左
		int bCount = 0;//右
		if(row == column || (row + column) == m){
			//求对角线值
			for(int i=0;i<n;i++){
				aCount += mgSq[m-i][i];
				bCount += mgSq[i][i];
			}
			//最后一行
			if(row == m){
				if(column == 0 && (aCount + value) != count){
					return false;
				}else if(column == m && (bCount + value) != count){
					return false;
				}
			}else if(row == column && (row + column) == m){//中间点,偶数阶幻方无该坐标
				if((aCount + value) >= count || (bCount + value) >= count){
					return false;
				}
			}else{
				if(row == column){
					if((bCount + value) >= count){
						return false;
					}
				}else{
					if((aCount + value) >= count){
						return false;
					}
				}
			}
		}
		return true;
	}
	/**
	 * 在指定位置是否可以放置数据
	 */
	private boolean isSafe(int[][] mgSq, int row, int column, int value) {
		if(this.isNumSafe(mgSq, value)){
			if(this.isRowSafe(mgSq, row, value)){
				if(this.isColumnSafe(mgSq, column, value)){
					if(this.isOppositeSafe(mgSq, row, column, value)){
						return true;
					}
				}
			}
		}
		return false;
	}
	/**
	 * 打印二维数组到控制台
	 */
	private void printArray(int[][] mgSq) {
		System.out.println("------------------------");
		for (int i = 0; i < n; i++) {
			System.out.print("|");
			for (int j = 0; j < n; j++) {
				System.out.print(" ");
				System.out.print(mgSq[i][j]+" ");
				if(mgSq[i][j]<10){
					System.out.print(" ");
				}
				System.out.print("|");
			}
			System.out.println("");
		}
		System.out.println("------------------------");
	}
	
	/**
	 * 测试
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		allNum = sc.nextInt();
		double d = Math.sqrt(allNum);
		String dStr = String.valueOf(d);
		dStr = dStr.substring(dStr.indexOf(".") +1);
		if(allNum < 9 || !dStr.equals("0")){
			System.out.println("请输入正确的幻方数字，例如：9,16...");
		}else{
			MagicSquare example = new MagicSquare();
			int[][] mgSq = example.initMgSq();
			example.solve(mgSq);
		}
	}
}

寄语

我俯身，捧起脑海中记忆的浪花，藏进了心中