八皇后问题详细推导(递归和非递归,Go语言实现)

回溯法解八皇后问题(递归和非递归,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)
}

本文来自:CSDN博客

感谢作者:WAPWO

查看原文:八皇后问题详细推导(递归和非递归,Go语言实现)

• 编辑
• 预览