八皇后问题分析和 golang 求解

栏目: Go · 发布时间: 5年前

内容简介:问题:在一个8*8大小的国际象棋棋盘上放置8个皇后棋子,使得所有的皇后都是安全的即任意两个皇后都无法攻击到对方)。分析:按照国际象棋的规则,皇后的攻击方式是横,竖和斜向。

问题:在一个8*8大小的国际象棋棋盘上放置8个皇后棋子,使得所有的皇后都是安全的即任意两个皇后都无法攻击到对方)。

分析:

按照国际象棋的规则,皇后的攻击方式是横,竖和斜向。

皇后可以攻击到同一列所有其它棋子,因此可推导出每1列只能存在1个皇后,即每个皇后分别占据一列。棋盘一共8列,刚好放置8个皇后。

为了摆放出满足条件的8个皇后的布局,可以按如下方式逐步操作:

1. 在第0列找到一个位置放置第1个皇后;
2. 在第1列找到一个位置放置第2个皇后;
3. 在第2列找到一个位置放置第3个皇后;
4. 对第3,4,5,6,7,8列都执行放置操作;
5. 当执行完“在第7列找到一个放置第8个皇后”这一操作完毕后,问题求解完毕。

观察1,2,3,4 这些操作步骤,可以发现是一个重复的动作,抽象一下,即“在第 n 列放下第 n+1 个皇后”,n 从0到7。看起来我们需要写一个这样的过程:

func put(col int)

显然,需要使得 col 从0到7每次+1,一共执行8次 put。

可以考虑用循环或着递归来完成它,由于一般来说,使用递归解决问题的思路会更加自然和简单,因此我们选择使用递归。那么 put 看起来可能是这样的:

func put(col int) {
    // 执行某些操作
    put(cor+1)
}

我们猜测递归的启动方式可能是从 col = 0 开始,那么调用 put(0)

作为程序入口的 main 函数看起来是这样的:

func main() {
  put(0)
}

接下来我们需要考虑递归如何结束。分析步骤5可知,当 col==8 时递归结束。因此我们继续写 put 的代码。

func put(col int) {
    if col == 8 {
        return
    }
    // 执行某些操作
    put(col+1)
}

递归程序的框架看起来已经搭好了,接下来我们要求解的子问题是

在第 col 列,找到一个位置,放下第 col+1 个皇后。

这个子问题的约束条件是:

放下皇后之后,棋盘上没有任意两个皇后可以攻击到对方,即我们找到的这个位置是安全的。

由于每次放下皇后时,只有8个位置可选,因此在某行放下皇后的操作步骤如下:

1. 在第0行放下皇后;
2. 检测当前位置是否安全;
3. 如果安全,则子问题求解结束;
4. 如果不安全,则在下一个位置放皇后;
5. 回到步骤3,继续。

看起来这是一个循环问题,写下代码:

for pos = 0; pos < 8; pos++ {
    // 在 pos 处放下皇后
    if safe() {
        // 子问题求解结束
    }
}

第3步找到安全位置后,我们就去后一列找放置下一个皇后的位置了,即接下来调用 put(col+1),代码如下:

for pos := 0; pos < 8; pos++ {
    // 在 pos 处放下皇后
    if safe() {
        put(col+1)
    }
}

现在看一下目前的代码。

func put(col int) {
    if col == 8 {
        return
    }

    for pos := 0; pos < 8; po++ {
        // 在 pos 处放下皇后
        if safe() {
            put(col+1)
        }
    }
}

查看代码之后我们发现,代码里没有任何东西来表示棋盘,以及皇后的位置。看起来我们需要做点什么。

我们需要选用某个数据结构来表示棋盘和皇后的位置。

棋盘是由64个格子组成的,排列布局为8*8。第一反应是可以用一个二维数组来表示,下标是格子的坐标,数组元素选用 bool 型, true 表示此处放置了皇后, false 表示空格子。

初始时,数组中的64个元素都为 false, 程序运行之后,其中8个元素的值变为 true。

但看起来似乎有点浪费,而且处理多维数组的下标比较麻烦。我们可以再想想,是否可以简化一下棋盘的表示。

让我们再用自然语言描述一下最终求出的解,也许是这样的:

第0列的第a行有皇后
第1列的第b行有皇后
第2列的第c行有皇后
...
第7列的第h行有皇后

一维数组 [a, b, c, d, e, f, g, h] 就能表示上面这个解的全部信息。不妨先用简单的试试看。

对于 go 语言,slice 是比数组好得多的选择,我们用一个类型为 [8]int 的变量 boards 来表示棋盘。现在代码如下:

func put(col int) {
    if col == 8 {
        fmt.Println(boards) // 输出答案
        return
    }

    for pos := 0; pos < 8; po++ {
        boards[col] = pos // 在 pos 处放下皇后
        if safe() {
            put(col+1)
        }
    }
}

出于遵循“变量的作用域尽可能小”这一设计原则,我们把 boards 这个类型为[8]int 的 slice 作为 put 的参数。现在代码如下:

func put(boards [8]int, col int) {
    if col == 8 {
        fmt.Println(boards) // 输出答案
        return
    }

    for pos := 0; pos < 8; po++ {
        boards[col] = pos // 在 pos 处放下皇后
        if safe() {
            put(boards, col+1)
        }
    }
}

初始时,我们需要一个空的棋盘。在 main 函数再加点东西。

func main() {
    boards := [8]int{}
    put(boards, 0)
}

有了可以表示棋盘的数据对象 boards 之后,我们来完成 safe 这个函数。

boards 作为 safe 的参数,接下来我们要检验棋盘上 pos 这个位置是否安全。

咋一看,我们可能想到遍历整个棋盘,看看是否有任意两个皇后可以攻击。但我们再阅读一下已经写好的代码并仔细回顾最初的解题操作步骤,代码显示我们的操作逻辑是:

1. 在第n行的 pos (pos从0到7) 放下皇后
2. 检测 pos 是否安全
3. ...

我们再看看“外”一层的操作步骤:

1. 在第0列找到一个位置放置第1个皇后;
2. 在第1列找到一个位置放置第2个皇后;
3. ...
4. 在第6列找到一个位置方式第7个皇后;
5. ...

我们发现,按照这个操作步骤,当我们在第 n 列寻找安全格子 pos 时,我们只需要检查这个 pos 是否会被前面列的那些皇后们攻击到,而这些皇后们本身彼此都是不会互相攻击。

那么检查的操作步骤如下:

1. 获取第0列皇后的位置;
2. 检查是否会攻击到第n列的 pos;
3. 如果能攻击到,则不安全;
4. 如果安全,则循环计数加1,回到步骤1继续;
5. ...
6. 循环的的最后一次时检查第 n-1 列皇后是否会攻击到第n列的 pos,如果依然攻击不到,那么我们能确认 pos 是安全的。

因此,safe 函数的实现如下:

func safe(boards [8]int, col int, pos int) bool {
    for c := 0; c < col; c++ {
        if isAttack(boards, c, col, pos) {
            return false
        }
    }
    return true
}

需要传递 boards , col 和 pos 三个参数。返回 bool 值,false 表示不安全, true 表示安全。

代码反映了一个事实:只要有一个皇后能攻击到 pos ,则 pos 就是不安全的,只有检车了前面 n-1 个皇后,它们全都不能攻击 pos ,我们才可以说 pos 是安全的。

现在 put 的代码如下:

func put(boards [8]int, col int) {
    if col == 8 {
        fmt.Println(boards) // 输出答案
        return
    }

    for pos := 0; pos < 8; pos++ {
        boards[col] = pos // 在 pos 处放下皇后
        if safe(boards, col, pos) {
            put(boards, col+1)
        }
    }
}

接下来我们着手实现 isAttack。

func isAttack(boards [8]int, c int, col int, pos int) bool {
    if boards[c] == pos {
        return true
    }
    if pos-boards[c] == c-col {
        return true
    }
    if pos-boards[c] == col-c {
        return true
    }
    return false
}

这个 function 需要4个参数让我们嗅到了一点不好的味道,其中有3个参数都是从 safe 延续而来的,我们来看看调用 safe 的代码片段:

...
        boards[col] = pos // 在 pos 处放下皇后
        if safe(boards, col, pos) {
            ...
        }

boards, col, pos 是存在关联的,在执行完 boards[col] = pos 之后,boards[col] 的值就等于 pos 了,因此我们可以去掉 pos 这个参数,用 boards[col] 替换它。

最后再检查一遍,代码里多处出现8这个 magic number,这显然不好。

8是棋盘的尺寸,即 boards 这个 slice 的长度,我们动手修改 boards 的类型和初始化方式。

新的初始化代码如下:

size := 8
    boards := make([]int, size)

现在,magic number 可以用 len(boards) 来替代了。

我们意外地发现,这次重构后,程序可以求解任意尺寸棋盘的皇后问题了。

最终完整代码如下:

package main

import "fmt"

func main() {
    queen(8)
}

func queen(size int) {
    boards := make([]int, size)
    put(boards, 0)
}

func put(boards []int, col int) {
    size := len(boards)
    if col == size {
        fmt.Println(boards) // 输出答案
        return
    }

    for pos := 0; pos < size; pos++ {
        boards[col] = pos // 在 pos 处放下皇后
        if safe(boards, col) {
            put(boards, col+1)
        }
    }
}

func safe(boards []int, col int) bool {
    for c := 0; c < col; c++ {
        if isAttack(boards, c, col) {
            return false
        }
    }
    return true
}

func isAttack(boards []int, c int, col int) bool {
    if boards[c] == boards[col] {
        return true
    }
    if boards[col]-boards[c] == c-col {
        return true
    }
    if boards[col]-boards[c] == col-c {
        return true
    }
    return false
}

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

痛点

痛点

马丁·林斯特龙 / 陈亚萍 / 中信出版集团股份有限公司 / 2017-4-1 / CNY 49.00

互联网经济迅猛发展,大数据成为分析用户需求的一种惯性路径。世界首席品牌营销专家林斯特龙则指出,大数据连接了千百万的数据点,可以准确地产生相互关系。但是,当人类按照自己的习惯行动时,大数据分析通常不会十分准确。所以挖掘用户需求时,在大数据之外,更重要的是通过对一个小群体的亲身观察和小数据常识,捕捉到这个社会群体所体现出的文化欲望。满足这些用户需求,击中痛点,则意味着将掌握无限的商机。一起来看看 《痛点》 这本书的介绍吧!

URL 编码/解码
URL 编码/解码

URL 编码/解码

SHA 加密
SHA 加密

SHA 加密工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具