nqueens - проверка с доской, вместо предыдущих ферзей

Question

Здесь так много вопросов, касающихся проблемы Nqueens. Однако моя реализация отличается. Мой код проверяет доску, возможно ли размещение ферзя, вместо того, чтобы проверять позицию предыдущей ферзя.

Это выглядит так:

initially, the board has all zeros filled. The algorithm starts with the position (0,0). Then, it checks 
row-wise per column to find the first 0. After finding the first zero, it changes the zero to one. 
From this point onward, my logic differs. Instead of going to the next column, it first disables all the 
positions, which the currently placed queen attacks, i.e. writes -1 on those places, i.e., row, column,
upper diagonal and lower diagonal. Now, the column value increments, and instead of check with the previous queen,
it simply has to find the first zero. Then again, relative positions get disabled.... you get the idea.

Код:

#include <iostream>

int board[8][8];

void printBoard() {
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            std::cout << board[i][j] << " ";
        }
        std::cout << "\n";
    }
}

void disablePositions(int row, int col) {
    //disable row
    for (int j = col + 1; j < 8; j++) {
        board[row][j] = 2;
    }

    //disable column
    for (int i = 0; i < 8; i++) {
        if (board[i][col] == 1) {
            continue;
        }
        board[i][col] = 2;
    }

    //disable upper diagonal
    for (int i = row - 1, j = col + 1; i >= 0 || j < 8; i--, j++) {
        board[i][j] = 2;
    }

    for (int i = row + 1, j = col + 1; i < 8 || j < 8; i++, j++) {
        board[i][j] = 2;
    }
}

void solve(int initial_row) {
    int init = initial_row;
    int row = 0;
    int col = 0;
    while (col != 8) {
        for (row = init; row < 8; row++) {
            if (board[row][col] == 0) {
                board[row][col] = 1;
                break;
            }
        }
        if (row == 8) {
            col = 0;
            initial_row++;
            init = initial_row; 
            for (int i = 0; i < 8; i++) {
                for (int j = 0; j < 8; j++) {
                    board[i][j] = 0;
                }
            }
        }
        else {
            init = 0;
            disablePositions(row, col);
            col++;
        }
        printBoard();
        std::cout << std::endl;
    }
}

int main() {
    solve(0);
    std::cout << std::endl;
}

Этот код для 8 королев. Проблема в том, что после того, как он достигает стадии, где он начинается с [5] [0], он просто падает. В чем причина проблемы?

Кроме того, поскольку она пытается сделать оптимальный выбор на каждом этапе, мы бы назвали это жадным алгоритмом?

Answer 1

В ваших disable upper diagonal циклах вы ошиблись. При использовании операции || зацикливание продолжается, когда выполняется любое из условий, что приведет к выходу за пределы массива.

Измените условия в обоих циклах на && (и ).