题解 | N皇后问题

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	for {
		scanner := bufio.NewScanner(os.Stdin)

		// 设置大缓冲区，防止大输入时出错
		buf := make([]byte, 1024*1024) // 1MB
		scanner.Buffer(buf, 1024*1024)
		scanner.Split(bufio.ScanWords) // 按单词扫描（空格、换行等分隔）

		// 读取第一行：n
		scanner.Scan()
		n, _ := strconv.Atoi(scanner.Text())
		if n == 0 {
			break
		}

		// n = 3
		// [0,0] [0,1], [0,2]
		// [1,0] [1,1], [1,2]
		// [2,0] [2,1], [2,2]
		// min := 0
		// max := 4
		col := make([]bool, n)
		dui1 := make([]bool, 2*n-1) // i-j+n-1 右下角斜线
		dui2 := make([]bool, 2*n-1) // i+j 左下角斜线
		fmt.Println(process(n, 0, col, dui1, dui2))
	}
}

func process(n int, row int, col, dui1, dui2 []bool) int {
	if n == row {
		return 1
	}

	sum := 0
	for i := 0; i < n; i++ {
	    // 判断是否能够放置
		if col[i] || dui1[row-i+n-1] || dui2[i+row] {
			continue
		}
		col[i] = true
		dui1[row-i+n-1] = true
		dui2[i+row] = true
        // 累加可能性
		sum += process(n, row+1, col, dui1, dui2)
        // 回溯状态信息
		col[i] = false
		dui1[row-i+n-1] = false
		dui2[i+row] = false
	}
	return sum
}