欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-03-13 23:38:08
...

题目:
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
leetcode中八皇后问题+java代码+回溯的解法
上图为 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");
        }
    }
}
相关标签: 刷题