四皇后问题（暴力穷举）
|
6,861
|
算法,题解
|
tdiant

今天老师上课讲解n皇后问题，提出一个比较简单的问题：如何用穷举法来解决四皇后问题。
由于我太菜了，用了比较长的时间来解决这个问题。emmmm，在一顿反思之后，决定总结一下。

四皇后问题

皇后可以吃掉棋盘上其所在行、列以及对角线上的所有旗子。如果有4和皇后，如何摆放才能使其在一个 4*4 的棋盘上共存呢？

思路

考虑到每个皇后可以吃掉其所在行上的所有旗子，那么显然，不可能存在一行有多个皇后的问题，皇后肯定各自独占一行。
这也就意味着，我们在接下来的暴力穷举时，只需要考虑这四个皇后在它们所在行的第几列即可。我们写的程序大致原理应当是对每个皇后在其所在行的四个位置进行穷举。

我们的程序应当是四个for嵌套，形成一个四重循环结构。每重循环遍历每行的各个列，以此对各种可能性进行穷举。
由于这种结构时间复杂度是O(n^n)，显然这种方法对于解决n皇后问题而言效率太低，因此理论上对于四个以上的皇后并存问题而言，这种方式不可取。

实现

在实际的操作中，考虑到各个皇后只能占据其所在行的某一列，显然，这个棋盘只需要表示为一个一维数组既可。
下面的操作为了表示的更加直观，我还是用了二维数组。

放置皇后与撤销放置

创建了一个二维数组, 表示皇后是否在某个位置上放置

bool a[5][5]={false};

放置皇后的操作应当是这样

void place(int x, int y) {
    if (x <= 0 || y <= 0 || x > 4 || y > 4)
        return;
    if (isCanPlace(x, y)) { //isCanPlace表示这个位置是否能放置皇后
        a[y][x] = true;
    }
}

对于这四个循环而言，每次循环都应该撤销上一次循环的操作才行，所以我们需要一个place操作的反操作，也就是撤销放置。

void unplace(int x, int y) {
    if (x <= 0 || y <= 0 || x > 4 || y > 4)
        return;
    for (int i = y; i <= 4; ++i) {
        for (int j = 1; j <= 4; ++j) {
            a[i][j] = false;
        }
    }
}

在这里因为，假如我们撤销的是第二行的皇后放置操作，实际上我们应当把第二行、第三行、第四行的放置操作全部撤销才对。

能否放置的判定

bool isCanPlace(int x, int y) {
    //显然如果这个位置没有被放置皇后才能放置
    if (a[y][x] == false) {
        for (int i = 1; i <= 4; ++i) {
            //判断这一行有没有皇后
            if (a[y][i] != 0)
                return false;
            //判断列
            if (a[i][x] != 0)
                return false;
            //判断右下方向对角线
            if (y + i < 5 && x + i < 5 && a[y + i][x + i] != 0)
                return false;
            //判断左下方向对角线
            if (y + i < 5 && x - i > 0 && a[y + i][x - i] != 0)
                return false;
            //判断右上方向对角线
            if (y - i > 0 && x + i < 5 && a[y - i][x + i] != 0)
                return false;
            //判断左上方向对角线
            if (y - i > 0 && x - i > 0 && a[y - i][x - i] != 0)
                return false;
        }
    } else {
        return false;
    }
    return true;
}

做出嵌套循环进行穷举

int main() {
    for (int i = 1; i <= 4; ++i) {

        unplace(i - 1, 1);
        if (isCanPlace(i, 1)) {
            place(i, 1);

            for (int j = 1; j <= 4; ++j) {

                unplace(j - 1, 2);
                if (isCanPlace(j, 2)) {
                    place(j, 2);

                    for (int k = 1; k <= 4; ++k) {
                        unplace(k - 1, 3);
                        if (isCanPlace(k, 3)) {
                            place(k, 3);

                            for (int l = 1; l <= 4; ++l) {
                                unplace(l - 1, 4);
                                if (isCanPlace(l, 4)) {
                                    place(l, 4);
                                    cout << i << " " << j << " " << k << " " << l << endl;
                                }
                            }

                        }
                    }

                }
            }

        }
    }
    return 0;
}

四皇后问题答案是：

2 4 1 3
3 1 4 2
上一篇
下一篇