9.9 Write an algorithm to print all ways of arranging eight queens on an 8x8 chess board so that none of them share the same row, column or diagonal. In this case, "diagonal" means all diagonals, not just the two that bisect the board.
LeetCode上的原题,请参见我之前的博客N-Queens N皇后问题和N-Queens II N皇后问题之二。
class Solution {
public:
vector
vector
vector
placeQueensDFS(pos, 0, res);
return res;
}
void placeQueensDFS(vector
int n = pos.size();
if (row == n) res.push_back(pos);
else {
for (int col = 0; col < n; ++col) {
if (isValid(pos, row, col)) {
pos[row] = col;
placeQueensDFS(pos, row + 1, res);
pos[row] = -1;
}
}
}
}
bool isValid(vector
for (int i = 0; i < row; ++i) {
if (col == pos[i] || abs(row - i) == abs(col - pos[i])) {
return false;
}
}
return true;
}
};
发表评论