九宫格问题（回溯法，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
}
有疑问加站长微信联系（非本文作者）
