N皇后问题（Java深度优先递归解法）_n皇后问题java

1. 问题描述

N皇后问题是在N×N的棋盘上放置N个皇后，任意两个皇后不在同一行、同一列和同一斜线。

2. 解题思路

对于N×N棋盘上的点，第一行的点比较特殊，因为我们会以他们为根去向下搜索。如下

上图中，0图的解数仅与它的子节点有关（0的另外两个子节点未画出）；图1的解的数量也仅与它的子节点2、3的解数有关；第四层节点的解数为1。根据这个原理可以对每个节点设计递归函数hasSolution()，其返回值为该节点的解的个数。

3. 代码

3.1定义一个类Location表示棋子位置

3.2定义isOK(ArrayList<Location> board, Location location)判断放入当前位置的棋子是否符合要求

3.3定义int hasSolution(Location location, int n,ArrayList<Location> board)求对于给定棋盘的当前位置的解数；

3.4定义queens(int n)求n个皇后的解数。函数中调用 hasSolution求得棋盘第一行每个位置的解数，然后求和得到最终结果

package com.xiexun.Solutions;
 
import java.util.*;
 
public class Solution4 {
 
    class Location {
        public int x;
        public int y;
 
        public Location() {
        }
 
        public Location(int x, int y) {
            this.x = x;
            this.y = y;
        }
 
        @Override
        public int hashCode() {//hashcode必须重写
            return Objects.hash(x, y);
        }
    }
 
    
 
 
 
    static boolean isOK(ArrayList<Location> board, Location location) {
        if (board.size() == 0) return true;//棋盘没有棋子，一定为真
 
        boolean flag = true;
        for (int i = 0; i < board.size(); i++) {
            if (location.x == board.get(i).x ||//同一行
                    location.y == board.get(i).y ||//同一列
                    Math.abs(location.x - board.get(i).x) == Math.abs(location.y - board.get(i).y)) {//同一斜线
                flag = false;
            }
        }
        return flag;
    }
 
 
 
 
 
    public int hasSolution(Location location, int n,ArrayList<Location> board) {
 
        if (location.x == n - 1) return 1;//location处于最底层
        else {
            board.add(location);//向棋盘添加当前位置；此时location一定合法，因为只有合法才会执行hasSolution()
            int thisSolution=0;
            Location l = new Location();
            for (int i = 0; i < n; i++) {
                l.x = location.x + 1;
                l.y = i;
                if(isOK(board,l)){//如果将l代表的位置加入棋盘可行的话
                    thisSolution+=hasSolution(l,n,board);//该节点的解数等于它所以可行的子节点的解数之和
                }
            }
            board.remove(location);//当前节点的解数已经求出；将当前位置的棋子移除棋盘
            return thisSolution;
        }
    }
 
 
 
 
 
    public int queens(int n) {
            ArrayList<Location> board = new ArrayList<>();//定义棋盘
            Stack<Location> possibleQi = new Stack<>();
    
            //加入第一行的所有位置到 possibleQi
            for (int i = 0; i < n; i++) {
                Location l = new Location(0, i);
                possibleQi.add(l);
            }
    
            int n_Solution = 0;
    
            for(Location l:possibleQi){
                n_Solution+=hasSolution(l,n,board);//对于当前位置的棋子和给定的棋盘、n，求当前位置棋子存在的解数
            }
            return n_Solution;
        }
    
}
 

3.5定义main函数执行queens(n)

import java.util.Scanner;
 
public class App {
    public static void main(String[] args) {
        Solution4 s = new Solution4();
        Scanner scanner=new Scanner(System.in);
        int n = scanner.nextInt();
 
        System.out.println(s.queens(n));
    }
}