algorithm - 8皇后问题算法的一些疑惑

Question

我正在研究8皇后问题，我认为以下算法可以解决这个问题（但似乎不正确）

我的算法在 8X8 棋盘上以这种方式工作：

一开始在棋盘的随机位置放一个皇后
将当前女王的水平线、垂直线和两条对角线上的所有位置标记为无法使用。
将另一个皇后放在棋盘上仍然空闲的任何位置
重复这个过程（从第 2 点开始），直到板上有可用的位置

我已经在纸上尝试过这个解决方案，但通常我只能放置 7 个皇后而不是皇后......

所以我认为这个解决方案能够放置一些不能互相吃掉的皇后，但它不能确保，如果我使用 nXn 板，我总是可以放置 8 个皇后......

这是真的吗？

肿瘤坏死因子

安德烈亚

score 3 · Accepted Answer

为您的算法添加回溯。如果放置第 7 个皇后会导致没有第 8 个皇后的位置，那么这对第 7 个皇后来说是一个糟糕的位置。所以删除它并为它选择一个不同的位置。如果你的第 7 个皇后的位置用完了，这意味着第 6 个皇后的位置不好，等等。

score 3 · Accepted Answer

@miorel关于回溯是完全正确的。只是为了好玩，我尝试使用简单的递归算法在 C/C++ 中解决这种蛮力，并进行了一个简单的优化：

我们知道，对于任何给定的问题大小 N，每个皇后都将位于单独的列中。所以我们甚至不尝试其他列。所以想法是这样的：

每个皇后都有自己的列，因此皇后 1 进入第 1 列，皇后 2 进入第 2 列，以此类推。
所以真正的目标是为每个皇后挑选一行。从第一个皇后开始，让我们依次尝试每一行。我们通过在可能的行中放置一个皇后来做到这一点，然后进行递归调用以放置第二个、第三个和第四个皇后。

在检查放置是否兼容时，我们只需要检查 a) 同一行是否有皇后 b) 是否有对角线皇后。

#include <stdlib.h>
#include <stdio.h>

int solveQueens(int queenIndex, int sz, int * positions) {
    for (int i=0; i<sz; i++) {
        int valid = 1;
        for (int j=0; j<queenIndex; j++) {
            int diff = queenIndex-j;
            if ( 
                    (positions[j]==i)
                ||  (positions[j]+diff == i) 
                ||  (positions[j]-diff == i)
            ) {
                valid = 0;
                break;
            }
        }

        if (valid) {
            positions[queenIndex]=i;
            if (queenIndex < sz-1) {
                // Recursive call
                int res = solveQueens(queenIndex+1, sz, positions);
                if (res) 
                    return 1;
            } else {
                return 1;
            }
        }
    }
    return 0;
}

void printQueens(int sz, int * positions) {
    for (int i=0; i<sz; i++) {
        printf("%c%d ", (char)(i+(int)'A'), positions[i]+1);
    }   
}

void queens(int sz) {
    int * positions = (int *)malloc(sizeof(int)*sz);
    if (solveQueens(0, sz, positions)) {
        printQueens(sz, positions);
    } else {
        printf("No solutions found\n");
    }
    free(positions);
}

int main() {
    queens(24);
    return 0;
}

我确信这不是最佳算法，但它在 24 板大小的板上工作时间不到 1 秒。

algorithm - 8皇后问题算法的一些疑惑

2 回答 2

Related

Reference