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

一天一大 lee(N 皇后)难度:困难-Day20200903

程序员文章站 2022-05-08 14:27:35
...

一天一大 lee(N 皇后)难度:困难-Day20200903

题目:

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

一天一大 lee(N 皇后)难度:困难-Day20200903

上图为 8 皇后问题的一种解法。

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

每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例:

输入:4
输出:[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

提示:

  • 皇后彼此不能相互攻击,也就是说:任何两个皇后都不能处于同一条横行、纵行或斜线上。

抛砖引玉

一天一大 lee(N 皇后)难度:困难-Day20200903

翻一下题目的意思:

出入 N,要在长宽为 N 的矩阵中放入 N 个 Q,且每个 Q 不能处在同行同列也不能处在对角线上

思路

第一下看示例的输出其实有点不符合直觉,第一反应应该是从第一位开始放 Q:

Q . . .
. . Q .
. . . .
. . . .

[0,2] -> [ [0,0],[1,2] ]

这个时候就知道为什么输出不是从开始就放 Q,因为如果在某些位置放置了 Q,后续可能不能放下 n 个 Q

那么此时就有两种方式开启行的枚举:

  1. 回溯到开始从新枚举
  2. 就当前位回溯开始新的枚举

如果采用第 1 种方式回溯,可能在当前起始填充位下存在正确的解法,直接切换了起始位就会造成解法丢失,则采用的第 2 种方法回溯

回溯第二个 Q,给其重新放置位置

Q . . .
. . . Q
. Q . .
. . . .

[0,3,1] -> [ [0,0],[1,3],[2,1] ]

还是放置不下 4 个 Q,说明枚举了第二个 Q 的位置还是不能满足条件,次数枚举了 Q 起始位置为[0,0]的组合,确定起始位置为[0,0]不存在正解

继续向后枚举起始位置

. Q . .
. . . Q
Q . . .
. . Q .

[1,3,0,2] -> [ [0,1],[1,3],[2,0],[3,2] ]

得到一种解法,记录下拉继续枚举…

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {
  let _result = Array.from({length:n,()=>Array(n).fill('.')}),
    tmp = [];

  dfs(tmp)

  function dfs(tmp) {
    if (tmp.length === n) {
      for (let i = 0; i < n; i++) {
        const s = Array(n).fill('.').splice(tmp[i], 1, 'Q').join('')
        _result.push(s)
      }
      return
    }

    for (let i = 0; i < n; i++) {
      if (isValid(tmp, i)) {
        // 遇到满足“不能相互攻击”的点就先占着后继续安放下一个Q
        tmp.push(i)
        dfs(tmp)
        // 回溯已经安放的Q
        tmp.pop()
      }
    }
  }

  // 判断新的位置是否满足“不能相互攻击”
  function isValid(tmp, Ny) {
    // 传入校验的坐标:[Nx,Ny]
    let Nx = tmp.length
    for (let x = 0; x < Nx; x++) {
      let y = tmp[x]
      // 不同列,因为所有做行一定不同行,不在斜对角上[注:斜对角判断]
      if (y === Ny || x - y === x - Ny || x + y === x + Ny) {
        return false
      }
    }
    return true
  }

  return _result
}

注:斜对角判断

a * b
* A *
c * d

元素 A ->[1,1]的斜对角有:

  1. a->[0,0]
  2. b->[2,0]
  3. c->[0,2]
  4. d->[2,2]

坐标[x,y]的斜对角坐标[i,j]都满足 x-y=== i-j 或者 x+y===i+j

博客: 小书童博客

每天的每日一题,写的题解会同步更新到公众号一天一大 lee 栏目
欢迎关注留言

公号: 坑人的小书童

一天一大 lee(N 皇后)难度:困难-Day20200903