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

N皇后问题---采用深度优先搜索算法求解

程序员文章站 2022-03-03 11:13:35
...

一.问题描述

     将棋子放在N*N的棋盘中,要求两个棋子不能在同一列,同一行及同一斜对角线上

二.代码

  

import java.util.HashMap;
import java.util.Map;

public class Queen {
    private int count = 0;

    private Integer n = 0;

    //棋子已有的坐标
    private Map<Integer, Integer> location = new HashMap<>();
    private Map<Integer, Integer> reverseLocation = new HashMap<>();  //坐标反转
    private static final Integer UNCAPTURED = 0;

    private static final Integer CAPTURED = 1;


    private int[][] chessboard;

    Queen(int n) {
        this.n = n;
        this.chessboard = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                chessboard[i][j] = UNCAPTURED;
            }
        }
    }

    private void dfs(int depth) {
        if (depth == n) {
            System.out.println("resolution :"+count+" start *****************");
            for (Map.Entry<Integer, Integer> entry : location.entrySet()) {
                System.out.println("x is:"+entry.getKey()+";y is:"+entry.getValue());
            }
            System.out.println("resoluction :"+count+" end ********");
            count++;
            return;
        }
        for (int i = 0; i < n; i++) {
            if (isSatisfied(depth, i)) {
                location.put(depth, i);
                reverseLocation.put(i, depth);
                dfs(depth + 1);
                location.remove(depth);
                reverseLocation.remove(i);
            }
        }
    }

    public int getCount() {
        dfs(0);
        return count;
    }

    private boolean isSatisfied(Integer i, Integer j) {
        //在同一行或同一列
        if (location.containsKey(i) || reverseLocation.containsKey(j)) {
            return false;
        }

        for (Map.Entry<Integer, Integer> entry : location.entrySet()) {
            //在斜对角线上
            if (Math.abs(entry.getKey() - i) == Math.abs(entry.getValue() - j)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Queen queen = new Queen(4);
        System.out.println(queen.getCount());
    }


}

 

相关标签: 数学与算法