N 皇后

递归与回溯

说明

逐行放置皇后并排除同列与对角线；回溯撤销选择。

分析

每一行只放一个皇后，因此只需记录列和两种对角线是否已占用。尝试一个位置后标记约束，递归下一行，返回时撤销标记。

图解推演

用零起始行列表示，4 皇后的一组解按行选择列 [1,3,0,2]。同列用 c 判断，两条对角线分别由 r−c、r+c 标识；负的 r−c 若用数组保存需加偏移。每层只放一行，已经隐含排除了同行冲突。

查看图表代码

适用前提与边界

搜索仍可能指数增长，但即时排除冲突位置比先枚举整张棋盘高效得多。

示例输入与调用

fmt.Println(NQueens(4))

运行输出

2

完整 Go 示例

package main

import "fmt"

func NQueens(n int) int {
	cols, d1, d2 := make([]bool, n), make([]bool, 2*n), make([]bool, 2*n)
	count := 0
	var dfs func(int)
	dfs = func(row int) {
		if row == n {
			count++
			return
		}
		for c := 0; c < n; c++ {
			a, b := row-c+n, row+c
			if cols[c] || d1[a] || d2[b] {
				continue
			}
			cols[c], d1[a], d2[b] = true, true, true
			dfs(row + 1)
			cols[c], d1[a], d2[b] = false, false, false
		}
	}
	dfs(0)
	return count
}

func main() {
	fmt.Println(NQueens(4))
}