2

这基本上是 8 个皇后问题，但是在一维数组中用蛮力解决它。假设我有一个大小为 8 的数组（名为 b），其元素范围为 0 到 7。

我用 8 个 for 循环初始化数组中的每个索引，如下所示：

int b[8]={0};

int count = 0;


for(b[0] = 0; b[0]<8; b[0]++){ 
for(b[1] = 0; b[1]<8; b[1]++){ 
for(b[2] = 0; b[2]<8; b[2]++){ 
for(b[3] = 0; b[3]<8; b[3]++){ 
for(b[4] = 0; b[4]<8; b[4]++){ 
for(b[5] = 0; b[5]<8; b[5]++){
for(b[6] = 0; b[6]<8; b[6]++){
for(b[7] = 0; b[7]<8; b[7]++){
                if(check(b)) 
                {
                count++;
                print(b, count);
                }
            }}
        }}
    }}
}}

这个程序应该做的是检查数字 0 到 7 的每个组合，并仅在某些条件下返回 true。应该有 92 个解决方案，如果这听起来很熟悉，应该是 - 这是使用蛮力的 8 个皇后问题。从这里，这就是我所理解的条件：

我希望能够检查一个数组是否有连续的数字串；如：

[0|5|7|1|2|3|6|4]

这里，元素b[3]、b[4]和b[5]是连续的。我不想这样，我想返回false，因为有一串连续的数字（基本上是皇后在进攻）

我也不想要一个包含一串向后连续数字的数组，如下所示：

[0|5|7|3|2|1|6|4]

最后，我不希望索引中有两个或更多数字，如果我们只是更改它们之间的数字，它们会使它们看起来是连续的：

[0|2|4|6|1|3|5|7]

以上是不可接受的，因为 b[0] 和 b[7] 是它们“连续索引”中的数字（因为至少有 2 个皇后在互相攻击）。

[6|1|3|0|4|7|5|2]

以上也是不可接受的，因为 b[1] 和 b[4] 也在连续索引中。

同样，当交换值时，数组

[7|2|4|6|1|3|5|0]

[6|4|3|0​​|1|7|5|2]

也是不能接受的。我也不能有 2 个或更多相同的数字。

我遇到的问题是创建检查功能。我被告知我需要使用 1 个 for 循环和 1 个 if-then 语句。检查功能可以按原样获取整个数组吗？如果是这样，如何查看数组中最右边的元素，并检查它是否有连续的索引（皇后正在攻击它）？我试过这个：

bool ok(int board[8]){

    for(int c = 7; c >= 0; c--){ //row check
        for (int j=0; j<c; j++){
            if (board[c]==board[j]){
                return false;
            }
        }


        for(int i = 1; i <= c; i++){
            // diagonal check from top left to bottom right
            if  ((board[c]-i >= 0) && (board[c-i] == board[c]-i))
                {return false;}
            if ((board[c]+i <= 7) && (board[c+i] == board[c]+i))
                {return false;}
            // diagonal check from bottom left to top right
            if ((board[c]-i >= 0) && (board[c-i] == board[c]+i))
                {return false;}
            if ((board[c]+i <= 7) && (board[c+i] == board[c]-i))
                {return false;}

        }

    }

    return true;
}

但这不仅行不通（我得到了 300 多个解决方案），它也没有我听说的那么小。

4

1 回答 1

1

我认为检查对角线中的碰撞有一个小问题：每条路都有 15 条对角线（包括角落里非常短的方形对角线），而您的代码只检查了其中的 7 条，因为board[c]+i <= 7和board[c]-i >= 0条件。

Here is how you can simplify the checks and make them faster with the use of three boolean arrays: you've got 8 rows, 15 ascending diagonals, and 15 descending diagonals:

bool row[8];
bool ascending[15];
bool descending[15];

Initially, there are no queens in any of these rows/diagonals. As you go through the elements of board, do this:

for (int i = 0 ; i != 8 ; i++) {
    // Check and mark the row
    if (row[board[i]]) return false;
    row[board[i]] = true;
    // Check and mark the ascending diagonal
    int ascIdx = board[i]+i;
    if (ascending[ascIdx]) return false;
    ascending[ascIdx] = true;
    int descIdx = 7+board[i]-i;
    if (descending[descIdx]) return false;
    descending[descIdx] = true;
}
return true;
于 2013-03-03T17:51:06.363 回答