这里有很多关于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]开始的阶段后,它就崩溃了。是什么导致了这个问题?