day4 leetcode52 n皇后问题

n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上,并且使皇后彼此之间不能相互攻击。

给你一个整数 n ,返回 n 皇后问题 不同的解决方案的数量。

问题解析

经典的递归回溯算法,尝试向下去放下一步棋,不行就回溯

代码如下:

主方法调用
arr代表对应行的几号位下了棋
eg:arr[8] = 8,代表在第8行的第8列下了棋

public int totalNQueens(int n) {
        arr = new int[n];
        max = n;
        count = 0;
        check(0);
        System.out.println(count);
        return count;
    }

递归下棋,如果n==max代表得到一次答案,如果没有走到max就进行循环判断,对当前行的每一个位置进行判断,如果这一个位置可以下棋,就递归到下一行继续判断,如果整行都不满足,就会自动回溯.

public void check(int n) {
        if (n == max) {
            count++;
            return;
        } else {
            for (int i = 0; i < max; i++) {
                arr[n] = i;
                if (judge(n)) {
                    check(n + 1);
                }
            }
        }
    }

判断

private boolean judge(int n) {
        for (int i = 0; i < n; i++) {//判断和之前的皇后是否冲突,n代表现在这行,i代表之前放好的行
            if (arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[n] - arr[i])) {//判断是否是同一列或者是斜线上
                return false;
            }
        }
        return true;
    }

相关推荐

  1. day4 leetcode52 n皇后问题

    2024-05-16 09:28:10       4 阅读

最近更新

  1. .Net Core WebAPI参数的传递方式

    2024-05-16 09:28:10       0 阅读
  2. QT--气泡框的实现

    2024-05-16 09:28:10       0 阅读
  3. LeetCode 968.监控二叉树 (hard)

    2024-05-16 09:28:10       0 阅读
  4. leetcode热题100.完全平方数(动态规划进阶)

    2024-05-16 09:28:10       0 阅读
  5. leetcode328-Odd Even Linked List

    2024-05-16 09:28:10       0 阅读
  6. C 语言设计模式(结构型)

    2024-05-16 09:28:10       0 阅读
  7. v-if 与 v-show(vue3条件渲染)

    2024-05-16 09:28:10       0 阅读
  8. kafka防止消息丢失配置

    2024-05-16 09:28:10       0 阅读

热门阅读

  1. CyclicBarrier的 常用场景及使用示例

    2024-05-16 09:28:10       2 阅读
  2. list使用

    2024-05-16 09:28:10       4 阅读
  3. JVM线程和内存溢出问题排查思路

    2024-05-16 09:28:10       4 阅读
  4. Excel IF 公式 简要说明

    2024-05-16 09:28:10       4 阅读
  5. go的web开发框架gin(一)

    2024-05-16 09:28:10       4 阅读