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.."] ]思路：
采用经典解法回溯递归，一层一层的向下扫描，需要用到一个columns数组，其中columns[row] = col表示row行col列存在皇后，从0行开始递归，每一行都依次遍历各列，判断如果在该位置放置皇后会不会有冲突，以此类推，当到最后一行的皇后放好后，一种解法就生成了，将其存入结果result中，然后继续完成搜索所有的情况
代码AC：
public class Solution { public List<List<String>> solveNQueens(int n) { List<List<String>> result = new ArrayList<List<String>>(); //columns[row] = col表示在row行col列放置queen int[] columns = new int[n]; solveNQueens(0, columns, result, n); return result; } public void solveNQueens(int row, int[] columns, List<List<String>> result, int n){ if(row == n){ //找到有效的摆法 List<String> str = new ArrayList<String>(); for(int i = 0; i < n; i++ ){ String s = ""; for(int k = 0; k < n; k++){ s+="."; } str.add(s); } for(int j = 0; j < n; j++){ StringBuilder strBuilder = new StringBuilder(str.get(j)); strBuilder.setCharAt(columns[j], 'Q'); str.set(j, strBuilder.toString()); } result.add(str); }else{ for(int col = 0; col < n; col++){ if(checkValid(columns, row, col)){ columns[row] = col; //摆放皇后 solveNQueens(row+1, columns, result, n); } } } } public boolean checkValid(int[] columns, int row, int col){ for(int tempRow = 0; tempRow < row; tempRow++){ //若两个皇后在同一列，则无效 if(columns[tempRow] == col) return false; //若两个皇后在对角线则无效 if(Math.abs(columns[tempRow]-col)== row-tempRow) return false; } return true; } }
