八皇后问题的解法(Java版)

本文主要描述思路,Java入门初学者,代码比较简单。 网上的八皇后解法有很多种,这是我自己设计出来的一种算法,因此不能算是在水文章。

本文主要描述思路,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);
    }

8皇后问题的最终输出解
8皇后问题的最终输出解

以上就是全部思路和表述,下面是完整代码,共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);
    }
}

添加新评论

已有 2 条评论

有考虑拿c写吗 ∠( ᐛ 」∠)_

不会c,没学过。上周看c的书想试试写一下结果发现有点难写,面向过程有点搞不明白(卡在传参那里了)