# 九宫格问题（回溯的多种写法，Go语言实现）

WAPWO · · 2101 次点击 · · 开始浏览

```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
}
```

0 回复

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、``单行代码``
• 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传

```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
}
```