N皇后问题

package com.lagou.edu.autodeliver;

import java.util.*;


public class Solution {

    // 存放下棋的记录
    int[] arr;
    // 棋盘大小
    int n;
    // 记录摆法数量
    int count;

    /**
     *
     * @param n int整型 the n
     * @return int整型
     */
    public int Nqueen (int n) {
        // write code here
        // 初始化
        this.n = n;
        this.arr = new int[n];
        execute(0);
        return count;
    }

    /**
     * rowNum,当前下棋的行
     */
    public void execute (int rowNum) {
        if(rowNum==n){
            System.out.println(Arrays.toString(arr));
            count++;
            return;
        }

        // j 代表列,每一列都要尝试放棋子
        for(int j=0; j<n; j++) {
            // 检查这个位置能不能放棋子
            if(judge(rowNum, j)) {
                arr[rowNum] = j;
                execute(rowNum+1);
            }
        }
    }

    public boolean judge(int n, int j) {
        for(int i=0;i<n;i++) {
            // arr[i]==j 表示在同一列
            // Math.abs(n-i)==Math.abs(j-arr[i]) 表示x和y是对角线
            if(arr[i]==j || Math.abs(n-i)==Math.abs(j-arr[i])){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().Nqueen(8));
    }
}

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容