当前位置: 首页 > article >正文

学习记录:js算法(九十):N皇后

文章目录

    • N 皇后
      • 思路一

N 皇后

按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

图一:
在这里插入图片描述

示例 1:图一
输入:n = 4
输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释:如上图所示,4 皇后问题存在两个不同的解法。

示例 2:
输入:n = 1
输出:[["Q"]]

思路一

function solveNQueens(n) {
  const solutions = [];
  const board = new Array(n).fill(-1); // 初始化棋盘,-1 表示未放置皇后

  function isSafe(row, col) {
    // 检查列是否有冲突
    for (let i = 0; i < row; i++) {
      if (board[i] === col || Math.abs(board[i] - col) === row - i) {
        return false;
      }
    }
    return true;
  }

  function backtrack(row) {
    if (row === n) {
      // 收集解
      const solution = [];
      for (let i = 0; i < n; i++) {
        const line = '.'.repeat(board[i]) + 'Q' + '.'.repeat(n - board[i] - 1);
        solution.push(line);
      }
      solutions.push(solution);
      return;
    }

    for (let col = 0; col < n; col++) {
      if (isSafe(row, col)) {
        board[row] = col; // 放置皇后
        backtrack(row + 1); // 递归到下一行
        board[row] = -1; // 清除该行皇后,进行回溯
      }
    }
  }

  backtrack(0); // 开始从第一行放置皇后
  return solutions;
}

讲解
N 皇后问题是一个经典的回溯问题,目标是在一个 N×N 的棋盘上放置 N 个皇后,使得没有两个皇后互相攻击。也就是说,任何两个皇后不能在同一行、同一列或同一对角线上。

  1. 初始化:创建一个棋盘矩阵,可以用一个一维数组表示,其中的元素值代表该皇后所在的列,下标则代表行。
  2. 递归函数:定义一个递归函数 backtrack(row),用于尝试在第 row 行放置皇后。在这个函数中,检查每一列是否可以放置皇后,如果可以,则放置皇后并递归到下一行;如果不可以,则跳过。
  3. 冲突检测:在每一步尝试放置皇后之前,需要检查是否与已放置的皇后发生冲突。这包括检查同一列和两个对角线方向。
  4. 回溯:当某一行无法放置皇后时,回溯至上一层,即回退到上一行重新选择列的位置。
  5. 终止条件:如果到达了最后一行并且成功放置了皇后,那么就找到了一个有效的解,将其添加到结果集中。

http://www.kler.cn/a/388525.html

相关文章:

  • 反向代理-缓存篇
  • 杨振宁大学物理视频中黄色的字,c#写程序去掉
  • grpc的负载均衡
  • 【JavaWeb后端学习笔记】Spring全局异常处理器
  • Qt 安装Qt Serial Port
  • 环境兼容: Vue3+ELement-plus
  • Spring Boot 的核心注解
  • SH3001六轴 学习1
  • 【Vue】-组件开发
  • 【Vue】Vue3.0(十八)Vue 3.0中‘props‘一种使用频率最高的通信方式(全面解析)
  • MML 中使用 libevent +std::async unix socket domain 进程间通信
  • RT-Thread 配置工具
  • 英国留学论文写作中复合句式基础知识讲解
  • 算法复杂度
  • 【SpringMVC】记录一次Bug——mvc:resources设置静态资源不过滤导致WEB-INF下的资源无法访问
  • W3C HTML 活动
  • springboot使用aop防御用户重复请求
  • Centos Linux 7 搭建邮件服务器(postfix + dovecot)
  • cv2.threshold利用OSTU方法分割图像的前景和背景
  • 从文本到图像:AIGC 如何改变内容生产的未来
  • 羲和数据集收集器1.0
  • Leetcode 3347. Maximum Frequency of an Element After Performing Operations II
  • 【k8s】ClusterIP能http访问,但是不能ping 的原因
  • 「C/C++」C/C++STL篇 之 数组赋值给std::vector多种方法
  • Ubuntu 的 ROS 2 操作系统安装与测试
  • 基于Diodes全新的140瓦PD3.1超高功率密度GaN充电器解决方案