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<int> > placeQueens(int n) { vector<vector<int> > res; vector<int> pos(n, -1); placeQueensDFS(pos, 0, res); return res; } void placeQueensDFS(vector<int> &pos, int row, vector<vector<int> > &res) { 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<int> &pos, int row, int col) { for (int i = 0; i < row; ++i) { if (col == pos[i] || abs(row - i) == abs(col - pos[i])) { return false; } } return true; } };
本文转自博客园Grandyang的博客，原文链接：八皇后问题[CareerCup] 9.9 Eight Queens，如需转载请自行联系原博主。
