内容简介:问题:在一个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 }
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。