之前简单了解过回溯算法，没有举例。今天来回顾一下，回溯算法有一套相对固定的核心逻辑。
if 满足条件 ：
跳出循环
for 条件 in 条件集合：
做出选择
backtrack()
撤销选择
if 语句用来判断是否达到跳出条件，达到就返回结果。 for 循环才是这段核心代码中的核心，先从条件池中做出选择，然后用剩余条件去做回溯， 整个结果全走完一遍，撤销选择，挑选第二个条件，再走一变。 举个例子就是 "abcd"四个字母的不同排序方法有多少种，就是先挑出a字母作为第一个的字母，然后用"bcd"充当第二次循环的条件池，然后再循环，一次类推。 循环完一轮后，跳出循环，再选择字母“b”做开头的第一个字母，继续循环。
以下是go的示例代码：
package main
import "fmt"
func helper(bt []byte, start int, str *[]string) {
if start == len(bt) {
*str = append(*str, string(bt))
} else {
for i := start; i <= len(bt)-1; i++ {
if i != start {
tmp := bt[start]
bt[start] = bt[i]
bt[i] = tmp
}
fmt.Println(str)
helper(bt, start+1, str)
if i != start {
tmp := bt[start]
bt[start] = bt[i]
bt[i] = tmp
}
}
}
}
func getAbc(s string) []string {
str := make([]string, 0)
helper([]byte(s), 0, &str)
return str
}
func main() {
fmt.Println(getAbc("abc"))
}
还有一个就是九宫格问题，就是从1-10中抽取数字，排列成3*3的九宫格，要求是任意方向的两个数字加起来必须是质数。 逻辑跟上面的全排列类似，首先定义两个list， 一个是1-9， 另一个是20以内的质数。for 循环 9 次， 每次选选定一个数字作为第一个，然后从剩余的数字中选择一个数字填充第二个格子，这里就多加了一步判断，判断是否前两个横竖都是两个数相加都是质数。还是go的代码示例：
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 Jiu
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}
func searchFromNum(n int) bool {
for i :=0; i < 9; i++ {
if n == num[i] {
return true
}
}
return false
}
func check(i 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
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)
}
以上代码都是我从网上摘取下来的。大体思路我是有了，但是让我自己复写不一定能写出来，抄写下来作为备忘。
