回溯法解八皇后问题（递归和非递归，Go语言实现）
问题重现：
在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法？如果问题拓展到n*n，又有多少种摆法？
分析：
回溯法解8*8问题
棋盘横坐标i,纵坐标j，7>=i>=0且7>=j>=0，皇后摆法位置(i,j)
用pos[i]记录第i个皇后放的位置
分析：用0表示没有,用1表示已有
用a[i]表示第i行是否摆放了皇后（a取值在0~7）
用b[j]表示第j列是否摆法了皇后（b取值在0~7）
用c[j-i+7]正对角线是否摆放了皇后（c取值在0~14）
用d[i+j]斜对角线是否摆法了皇后（d取值在0~14）
优化：
a[i]这个判断条件可以省略，因为在取皇后的时候，皇后不能放在同一行，于是可以假定第i个皇后放到第j列，这里的第i个皇后的i就是所在行。
第i个皇后在第j列
for(j=0;j<8;j++){
if(i>7){
count++
打印当前解集
}
if( (i,j)位置对应abcd均表示为0 ){
置对应abcd为1
递归调用下一个
置对应abcd为0
}
}
非递归版本1
package main
import (
"fmt"
)
var pos, b [80]int
var c, d [150]int
/*置相应数组为n{0|1}*/
func putn(i, j, flag int) {
b[j], c[j-i+7], d[i+j] = flag, flag, flag
}
/*
*pos[i]=j表示第i行的皇后在第j列
*b[i]表示第i行是否放置了皇后，也就限定了每行只可能出现一个皇后，也就有每行都一定有且只有一个皇后
*c[j-i+7]表示主对角线是否放置了皇后
*d[i+j]表示次对角线是否放置了皇后
*0表示没有，1表示放置了皇后
*检查相应位置是否可以放置皇后，冲突时返回1
*/
func checkPos(i, j int) int {
if b[j] == 1 || c[j-i+7] == 1 || d[i+j] == 1 {
return 1
}
return 0
}
/*
*回溯非递归写法：八皇后问题 作者：天之
*/
func backTrackQueen(n int) int {
//传进来的n值为原值的(n-1)
count := 0 //统计摆法
i := 0 //已经放置了多少个皇后,也就是处理完了多少行
conflict := 0 //是否冲突,默认0没有冲突
for {
if conflict == 0 {
//没有冲突
if i == n {
//搜索到一个解
count++
//开始回溯，重新开始
for pos[i] == n {
//特别注明1：i=7,pos[7]=n时，i=7无需释放（见注明2）,并且只要i=7时才会执行这句
//如果颠倒位置，将会使得i=6时原位置不被释放，故而必须先i--，再释放
i--
/*if i == -1 {
//结束条件
return count
}*/
//释放空间，使得位置可以放
putn(i, pos[i], 0)
}
pos[i]++
} else {
//else if i < n，因为i是步增的，所以else 后的if i<n可以不要
//打上新标记,注明不可放
//特别指出2：i=7时并没有执行这条语句，因为在i=7时，只要找到合适位置就可以了，接着就是回溯了
putn(i, pos[i], 1)
//进入下一行第0列搜索
i++
pos[i] = 0
//直到i=7，已知试探
}
} else {
//发现冲突，并且搜索从0深度到了n
for pos[i] == n {
//特别注明3：这里和上面的还是有区别的,因为第i行根本还处于冲突中,所以必须先i--，再释放，
i--
if i == -1 {
//真实的结束出口，而且是必然的
return count
}
//释放空间，使得位置可以放
putn(i, pos[i], 0)
}
pos[i]++
}
conflict = checkPos(i, pos[i])
}
//return count
}
func main() {
fmt.Println(backTrackQueen(8 - 1))
}
非递归版本2
package main
import (
"fmt"
)
var col [9]int //col[j]=i,表示第j列的第i行放置了皇后
var row [9]int //row[i]=0表示第i行没有皇后
var b [17]int //0表示主对角线没有放皇后
var c [17]int //0表示次对角线没有放皇后
/*在指定位置设定新标志*/
func putn(num, n, flag int) {
row[col[num]] = flag
b[num+col[num]] = flag
c[n+num-col[num]] = flag
}
/*检查位置是否可用，可用返回0*/
func checkPos(num, n int) int {
if row[col[num]] == 1 || b[num+col[num]] == 1 || c[n+num-col[num]] == 1 {
return 1
}
return 0
}
/*
*回溯非递归写法：八皇后问题 作者：天之
*/
func backTrackQueen(n int) int {
count := 0 //统计摆法
//初始化
num := 1 //已经放置了的皇后数目
flag := 0 //0表示没有发生冲突
col[1] = 1 //第1列选第1个位置
col[0] = 0 //第0列数据不用
for num > 0 {
if flag == 0 {
//没有冲突
if num == n {
count++
//发生冲突,开始回退
for col[num] == n {
//num减到0的时候也就意味着结束了
num--
//清除之前的状态标记,释放位置
putn(num, n, 0)
}
col[num]++
} else {
//打上新的状态标记,表示不可再放
putn(num, n, 1)
//从下一列的第i个位置继续搜索
num++
col[num] = 1
}
} else {
//本列发生冲突并且搜到了n,开始回退
for col[num] == n {
num--
putn(num, n, 0)
}
//继续搜索本列下一个
col[num]++
}
flag = checkPos(num, n)
}
return count
}
func main() {
fmt.Println(backTrackQueen(8))
}
递归版本
package main
import (
"fmt"
)
//初始值默认都为0,为便于扩展，空间大小乘以了10
//pos[i]=j表示第i行皇后放在j位置
//用a[i]表示第i行是否摆放了皇后（a取值在0~7）
//用c[j-i+7]正对角线是否摆放了皇后（c取值在0~14）
//用d[i+j]斜对角线是否摆法了皇后（d取值在0~14）
var pos, b [80]int
var c, d [150]int
/*置相应数组为n{0|1}*/
func putn(i, j, n int) {
pos[i], b[j], c[j-i+7], d[i+j] = j, n, n, n
}
/*检查相应位置是否可以放置皇后*/
func checkPos(i, j int) int {
if b[j] == 1 || c[j-i+7] == 1 || d[i+j] == 1 {
return 0
}
return 1
}
/*打印皇后的位置*/
func printQueen(n int) {
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if pos[i] == j {
fmt.Print(1)
} else {
fmt.Print(0)
}
}
fmt.Println()
}
fmt.Println("==================")
}
/*
*最简洁回溯法之全排列解法：八皇后问题递归核心 作者：天之
*/
func queen(i, n int, count *int) {
if i > 7 {
//说明8皇后已经放好，也就是得到了解
*count++
printQueen(n)
//避免无用的搜索，应该立即返回
return
}
for j := 0; j < n; j++ {
if checkPos(i, j) == 1 {
putn(i, j, 1)
queen(i+1, n, count)
putn(i, j, 0)
}
}
}
func main() {
n, count := 8, 0
queen(0, n, &count)
fmt.Println(count)
}
有疑问加站长微信联系（非本文作者）
