N-QueensThe 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皇后问题转化为全排列问题。设x[n]为一组解，，代表第i行第x[i]列放置了皇后。
所以求出全排列，然后判断是否合法即可。
代码如下（没有Ac，进一步优化之后应该是可以Ac的）：
public class Solution {public List<List<String>> solveNQueens(int n) {List<List<String>> returnList = new ArrayList<List<String>>();/*** x[i]为第i列存放的位置* 转化为0-（n-1）的全排列，然后判断全排列的位置是否合法即可*/int[] num = new int[n];int i = 0;while(i < n){num[i] = i;//填充数组为0-(n-1)i++;}List<List<Integer>> list = permuteUnique(num);for(List<Integer> al : list){//对每一组数据处理for(i = 0; i < al.size(); i++){if(!check(al, i, al.get(i)))break;//不合法跳出}if(i == n){//到最后一位，说明全部合法List<String> ls = new ArrayList<String>();for(i = 0; i < al.size(); i++){String s = "";//每一组的Stringfor(int j = 0; j < n;j++){if(j == al.get(i)){s += "Q";//放置皇后的位置}else{s += ".";//不放的位置}}ls.add(s);//添加到ls}returnList.add(ls);//添加一组解}}return returnList;}/*** 判断是否合法* @param al 一组解* @param i 当前行* @param x 当前列* @return 是否合法*/boolean check(List<Integer> al,int i,int x){for(int k = 0; k < i; k++){//只与上方比较，不然与会自身比较if(al.get(k) == x || x – i == al.get(k) – k || x + i == al.get(k) + k)return false;}return true;}//求全排列public static List<List<Integer>> permuteUnique(int[] num) {List<List<Integer>> returnList = new ArrayList<List<Integer>>();returnList.add(new ArrayList<Integer>());for (int i = 0; i < num.length; i++) {Set<List<Integer>> currentSet = new HashSet<List<Integer>>();for (List<Integer> l : returnList) {for (int j = 0; j < l.size() + 1; j++) {l.add(j, num[i]);List<Integer> T = new ArrayList<Integer>(l);l.remove(j);currentSet.add(T);}}returnList = new ArrayList<List<Integer>>(currentSet);}return returnList;}}
另一种思路是回溯法，符合要求的往下走，不符合要求的往回退。
具体代码：
public class Solution {/*** 这题的整体思想是建一个x[n]的数组，意为第i放第x[i]列放置皇后* 皇后的合法判断规则是列不相等，斜线上也不相等* i + x[i] == j + x[j] 表示正斜线一致* x[i] – i = x[j] – j 表示负斜线上一致 都不合法*/List<List<String>> list;//保存结果public List<List<String>> solveNQueens(int n) {list = new ArrayList<List<String>>();int[] x = new int[n];//保存结果queens(x, n, 0);return list;}void queens(int[] x,int n,int row){for(int i = 0; i < n; i++){if(check(x,n,row,i)){//判断合法x[row] = i;//将皇后放在第row行，第i列if(row == n-1){//如果是最后一行，则输出结果addList(x,n);x[row] = 0;//回溯，寻找下一个结果return;}queens(x, n, row+1);//寻找下一行x[row] = 0;//回溯}}}/** * 将每一组的结果添加list * @param x 数组解 * @param n 棋盘长宽 */private void addList(int[] x,int n) {//添加结果String[][] sArr = new String[n][n];List<String> al = new ArrayList<String>();for(int i = 0; i < n ; i++){Arrays.fill(sArr[i], ".");//先填充.sArr[i][x[i]] = "Q";//特定位置放置QString s = "";for(String str:sArr[i]){s += str;//加在一起}al.add(s);//添加一行}list.add(al);//添加一组解}/** * @param x 数组解 * @param n 棋盘长宽 * @param index 当前放置行 * @param i 当前放置列 * @return */boolean check(int[] x,int n,int row, int col){for(int i = 0; i < row; i++){//因为行不相等，判断列是否相等，斜线上是否相等if(x[i] == col || x[i] + i == col + row || x[i] – i == col – row)return false;}return true;}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
我不敢说我可以忘却，或者勇敢，坚强，等等等等一切堂皇而陈旧的字眼。
