九宫格问题(回溯的多种写法,Go语言实现)

WAPWO · · 2517 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

九宫格问题(回溯法,Go语言实现)

 

问题重现:

有1~10十个数,从中选出不重复的9个数填入到九宫格,现要求相邻(上下、左右)的两数之和为质数,问有多少种填法?

此题比较简单,所以直接给代码了。

解法一

package main

import (
	"fmt"
)

var pos [9]int
var sub []int = []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
var num []int = []int{1, 2, 3, 5, 7, 11, 13, 17, 19}

/*从质数中查找,找到返回true*/
func searchFromNum(n int) bool {
	for i := 0; i < 9; i++ {
		if n == num[i] {
			return true
		}
	}
	return false
}

/*检验结果是否正确*/
func check(i, n int) bool {
	//纵向
	if i-3 >= 0 {
		if searchFromNum(pos[i]+pos[i-3]) == false {
			return false
		}
	}
	//横向
	if i%3 != 0 {
		if searchFromNum(pos[i]+pos[i-1]) == false {
			return false
		}
	}
	return true
}

var down, up int = 0, 9

/*填入1~10到九宫格的解,回溯法*/
func fillBox(i, n, r int, count *int) {
	if i == n {
		(*count)++
		for i := 0; i < r; i++ {
			for j := 0; j < r; j++ {
				fmt.Printf("%3d", pos[i*r+j])
			}
			fmt.Println()
		}
		fmt.Println("============")
		return
	}
	for j := down; j <= up; j++ {
		//先放入
		pos[i] = sub[j]
		if sub[j] != -1 && check(i, n) {
			sub[j] = -1
			fillBox(i+1, n, r, count)
			sub[j] = pos[i]
		}

	}
}

func main() {
	count := 0
	fillBox(0, 9, 3, &count)
	fmt.Println(count)
}

解法二

package main

import (
	"fmt"
)

var pos [9]int
var sub []int = []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
var num []int = []int{1, 2, 3, 5, 7, 11, 13, 17, 19}

/*从质数中查找,找到返回true*/
func searchFromNum(n int) bool {
	for i := 0; i < 9; i++ {
		if n == num[i] {
			return true
		}
	}
	return false
}

/*检验结果是否正确*/
func check(n int) bool {
	//行相邻
	for i := 0; i < n; i++ {
		for j := 0; j < n-1; j++ {
			if searchFromNum(pos[i*n+j]+pos[i*n+j+1]) == false {
				return false
			}
		}
	}
	//列相邻
	for j := 0; j < n; j++ {
		for i := 0; i < n-1; i++ {
			if searchFromNum(pos[i*n+j]+pos[(i+1)*n+j]) == false {
				return false
			}
		}
	}
	return true
}

var down, up int = 0, 9

/*填入0~8到九宫格的解,全排列(枚举)*/
func fillBox(i, n, r int, count *int) {
	if i == n {
		if check(r) {
			(*count)++
			for i := 0; i < r; i++ {
				for j := 0; j < r; j++ {
					fmt.Printf("%3d", pos[i*r+j])
				}
				fmt.Println()
			}
			fmt.Println("============")
		}
		return
	}
	for j := down; j <= up; j++ {
		if sub[j] != -1 {
			pos[i] = sub[j]
			sub[j] = -1
			fillBox(i+1, n, r, count)
			sub[j] = pos[i]
		}

	}
}

func main() {
	count := 0
	fillBox(0, 9, 3, &count)
	fmt.Println(count)
}

回溯非递归解法:

package main

import (
	"fmt"
)

var num [9]int = [9]int{1, 2, 3, 5, 7, 11, 13, 17, 19}
var pos [9]int //存放连续的1~10
var sum, down, up, r int = 9, 0, 10, 3

func backTrack() int {
	sum--
	isNoConflict := true //默认true无冲突
	count := 0           //统计数0
	i := 0
	pos[0] = 1 //起始值是从1开始
	for {
		if isNoConflict {
			if i == sum {
				count++
				for i := 0; i < r; i++ {
					for j := 0; j < r; j++ {
						fmt.Printf("%3d", pos[i*r+j])
					}
					fmt.Println()
				}
				for pos[i] == up {
					i--
					if i == -1 {
						return count
					}
					//此时的i占据的值根本就没有参与check(),所以值是多少并不重要了,也就等于撤销了之前的占用
				}
				pos[i]++
			} else {
				i++
				pos[i] = 1 //起始值是从1开始
			}
		} else {
			//发生冲突
			for pos[i] == up {
				i--
				if i == -1 {
					return count
				}
				//此时的i占据的值根本就没有参与check(),所以值是多少并不重要了,也就等于撤销了之前的占用
			}
			pos[i]++
		}
		isNoConflict = check(i)
	}

}

func main() {
	fmt.Println(backTrack())
}

/*检验结果是否正确*/
func check(i int) bool {
	//搜索当前值是否已在前面使用过了
	for j := 0; j < i; j++ {
		if pos[j] == pos[i] {
			return false
		}
	}
	//纵向  
	if i-3 >= 0 {
		if searchFromNum(pos[i]+pos[i-3]) == false {
			return false
		}
	}
	//横向  
	if i%3 != 0 {
		if searchFromNum(pos[i]+pos[i-1]) == false {
			return false
		}
	}
	return true
}

/*从质数中查找,找到返回true*/
func searchFromNum(n int) bool {
	for i := 0; i < 9; i++ {
		if n == num[i] {
			return true
		}
	}
	return false
}

 


有疑问加站长微信联系(非本文作者)

本文来自:CSDN博客

感谢作者:WAPWO

查看原文:九宫格问题(回溯的多种写法,Go语言实现)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

2517 次点击  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传