c++ - 如何在 C++ 中查看数组是否具有连续数字？

Question

这基本上是 8 Queens 问题，但在一维数组中用蛮力求解。假设我有一个大小为 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 Queens 问题。从这里，这是我所理解的条件:

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

[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]

以上是 Not Acceptable ，因为 b[0] 和 b[7] 是它们“连续索引”中的数字(因为至少有 2 个皇后在互相攻击)。

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

上面也是 Not Acceptable ，因为 b[1] 和 b[4] 也在连续的索引中。

类似地，当交换值时，数组

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

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

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

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

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 多个解决方案)，而且它并不像我被告知的那样小。

Answer 1

我认为您在检查对角线碰撞时存在一个小问题:每个方向有 15 条对角线(包括拐角处非常短的一方形对角线)，而您的代码只检查每条对角线中的 7 条由于 board[c]+i <= 7和 board[c]-i >= 0条件。

以下是如何使用三个 bool 数组简化检查并使其更快:您有 8 行、15 个上升对角线和 15 个下降对角线:

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

最初，这些行/对角线上都没有皇后。当您浏览 board 的元素时，这样做:

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;