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 循环中，你的条件有误。使用 || 操作，当任一条件为真时循环继续，这将导致对数组的越界访问。

将两个 for 循环中的条件更改为 && (and).

nqueens - 检查棋盘，而不是以前的皇后

nqueens - checking with the board, instead of previous queens

c++

loops

n-queens