寒光博客

[CC150]n皇后问题 dfs 不回溯
问题描述 请设计一种算法,解决著名的n皇后问题。这里的n皇后问题指在一个n*n的棋盘上放置n个棋子, 使得每行每列...
扫描右侧二维码阅读全文
05
2019/08

[CC150]n皇后问题 dfs 不回溯

问题描述

请设计一种算法,解决著名的n皇后问题。这里的n皇后问题指在一个n*n的棋盘上放置n个棋子,
使得每行每列和每条对角线上都只有一个棋子,求其摆放的方法数。

分析

精髓在check
rec[i]=col 判断同一列嘛 行就不用判断 因为 row+1 只判断 当前位置和上一行的皇后
正反斜线判断


i + rec[i] == row + col
i - rec[i] == row - col

对应俩坐标 x+y 相同 就是 在同一条斜线上
对应俩坐标 x-y 相同 就是 在同一条斜线上

代码

package BlueCup.Seven_recursion;

import java.util.Scanner;

import static java.lang.System.out;

public class Dfs4N皇后 {
    static int n;
    static int[] rec;
    static int cnt = 0;

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        n = cin.nextInt();
        rec = new int[n];//记录皇后的位置
        dfs(0);
        System.out.println(cnt);
    }

    /**
     * @param row 正在处理的行
     */
    private static void dfs(int row) {
        if (row == n) {
            cnt++;
            return;
        }
        for (int col = 0; col < n; col++) {//皇后所在行的位置(依次每个列防止皇后)
            if (check(rec, col, row)) {//检查位置 是否与之前的皇后冲突
                rec[row] = col;//标记皇后
                dfs(row + 1);
            }
        }
    }

    /**
     * 
     * @param rec 皇后的位置 索引位行 值该位置
     * @param col 所在行的位置 i-->col 所在列的位置
     * @param row 所处的行
     * @return 是否可以在该位置防止皇后
     */
    private static boolean check(int[] rec, int col, int row) {
        for (int i = 0; i < row; i++) {//遍历行
            if (rec[i] == col) {//列相同了
                return false;
            }
            if (i + rec[i] == row + col) {//正斜线
                return false;
            }
            if (i - rec[i] == row - col) {//反斜线
                return false;
            }
        }
        return true;
    }
}

GitHub

本文作者:Author:     文章标题:[CC150]n皇后问题 dfs 不回溯
本文地址:https://dxoca.cn/Algorithm/223.html       百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:August 6th, 2019 at 05:58 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment Cancel reply

9 comments

  1. 把所有几何对称的情况都单独算,算8次吗?实际情况只有cnt/8种吗?

    1. Dxoca
      @灵

      我也在想 几何对称 是不是可以在 col =n/2 的时候 停下来 cnt*2 就是结果

      1. @Dxoca

        旋转

        1. @灵

          还有对称后旋转

          1. Dxoca
            @灵

            嗯 的确哦,,,

    2. Dxoca
      @灵

      你是说 n=几,,,

  2. Dxoca

    思考 为什么可以不回溯 在 32行j加 rec[i]=-1

    1. Dxoca
      @Dxoca

      明白了 为什么不回溯 因为 res是一位数组 当同样的一行第k(k>1)次扫描到的时候 res[i]就会更新新的数据 所以没必要回溯 新扫描会覆盖旧值 且check是 在皇后 左上 右上 和 所在列判断的 所以无需 回溯 妙啊 妙啊~!!

      1. Dxoca
        @Dxoca

        check的永远的 之前的数据