面试题 08.12

Write an algorithm to print all ways of arranging n queens on an n x n 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.

Notes: This problem is a generalization of the original one in the book.

Example:

Input: 4 Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] Explanation: 4 queens has following two solutions [ [".Q..", // solution 1 "...Q", "Q...", "..Q."],

["..Q.", // solution 2 "Q...", "...Q", ".Q.."] ]

Solutions

1. backtracking with iteration

class Solution {
public:
    bool valid(vector<int> & pos, int r2) {
        int c2 = pos[r2];
        for (int r1 = 0; r1 < r2; r1++) {
            int c1 = pos[r1];
            if (c1 == c2 || r1 + c1 == r2 + c2 || r1 - c1 == r2 - c2)
                return false;
        }
        return true;
    }

    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;

        vector<int> pos(n + 1, -1);
        int r = 0;
        while (r >= 0) {
            // try next position in the current row
            pos[r]++;
            // Find a answer
            if (r >= n) {
                vector<string> solu(n, string(n, '.'));
                for (int r = 0; r < n; r++)
                    solu[r][pos[r]] = 'Q';
                res.push_back(move(solu));
                r--;
            } // no valid position in the current row
            else if (pos[r] >= n)
                r--;
            // find a valid position in the current row
            else if (valid(pos, r))
                pos[++r] = -1;
        }

        return res;
    }
};