leetcode中八皇后问题+java代码+回溯的解法

题目：
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例:

输入: 4
输出: [
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

解法：
回溯算法 ，在棋盘中放置棋子（皇后）的时候每次都检查一下是否符合要求。

package aleetcode.n_queen;

import java.util.ArrayList;

public class Solution2 {

    //static ArrayList<String[]> result;

    public ArrayList<String[]> solveNQueens(int n) {
        ArrayList<String[]> result = new ArrayList<String[]>();
        if(n <= 0)
            return result;
        int[][] arry = new int[n][n];
        findQueen(0,n,arry,result);
        return result;
    }


    public  void getString(int[][] arry,ArrayList<String[]> result){
        int num = arry[0].length;
        String[] resString = new String[num];
        for(int k=0;k<num;k++){
            resString[k] = "";
        }
        //int k = 0;
        for(int i=0;i<num;i++){
            for(int m=0;m<num;m++){
                if(arry[i][m] ==1){
                    resString[i] += "Q";
                }else{
                    resString[i] += ".";
                }
            }
            //System.out.println();
        }
        //System.out.println();
        result.add(resString);
    }


    // 核心函数
    public  void findQueen(int i,int n,int[][] arry,ArrayList<String[]> result){
        if(i>n-1){
          //  map++;
          //  print(arry);
            getString(arry,result);        // 如何能在这里返回，则必然是一种可以能的排列
            return;
        }

        for(int m=0;m<n;m++){
            if(check(i,m,arry)){
                arry[i][m] = 1;
                findQueen(i+1,n,arry,result);
                arry[i][m]=0;
            }
        }
    }


    public  boolean check(int k,int j,int [][]arry){
        for(int i=0;i<arry[0].length;i++){
            if(arry[i][j]==1){
                return false;
            }
        }
        for(int i=k-1,m=j-1; i>=0 && m>=0; i--,m--){//检查左对角线
            if(arry[i][m]==1){
                return false;
            }
        }
        for(int i=k-1,m=j+1; i>=0 && m<=arry[0].length-1; i--,m++){//检查右对角线
            if(arry[i][m]==1){
                return false;
            }
        }
        return true;
    }

    public   void print(int[][] arry){
        //System.out.println("方案"+map+":"+"\n");
        for(int i=0;i<4;i++){
            for(int m=0;m<4;m++){
                if(arry[i][m] ==1){
                    System.out.print("o ");
                }else{
                    System.out.print("+ ");

                }
            }
            System.out.println();
        }
        System.out.println();
    }

}

test函数入口：

public class main {
    public static void main(String[] args) {
        System.out.println("八皇后问题 ");
        //Solution.findQueen(0);
        // System.out.println("八皇后问题共有："+Solution.map+"种可能");
        //Solution2  mySolution2 = new Solution2();
       Solution1  mySolution2 = new Solution1();
        ArrayList<String[]> result = mySolution2.solveNQueens(4);
      //  System.out.println(result.toString());
        for(String[] tmp:result){
           // System.out.println(tmp.toString());
            for(String oneStr:tmp){
                System.out.print(oneStr+"\n");
            }
            System.out.println("\n\n");
        }
    }
}