八皇后

八皇后问题

八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当n = 1或n ≥ 4时问题有解。

使用回溯法求解八皇后问题

可以用一个向量x(x1, x2, x3, x4...xn)表示n个皇后的位置：xi表示第i个皇后在第i行的位置。

State Space Tree

代码

package main

import "fmt"

func main() {
	fourQueen := solveNQueens(4)
	for _, v := range fourQueen {
		for _, vv := range v {
			fmt.Println(vv)
		}
		fmt.Println("------------------------")
	}

	eightQueen := solveNQueens(8)
	for _, v := range eightQueen {
		for _, vv := range v {
			fmt.Println(vv)
		}
		fmt.Println("------------------------")
	}
}

func solveNQueens(n int) (ans [][]string) {
	var backtrack func([]int)
	backtrack = func(vector []int) {
		// 递归终止条件
		if isConflict(vector) {
			return
		} else if len(vector) == n {
			ans = append(ans, output(vector))
			return
		}

		for i := 0; i < n; i++ {
			newVector := make([]int, len(vector))
			copy(newVector, vector)
			newVector = append(newVector, i)
			backtrack(newVector)
		}
	}

	// vector[i]表示第i个皇后在第i行的位置
	var vector []int
	backtrack(vector)
	return
}

// 所有的皇后是否有冲突
func isConflict(vector []int) bool {
	// 只需判断新添加的（最后一个）皇后和已有的皇后是否有冲突
	for i := 0; i < len(vector)-1; i++ {
		if _isConflict(i, vector[i], len(vector)-1, vector[len(vector)-1]) {
			return true
		}
	}
	return false
}

// (x1, y1) 和 (x2, y2) 两个皇后是否有冲突
func _isConflict(x1, y1, x2, y2 int) bool {
	// 在一条直线上
	if x1 == x2 || y1 == y2 {
		return true
	}
	// 在一条对角线上
	if abs(y1-y2) == abs(x1-x2) {
		return true
	}
	return false
}

// 输出结果：Q代表皇后
func output(vector []int) (ans []string) {
	dots := make([]byte, len(vector))
	for i := range dots {
		dots[i] = '.'
	}
	for i := 0; i < len(vector); i++ {
		pos := make([]byte, len(vector))
		copy(pos, dots)
		pos[vector[i]] = 'Q'
		ans = append(ans, string(pos))
	}
	return
}

// absolute
func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

如果不使用闭包，也可以用全局变量，并且回溯函数需要更多的参数。