3.6 回溯

1. 回溯是什么

• 每一步都选择一条路出发，能进则进，不能进则退回上一步（回溯），换一条路再试

2. 八皇后问题

• 

2.1. 思路

• 暴力法
  • 从 64 个格子中选出任意 8 个格子摆放皇后，检查每一种摆法的可行性
    • 一共有种摆法
  • 每一行只能放一个皇后，那么只有种摆法
• 回溯+剪枝

2.2. 实现

package 回溯

import (
	"fmt"
	"my_algorithm/util"
)

type NQueens struct {
	//存放每一个皇后的位置
	//下标是第row行的皇后，值是存放在第几列
	queensLocation []int
	//一共由多少种摆法
	ways int
	//几皇后
	n int
}

func NewNQueens(n int) *NQueens {
	return &NQueens{
		n:              n,
		queensLocation: make([]int, n, n),
		ways:           0,
	}
}

func (n *NQueens) placeQueens() {
	if n.n < 1 {
		return
	}

	n.place(0)
}

//摆放第row个皇后，也是摆放到第row行
func (n *NQueens) place(row int) {
	//全部都摆完了，那么ways +1
	if row == len(n.queensLocation) {
		n.ways++
		return
	}

	//每一列都尝试下是否合法
	for col := 0; col < len(n.queensLocation); col++ {
		if n.isValid(row, col) {
			//第row行的皇后存放在第col列
			n.queensLocation[row] = col
			//继续摆放下一行的皇后
			n.place(row + 1)
		}
	}
}

//同一行、同一列、同一斜线不能摆放两个皇后
func (n *NQueens) isValid(row int, col int) bool {
	for i := 0; i < row; i++ {
		//同一列
		//如果之前已经由皇后放在第i列了，那么不能摆放
		if n.queensLocation[i] == col {
			return false
		}

		//同一斜线
		// 第i行的皇后根第row行第col列格子处在同一斜线上
		// 45度角斜线: y-y0 = (x-x0), 则 (y-y0)/(x-x0) = 1, 表示为45度角的斜线
		if util.Abs(col-n.queensLocation[i]) == row-i {
			return false
		}
	}

	return true
}

func (n *NQueens) String() string {
	s := fmt.Sprintf("ways=%v, data={\n", n.ways)
	for row := 0; row < len(n.queensLocation); row++ {
		for col := 0; col < len(n.queensLocation); col++ {
			if n.queensLocation[row] == col {
				s += "1 "
			} else {
				s += "0 "
			}
		}
		s += "\n"
	}
	s += "}"
	return s
}

2.2.1. 测试

func TestEightQueens(t *testing.T) {
	fmt.Println(NewNQueens(4))
}

3. 参考

• 【恋上数据结构】回溯、剪枝（八皇后、n皇后）、LeetCode51.N皇后、LeetCode52.N皇后 II_Jerry House-CSDN博客