[LeetCode59]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.

For example,

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

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

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

Analysis:

The classic recursive problem.

1. Use a int vector to store the current state, A[i]=j refers that the ith row and jth column is placed a queen.

2. Valid state: not in the same column, which is A[i]!=A[current], not in the same diagonal direction: abs(A[i]-A[current]) != r-i

3. Recursion:

Start: placeQueen(0,n)

if current ==n then print result

else

for each place less than n,

place queen

if current state is valid, then place next queen place Queen(cur+1,n)

end for

end if

Java

public class Solution {
    List<String[]> result;
	int[] A;
	public List<String[]> solveNQueens(int n) {
		result = new ArrayList<String[]>();
		A = new int[n];
		nqueens(0, n);
		return result;
    }
	public void nqueens(int cur, int n){
		if(cur==n) printres(n);
		else {
			for(int i=0;i<n;i++){
				A[cur] = i;
				if(valid(cur)){
					nqueens(cur+1, n);
				}
			}
		}
	}
	public void printres(int n){
		String[] tem = new String[n];
		for(int i=0;i<n;i++){
			StringBuffer sBuffer = new StringBuffer();
			for(int j=0;j<n;j++){
				if(j==A[i]) sBuffer.append('Q');
				else sBuffer.append('.');
			}
			tem[i] = sBuffer.toString();
		}
		result.add(tem);
	}
	public boolean valid(int r){
		for(int i=0;i<r;i++){
			if(A[i]==A[r]|| Math.abs(A[i]-A[r])==r-i){
				return false;
			}
		}
		return true;
	}
}
           

c++

class Solution {
public:
    void printQueen(vector<int> &A,int n,vector<vector<string>> &result){
    vector<string> r;
        for(int i=0;i<n;i++){
            string str(n,'.');
            str[A[i]] = 'Q';
            r.push_back(str);
        }
        result.push_back(r);
}
bool isValidQueens(vector<int>A,int r){
    for(int i=0;i<r;i++){
        if((A[i]==A[r])||(abs(A[i]-A[r]))==(r-i))
            return false;
    }
    return true;
}
void nqueens(vector<int> A,int cur, int n,vector<vector<string>> &result){
    if(cur == n){
        printQueen(A,n,result);
    }else{
        for(int i=0;i<n;i++){
            A[cur] = i;
            if(isValidQueens(A,cur))
                nqueens(A,cur+1,n,result);
        }
    }
}
vector<vector<string> > solveNQueens(int n) {
    vector<vector<string>> result;
    result.clear();
    vector<int> A(n,-1);
    nqueens(A,0,n,result);
    return result;
}
};