LintCode(33) N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

Have you met this question in a real interview? 

Yes

Example

There exist two distinct solutions to the 4-queens puzzle:

[

    [".Q..", // Solution 1

     "...Q",

     "Q...",

     "..Q."],

    ["..Q.", // Solution 2

     "Q...",

     "...Q",

     ".Q.."]

]

Challenge

Can you do it without recursion?

基本算是暴力搜索了，剪枝的部分在于判断是不是一个合适的解，知道形成一个完整解之后，build string然后push到容器里。 本质是DFS， 加一点判断对角线的下三滥trick， 所以很无聊

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57

class Solution { public: /** * Get all distinct N-Queen solutions * @param n: The number of queens * @return: All distinct solutions * For example, A string '...Q' shows a queen on forth position */ vector<vector<string> > solveNQueens(int n) { // write your code here vector<vector<string>> result; vector<int> solution; if (n==0) return result; helper(result, solution, n); return result; } void helper(vector<vector<string>>& result, vector<int>& solution, int n){ if (solution.size()==n){ build_result(result, solution); return; } for (int i = 0; i<n; i++){ if (!isValidSolution(solution, i)) continue; solution.push_back(i); helper(result, solution, n); solution.pop_back(); } } void build_result(vector<vector<string>>& result,const vector<int>& solution){ int n=solution.size(); vector<string> res(n, string(n,'.')); for (int i=0; i<n; i++){ res[i][solution[i]]='Q'; } result.push_back(res); } bool isValidSolution(const vector<int>& solution, int ind){ int n = solution.size(); if (n==0) return true; for (int i=0; i<n; i++){ if (solution[i]==ind) return false; if (i-solution[i]==n-ind) return false; if (i+solution[i] == n+ind) return false; } return true; } };