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.."] ] 这是著名的n皇后问题，在n*n的棋盘上摆放n个皇后，要求任意2个皇后不能在同一行、同一列以及同一斜线上，求所有满足要求的集合。Q代表皇后， .代码空格。 这个题可以用回溯的思想解决， 我们先在棋盘的第一行任意选择一个方块放置一个皇后，然后在第二行选择一个 合适的位置（指该位置所在的行、列以及斜线都没有皇后） 放置第二个皇后，依次放置下去，如果某一行的所有位置都无法放置皇后，那么回溯，改变上一个皇后的位置，再重复此过程，直到第n行也放置了一个皇后，我们将这种合理的放置方式存储在集合中，继续回溯。 下面是代码： public class Solution { public List<List<String>> solveNQueens(int n) { char[][] ch = new char[n][n]; for(char[] c : ch){ //定义一个二维char数组，数组元素为'.'; Arrays.fill(c,'.'); } List<List<String>> list = new ArrayList<>(); fon(ch,0,list); return list; } public void fon(char[][] ch, int n, List<List<String>> list){ if(n == ch.length){ //放置方案满足要求，存放在list中 List<String> l = new ArrayList<>(); for(int i=0;i<ch.length;i++){ l.add(new String(ch[i])); } list.add(l); return; }else{ for(int i=0;i<ch.length;i++){ if(fon1(ch,n,i)){ //在第n行的第i个元素的位置上放置一个皇后 fon(ch,n+1,list); //向下递归 ch[n][i] = '.'; //更改回来 } } } } public boolean fon1(char[][] ch, int a, int b){ //判断char[a][b]是否可以放置一个皇后 for(int i=0;i<ch.length;i++){ if(ch[a][i] == 'Q' || ch[i][b] == 'Q') //判断该元素所在行或者列是否已经有皇后 return false; if(a+b-i>=0 && a+b-i<ch.length) //判断该元素所在的左下到右上的斜线是否已经有皇后 if(ch[i][a+b-i] == 'Q') return false; if(b-a+i>=0 && b-a+i<ch.length) //判断该元素所在的左上到右下的斜线是否已经有皇后 if(ch[i][b-a+i] == 'Q') return false; } ch[a][b] = 'Q'; //在该位置上放置一个皇后 return true; } }这个方法在LeetCode上超过了83.36%的其他方法，还算不错。这是一个经典的回溯的问题，在上面的代码中，我们借用了数组，每一行的元素都可以是回溯算法中的“一条岔路”，我们使用for循环遍历所有岔路，更普遍的是使用一个集合存储所有的“岔路”，进而遍历集合。
