前言
《算法谜题》中的题目，主要目的在于训练一种思维方式。这篇博客就是整理这本书中一些我认为有意思的题目。
三阶幻方
将1~9这9个不同的数字填入3x3的幻方，使得每行、每列、每条对角线的和相等。
穷举法
第一个格子可填9个数，第二个格子可填8个数，第三个格子可填7个数，以此类推，产生的可能解有9!（9的阶乘）个。对于n阶幻方，可能解数量是 (n^2)! 个。
缩小范围的解法
按以下步骤进行：
- 这个每行、每列、每条对角线的和（称为幻和）等于15：1加到9的总和为45，3行，每行和为15
- 中间格子应该填5：经过中间格子的有4条线（横竖2条，斜的2条），这4条线上数字总和=15*4=45+中间格*3=15*3+中间格*3，即15=中间格*3，因此中间格=5
- 4组数字对(1,9) (2,8) (3,7) (4,6)，2条对角线上应该填偶数对(2,8) (4,6)：因为幻和15为奇数，所以在不经过中间格的4条线上的数字组合必须为2个偶数+1个奇数（2奇+1偶=偶），只有当对角线上都是偶数时才满足这个条件
按照以上步骤，就可以得到三阶幻方的一种答案，其他答案就是由这个答案镜面翻转得到（三阶幻方一共有8个答案）。
楼梯法
世界上已经有很多构造奇数阶幻方的方法了，如楼梯法、杨辉法，其中楼梯法比较适合写程序（楼梯法的介绍可以上网查）。
下面是实现构造k阶奇数幻方的函数：
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
| public static void getSquareOdd(int k) {
int[][] sq = new int[k][k];
int x = 0;
int y = k / 2;
int total = k * k;
for (int i = 1; i <= total; i++) {
sq[x][y] = i;
int nextX = (x - 1 + k) % k;
int nextY = (y + 1) % k;
if (sq[nextX][nextY] > 0) {
x = (x + 1) % k;
} else {
x = nextX;
y = nextY;
}
}
for (int n = 0; n < k; n++) {
for (int m = 0; m < k; m++) {
System.out.print(sq[n][m] + " ");
}
System.out.println();
}
}
|
n皇后问题
将n个皇后放置在n*n的国际象棋棋盘上，其中没有任何两个皇后处于同一行、同一列、同一对角线上。
穷举法
组合公式，从n个对象中选k个对象，不考虑k个对象的排列顺序：C(n,k)
穷举法要考虑的所有可能解的个数，即从n*n个格子中选出n个格子的组合个数C(n^2,n)。当n=4时，C(16,4)=1820，因此用穷举法解4皇后问题需要遍历1820个组合。
回溯法
回溯法是对穷举法的一种改进，它采用走一步添加一个组件的方式，同时评估这一步中添加的组件是否符合题目要求，若不符合就返回上一步（回溯），从上一步重新开始考虑其他走法，若上一步往下的所有路都走不通，则再往上回溯；若符合就从这一步继续往下走，直到得出答案。
因此，回溯法需要遍历的可能解的数量会比穷举法少，当n=4时，考虑皇后必须放置在不同行和不同列，即第1个皇后有4种放法，第2个有3种，以此类推，可能解的数量为4!=24。
代码实现
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
| public class Main {
public static int n = 4;
public static int[] result = new int[n];
public static void main(String[] args) {
int r = 0;
findColumn(r);
}
public static boolean isValid(int r, int c) {
for (int i = 0; i < r; i++) {
if ((result[i] == c) || (Math.abs(r - i) == Math.abs(c - result[i]))) {
System.out.println("当前坐标：(" + r + "," + c + ")和已有位置(" + i + "," + result[i] + ")冲突");
return false;
}
}
return true;
}
public static void findColumn(int r) {
if (r == n) {
System.out.println("result: ");
for (int i = 0; i < n; i++) {
System.out.println(result[i]);
}
System.out.println("----------------------");
return;
}
for (int c = 0; c < n; c++) {
System.out.println("当前坐标：(" + r + "," + c + ")");
if (isValid(r, c)) {
System.out.println("当前坐标：(" + r + "," + c + ")填1");
result[r] = c;
findColumn(r + 1);
}
}
}
}
|
上面的代码时间复杂度为O(n^n)，即n的n次方，因为有n次递归，每次递归中遍历n列。空间复杂度为O(n)，因为用到了result[n]数组。
位运算改进版实现
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
| public class Main {
public static int n = 4;
public static int count = 0;
public static void main(String[] args) {
find(0, 0, 0);
System.out.println(count);
}
public static void find(int row, int ld, int rd) {
int pos, p;
int all1 = (1 << n) - 1;
if (row != all1) {
pos = all1 & (~(row | ld | rd));
System.out.println("可放的位置：" + Integer.toBinaryString(pos));
while (pos != 0) {
p = pos & (~pos + 1);
pos = pos - p;
find(row | p, (ld | p) << 1, (rd | p) >> 1);
}
} else {
count++;
}
}
}
|
n>3时的通用解法
因为n=1有一个解，n=2和n=3无解，所以只研究n>3的通用解法。
