public List<List<String>> solveNQueens(int n) {
		List<List<String>> res = new LinkedList<>();
		if(n<=0){
			return res;
		}else if(n==1){
			List<String> l = new ArrayList<String>(1);
			l.add("Q");
			res.add(l);
			return res;
		}
		int half = n/2;
		for(int i=0;i<half;i++){
			for(int j=0;j<half;j++){
				nqueen(getNewBoard(n),i,j,0,res);
			}
		}
		return res;
	}