How would one see if an array has consecutive numbers in C++?

Question

This is basically the 8 Queens problem, but solving it with brute force in a 1D array. Say I have an array (named b) of size 8, with elements ranging from 0 to 7.

I initialize each index in the array with 8 for-loops, like this:

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);
                }
            }}
        }}
    }}
}}

What this program is supposed to do is check every combination of numbers 0 to 7 and returning true for only certain conditions. There are supposed to be 92 solutions, if this sounds familiar, it should be - it is the 8 Queens problem using brute force. From here, this is what I understand are the conditions:

I want to be able to check if an array has a consecutive string of numbers; such as:

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

Here, the elements b[3], b[4] and b[5] are consecutive. I don't want that, I want to return false, since there is a consecutive string of numbers (basically queens are attacking)

I also do not want an array that has a string of backwards consecutive numbers like this:

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

And lastly, I do not want two or more numbers in indexes where it would make them look consecutive if we had simply changed then numbers between them:

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

Above is not acceptable because b[0] and b[7] are numbers in their "consecutive index" (because at least 2 queens are attacking each other).

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

Above is also not acceptable because b[1] and b[4] are also in consecutive indexes.

Similarly, when the values are swapped, the arrays

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

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

are also not acceptable. I also cannot have 2 or more of the same number.

The problem I am having is in creating the check function. I am told I need to use 1 for loop and 1 if-then statement. Can the check function just take the whole array as is? And if it does, how do look at the right-most element in the array, and check to see if it has consecutive indexes (queens are attacking it)? I've tried this:

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;
}

But not only does this not work (I get 300+ solutions), it is not as small as I am told it should be.

Answer 1

I think there is a little problem with your check of collisions in the diagonals: you've got 15 diagonals going each way (including the very short one-square diagonals in the corners), while your code checks only seven of each due to the board[c]+i <= 7 and board[c]-i >= 0 conditions.

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;