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(); } } } };

Lintcode: Subsets

Given a set of distinct integers, return all possible subsets.

Have you met this question in a real interview? 

Yes

Example

If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Note

Elements in a subset must be in non-descending order.

The solution set must not contain duplicate subsets.

Tags Expand 

Recursion

Initial thought:

I imitate the combination problem: 

I resolve this subsets problem into solve combinations problem.

Assume there are n numbers in vector, I can get combinations of k numbers from n

Let k be from 0 to n, and combining all solutions, I will get all subsets.

In below codes, combine () functions works to get combination for different k

Time: O(n! + (n-1)! + (n-2)! + ... + 1)
Space: O(n)

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

class Solution { public: /** * @param S: A set of numbers. * @return: A list of lists. All valid subsets. */ vector<vector<int> > subsets(vector<int> &nums) { // write your code here vector<vector<int> > res; sort(nums.begin(), nums.end()); for(int i = 0; i <= nums.size(); i++){ combine(i, nums, res); } return res; } private: void combine(int n, vector<int> &nums, vector<vector<int> > &res){ vector<int> tempres; DFS(0, n, nums, tempres, res); } void DFS(int start, int n, vector<int> &nums, vector<int> &tempres, vector<vector<int> > &res){ if(n == 0) { res.push_back(tempres); return; } for(int i = start; i < nums.size() - n + 1; i++){ tempres.push_back(nums[i]); DFS(i + 1, n - 1, nums, tempres, res); tempres.pop_back(); } } };

Common solution:
//Reference thoughts and cods
https://siddontang.gitbooks.io/leetcode-solution/content/backtracking/subsets.html


Just push all result in tempres into res when dfs
Time: O(n!)
Space: O(n)

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

class Solution { public: /** * @param S: A set of numbers. * @return: A list of lists. All valid subsets. */ vector<vector<int> > subsets(vector<int> &nums) { // write your code here vector<vector<int> > res; vector<int> tempres; sort(nums.begin(), nums.end()); res.push_back(tempres); DFS(0, nums, tempres, res); return res; } private: void DFS(int start, vector<int> &nums, vector<int> &tempres,vector<vector<int> > &res){ for(int i = start; i < nums.size(); i++){ tempres.push_back(nums[i]); DFS(i + 1, nums, tempres, res); res.push_back(tempres); tempres.pop_back(); } } };