本文主要描述思路,Java入门初学者,代码比较简单。
网上的八皇后解法有很多种,这是我自己设计出来的一种算法,因此不能算是在水文章。
首先,我们思考使用二维数组表示一个棋盘。我们用0来表示这个棋盘上皇后攻击不到的格子,用1来表示皇后可以攻击到的格子。因此在未放置皇后前,我们先用64个0来初始化我们的棋盘。
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
紧接着来思考皇后的摆放顺序:我们从右上开始(即从0,0开始放置第一个皇后),如果可以摆放,则尝试着把下一个皇后放置在下一行上,因为第一行已经放置过一个皇后,除非修改第一个皇后的位置,否则第一行只能放置一个皇后了。
在摆放完第一个皇后后,我们需要更新我们的棋盘布局,把所有的可以被皇后攻击到的格子修改为1,以方便后续摆放皇后时我们的程序可以做出正确的判断。
大体思路就是这样,稍微思考一下程序的运行流程,想到了一个棘手的问题:如果我们只是用1来表示会被攻击的方格,一旦在程序尝试中找不到可行解时,回溯会相当的麻烦——我们不能知道一个1的方格究竟是被哪一个皇后或者哪几个皇后所共同攻击的区域,我们不能简单的逆向把上一个皇后的攻击区域贸修改为0,因为这些0的区域可能依然在其他皇后的攻击范围内。
为了解决这个矛盾,需要重新设计棋盘:我们首先用64个-1来初始化这个棋盘数组:之后,我们对放置在第一行(在数组中,是第0行)的皇后可以攻击的区域用0进行填充,紧接着,在接下来放置在第二行的皇后可以攻击的区域用1填充,我们始终只将以前从未被攻击的格子(-1)修改为我们当前放的这个皇后的特定值(0,1,2,3...),而对于已经在其他皇后可以攻击范围的格子,我们保持它的非-1的值。这样,如果想要回溯,例如取消掉我们放置在第3行的皇后可以攻击的区域,只需对棋盘进行一次遍历,将所有值为2的格子修改为-1即可。
我们希望棋盘图可以在运行中呈现以下效果:
0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1
0 1 0 1 -1 -1 -1 -1
0 -1 1 0 1 -1 -1 -1
0 -1 1 -1 0 1 -1 -1
0 -1 1 -1 -1 0 1 -1
0 -1 1 -1 -1 -1 0 1
0 -1 1 -1 -1 -1 -1 0
我们写出一个refresh()
方法,以便回溯时使用:
public void refresh(int a) { // which a is the origin value to refresh.
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= m; j++) {
if (table[i][j] == a) table[i][j] = -1;
}
}
}
现在我们根据大体思路写出一个用于更新棋盘的makeFlag()
方法,由于我们打算自棋盘右上向左下进行搜索,先下后右,并且我们一旦发现任何的放置皇后的可能,就立即放置皇后然后不再考虑这一行。所以对于棋盘的更新我们只要更新新放置的皇后的垂直方向、西南方向和东南方向即可。更新时我们要注意循环设置时不能超出数组的边界。
public void makeFlagChange(int y, int x, int a) { //y,x is the real (x,y) value, and the a is flag value.
if (table[y][x] == -1) table[y][x] = a;
}
public void makeFlag(int y, int x) { // make flags to let next function know the process.
table[y][x] = y;
for (int i = 1; y + i <= m; i++) makeFlagChange(y + i, x, y);
for (int i = 1; (y + i <= m) && (x + i <= m); i++) makeFlagChange(y + i, x + i, y);
for (int i = 1; (y + i <= m) && (x - i >= 0); i++) makeFlagChange(y + i, x - i, y);
//vertical flag & southeast flag & southwest flag
}
紧接着我们来设计递归算法的最主要核心部分:我们如何处理棋盘中的某一个位置。
假设现在我们的视野缩小到棋盘上的任意一个格子(x,y),这里的x我的定义是横坐标,y是纵坐标(即第几行),这个格子可能处在哪些特殊位置上呢?
这个格子可能处于棋盘的最后一行,因此,一旦我们可以确定它的解,则已经得出了八皇后问题的一个答案;
这个格子可能处于棋盘中不在边上的一个地方,这时我们考察它的值:如果它的值是-1,说明这个格子可以摆放一个新的皇后,我们就立即摆放在此一个新的皇后,然后更新棋盘,让系统从下一行开始测试下一个皇后的摆放位置;如果它的值不是-1,说明这个格子是其他皇后的攻击区域,不能摆放新的皇后,于是让我们的程序测试同一行的下一个格子(x+1,y);
这个格子还有可能处在最右侧的边缘一列上,如果这个格子的值为-1,万事大吉,我们依然只需放置皇后然后让程序滚到下一行去测下一个皇后,这和本行没有关系了;如果这个格子的值不是-1,说明我们至少已经测完了本行的所有位置,不可能再有新的解,我们等待程序回溯即可。
对于第一种情况,格子处在最后一行,有解,我们写一个方法把解打印出来。为了打印解,我额外设置了一个plan[]
数组来存放程序每一次进入递归时,皇后放置的位置。你可以在文末的总代吗中看到plan[]
的值在哪定义,plan[]
是一个一维数组,第0个数的值是第1行的皇后的位置。
public boolean isEnd(int y) { // Determine if a line has reached the end.
if (y == m) {
sum = sum + 1;
for (int i = 0; i <= m; i++) {
System.out.print(plan[i] + "\t");
}
System.out.println();
return true;
} else {
return false;
}
}
因此,我们的核心递归算法就写出来了:
public void find(int y, int x) {
if (table[y][x] == -1) {
makeFlag(y, x);
if (!isEnd(y)) find(y + 1, 0);
}
refresh(y);
if (x != m) find(y, x + 1);
}
以上就是全部思路和表述,下面是完整代码,共59行,相对简洁。对于初学者,可以将其完整复制到文本文件,并重命名为Knight.java来编译和运行。至于为什么是骑士而不是皇后,因为我在新建文件时一时没想起来皇后的英文单词(
修改代码第二行n的值可以解决9皇后,10皇后,n皇后的问题(但是最好不要解决超过14皇后的问题,会死机)
public class Knight {
int n = 8; //n knights in an n*n table.
int m; //m is the limit of the array (m=n-1);
int table[][] = new int[n][n];
int plan[] = new int[n];
int sum = 0;
public static void main(String[] args) {
Knight one = new Knight();
one.m = one.n - 1;
one.refresh(0);
one.find(0, 0);
System.out.println("The total probability is " + one.sum);
}
public void refresh(int a) { // which a is the origin value to refresh.
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= m; j++) {
if (table[i][j] == a) table[i][j] = -1;
}
}
}
public boolean isEnd(int y) { // Determine if a line has reached the end.
if (y == m) {
sum = sum + 1;
for (int i = 0; i <= m; i++) {
System.out.print(plan[i] + "\t");
}
System.out.println();
return true;
} else {
return false;
}
}
public void makeFlagChange(int y, int x, int a) { //y,x is the real (x,y) value, and the a is flag value.
if (table[y][x] == -1) table[y][x] = a;
}
public void makeFlag(int y, int x) { // make flags to let next function know the process.
table[y][x] = y;
for (int i = 1; y + i <= m; i++) makeFlagChange(y + i, x, y);
for (int i = 1; (y + i <= m) && (x + i <= m); i++) makeFlagChange(y + i, x + i, y);
for (int i = 1; (y + i <= m) && (x - i >= 0); i++) makeFlagChange(y + i, x - i, y);
//vertical flag & southeast flag & southwest flag
}
public void find(int y, int x) {
plan[y] = x + 1;
if (table[y][x] == -1) {
makeFlag(y, x);
if (!isEnd(y)) find(y + 1, 0);
}
refresh(y);
if (x != m) find(y, x + 1);
}
}
有考虑拿c写吗 ∠( ᐛ 」∠)_
不会c,没学过。上周看c的书想试试写一下结果发现有点难写,面向过程有点搞不明白(卡在传参那里了)