51N皇后.md

var res [][]string
func solveNQueens(n int) [][]string {
    res = [][]string{}
    board := make([][]string, n)
    for i := 0; i < n; i++ {
        board[i] = make([]string, n)
        for j := 0; j < n; j++ {
            board[i][j] = "."
        }
    }
    backtrack(0, board)
    return res
}

func backtrack(row int, board [][]string) {
    n := len(board)
    // 终止条件 当已经完成第n行后结束
    if row == n {
        tmp := make([]string, n)
        for i := 0; i < n; i++ {
            tmp[i] = strings.Join(board[i], "")
        }
        res = append(res, tmp)
        return
    }
    for col := 0; col < n; col++ {
        if isValid(row, col, board) {
            board[row][col] = "Q"
            // 递归下一行后回溯
            backtrack(row+1, board)
            board[row][col] = "."
        }
    }
}

func isValid(row, col int, board [][]string) bool {
    n := len(board)
    // 检查列
    for i := 0; i < row; i++ {
        if board[i][col] == "Q" {
            return false
        }
    }
    // 检查45度（左上斜线）
    for i, j := row - 1, col - 1; i >= 0 && j >= 0; i, j = i - 1, j - 1 {
        if board[i][j] == "Q" {
            return false
        }
    }
    // 检查135度（右上斜线）
    for i, j := row - 1, col + 1; i >= 0 && j < n; i, j = i - 1, j + 1 {
        if board[i][j] == "Q" {
            return false
        }
    }
    // 无需检查行
    return true
}