Lintcode: N-Queens I

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?

Tags Expand 

Recursion

Recursion solution:

Reference:
八皇后问题
http://bangbingsyb.blogspot.com/2014/11/leetcode-n-queens-i-ii.html

use vector<int> &col to remember all cols queens appears
end condition: row == n
recursive condition: current col don't appear in the col vector, and not in diagonal  

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

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> > allSol; vector<string> sol; vector<int> col; solveNQ(n, 0, col, sol, allSol); return allSol; } private: void solveNQ(int n, int irow, vector<int> &col, vector<string> &sol, vector<vector<string> > &allSol){ if(irow == n){ allSol.push_back(sol); return; } for(int icol = 0; icol < n; icol++){ if(isValid(irow, icol, col)){ string s(n, '.'); s[icol] = 'Q'; col.push_back(icol); sol.push_back(s); solveNQ(n, irow + 1, col, sol, allSol); col.pop_back(); sol.pop_back(); } } } bool isValid(int irow, int icol, vector<int> &col){ //improve efficency, can be deleted if(irow < col.size()) return false; for(int i = 0; i < col.size(); i++){ //(irow, icol) (i, col[i]) if(icol == col[i]) return false; //diagonal judge if(abs(irow - i) == abs(icol - col[i])) return false; } return true; } };

Lintcode second:
back tracking are dfs with limited levels
Logics are mess, remember to use functions to help better format and logics

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

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<int> rows(n); vector<vector<string> > allsol; vector<string> sol; DFS(0, n, rows, sol, allsol); return allsol; } void DFS(int row, int n, vector<int> &rows, vector<string> &sol, vector<vector<string> > &allsol){ if(row == n){ allsol.push_back(sol); return; } if(row > n) return; for(int col = 0; col < n; col++){ //whether can be placed at (row, col) //judge whether row and col is safe bool valid = true; for(int j = 0; j < row; j++){ int prerow = j; int precol = rows[j]; if(precol == col) { valid = false; break; } if(abs(row - prerow) == abs(col - precol)) { valid = false; break; } } //if col and row is valid, save into sol and continue DFS, also update rows if(valid) { string temp; for(int i = 0; i < n; i++){ if(i == col) temp += "Q"; else temp += "."; } sol.push_back(temp); rows[row] = col; DFS(row + 1, n, rows, sol, allsol); sol.pop_back(); } } } };