leetcode51：N皇后

题目链接

leetcode

题目描述

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

/*
    回溯法

    由于每行只能有一个皇后，依次枚举每一行的皇后放到哪个位置，
    放置的过程中验证每一个位置是否合法。

    时间复杂度：O(n!)
        对于每个皇后，都有 n 种选择，因此总共有 n^n 种可能的排列。
        由于 n 个皇后不能在同行同列，所以每行恰有一个皇后。
        在不考虑对角线的情况下，计算方案数的上限。
        第一行有 n 个位置可选，第二行有 n−1 个位置可选，依次类推，可知方案数最多是 n!。
    空间复杂度：O(n)
        递归需要使用栈空间。
        在最坏的情况下，递归的深度可以达到 n，因此空间复杂度为 O(n)。
*/
class Solution_0 {
public:
    vector<vector<string>> solveNQueens(int n) {
        row = col = vector<bool>(n, false);
        dg = udg = vector<bool>(2 * n, false);
        path = vector<string>(n, string(n, '.'));
        dfs(0, 0, 0, n);

        return res;
    }

    void dfs(int x, int y, int u, int n) {
        if (y == n) {
            x ++;
            y = 0;
        }
        if (x == n) {
            if (u == n) res.push_back(path);
            return;
        }

        dfs(x, y + 1, u, n);
        if (!row[x] && !col[y] && !dg[x + y] && !udg[n - 1 - x + y]) {
            row[x] = col[y] = dg[x + y] = udg[n - 1 - x + y] = true;
            path[x][y] = 'Q';
            dfs(x, y + 1, u + 1, n);
            path[x][y] = '.';
            row[x] = col[y] = dg[x + y] = udg[n - 1 - x + y] = false;
        }
    }

private:
    vector<vector<string>> res;
    vector<string> path;
    vector<bool> row, col, dg, udg;
};

/*
    思路同上
*/
class Solution_1 {
public:
    vector<vector<string>> solveNQueens(int _n) {
        n = _n;
        col = vector<bool>(n);
        dg = udg = vector<bool>(n * 2);
        path = vector<string>(n, string(n, '.'));

        dfs(0);
        return res;
    }

    void dfs(int row) {
        if (row == n) {
            res.push_back(path);
            return;
        }

        for (int i = 0; i < n; i ++) {
            if (!col[i] && !dg[row - i + n] && !udg[row + i]) {
                col[i] = dg[row - i + n] = udg[row + i] = true;
                path[row][i] = 'Q';
                dfs(row + 1);
                path[row][i] = '.';
                col[i] = dg[row - i + n] = udg[row + i] = false;
            }
        }
    }

private:
    int n;
    vector<bool> col, dg, udg; // 记录每一列、每条对角线上是否存在皇后
    vector<vector<string>> res;
    vector<string> path;
};

/*
    回溯法
    
    由于每行只能有一个皇后，依次枚举每一行的皇后放到哪个位置，
    放置的过程中验证每一个位置是否合法。

    时间复杂度：O(n!)
        对于每个皇后，都有 n 种选择，因此总共有 n^n 种可能的排列。
        由于 n 个皇后不能在同行同列，所以每行恰有一个皇后。
        在不考虑对角线的情况下，计算方案数的上限。
        第一行有 n 个位置可选，第二行有 n−1 个位置可选，依次类推，可知方案数最多是 n!。
    空间复杂度：O(n)
        递归使用的栈空间。
        在最坏的情况下，递归的深度可以达到 n，因此空间复杂度为 O(n)。
*/
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<string> path = vector<string>(n, string(n, '.'));
        dfs(path, 0);

        return res;
    }

    void dfs(vector<string>& path, int row) {
        if (row == path.size()) {
            res.push_back(path);
            return;
        }

        for (int col = 0; col < path.size(); col ++) {
            // 检查该位置是否可以放置
            if (isValid(path, row, col)) {
                path[row][col] = 'Q'; // 做选择：放置皇后
                dfs(path, row + 1);   // 下一行决策
                path[row][col] = '.'; // 撤销选择：回溯
            }
        }
    }

    bool isValid(vector<string> path, int row, int col) {
        // 检查列（剪枝）
        for (int i = 0; i < row; i ++) {
            if (path[i][col] == 'Q') return false;
        }
        // 检查主对角线
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i --, j --) {
            if (path[i][j] == 'Q') return false;
        }
        // 检查副对角线
        for (int i = row - 1, j = col + 1; i >= 0 && j < path.size(); i --, j ++) {
            if (path[i][j] == 'Q') return false; 
        }

        return true;
    }

private:
    vector<vector<string>> res;
};

int main() {
    Solution solution;
    int n = 4;
    vector<vector<string>> solutions = solution.solveNQueens(n);
    cout << "Solutions for " << n << " queens:" << endl;
    for (const vector<string>& solution : solutions) {
        for (const string& row : solution) {
            cout << row << endl;
        }
        cout << endl;
    }
    
    return 0;
}

Golang 代码

package main

import (
	"fmt"
	"reflect"
	"strings"
)

/*
   回溯算法：
       使用递归函数 dfs，逐行放置皇后。
       每次尝试放置皇后时，检查当前列和对角线是否被占用。
       如果可以放置皇后，则递归处理下一行，否则跳过当前列。
   状态管理：
       使用 cols 表示列是否被占用。
       使用 dpos 和 npos 分别表示正对角线和副对角线是否被占用。
       在递归返回时，恢复状态（回溯）。

   时间复杂度：O(N!)
       由于每个皇后有 N 种放置方式，总共有 N! 种可能的放置方案，因此时间复杂度为 O(N!)。
   空间复杂度：O(N)
       递归调用栈的深度为 O(N)，同时需要存储列和对角线的状态，空间复杂度为 O(N)。
*/
func solveNQueens(n int) [][]string {
    result := [][]string{}
    cols := make([]bool, n)          // 列是否被占用
    diags := make([]bool, 2*n-1)     // 正对角线是否被占用
    antiDiags := make([]bool, 2*n-1) // 副对角线是否被占用

    var dfs func(row int, path []int)
    dfs = func(row int, path []int) {
        // 如果已经处理完所有行，将当前路径加入结果
        if row == n {
            board := constructBoard(n, path)
            result = append(result, board)
            return
        }

        for col := 0; col < n; col ++ {
            // 计算正对角线和副对角线的索引
            diag := row - col + n - 1
            antiDiag := row + col
            // 检查当前列和对角线是否冲突
            if cols[col] || diags[diag] || antiDiags[antiDiag] {
                continue
            }
            // 选择：放置皇后
            cols[col] = true
            diags[diag] = true
            antiDiags[antiDiag] = true
            // 递归处理下一行
            dfs(row+1, append(path, col))
            // 回溯：恢复状态
            cols[col] = false
            diags[diag] = false
            antiDiags[antiDiag] = false
        }
    }

    // 开始回溯
    dfs(0, []int{})
    return result
}

// constructBoard 根据路径构建棋盘
func constructBoard(n int, path []int,) []string {
    board := make([]string, n)
    for i, col := range path {
        // 构建每一行的字符串，皇后位置为 'Q'，其余位置为 '.'
        board[i] = strings.Repeat(".", col) + "Q" + strings.Repeat(".", n-1-col)
    }
    return board
}

/*
    思路同上
*/
func solveNQueens_1(n int) [][]string {
    // 初始化棋盘：'.' 表示空，'Q' 表示皇后
    board := make([]string, n)
    for i := range board {
        board[i] = strings.Repeat(".", n)
    }

    res := [][]string{}
    dfs(&res, board, 0)
    return res
}

// 路径：board 中小于 row 的行都已经成功放置了皇后
// 选择列表：第 row 行的所有列都是放置皇后的选择
// 结束条件：row 超过 board 的最后一行
func dfs(res *[][]string, board []string, row int) {
    // 触发结束条件
    if row == len(board) {
        *res = append(*res, append([]string{}, board...))
        return
    }

    for col := 0; col < len(board[row]); col ++ {
        // 排除不合法选择
        if !isValid(board, row, col) {
            continue
        }

        // 做选择
        newRow := []rune(board[row])
        newRow[col] = 'Q'
        board[row] = string(newRow)
        // 进入下一行决策
        dfs(res, board, row + 1)
        // 撤销选择
        newRow[col] = '.'
        board[row] = string(newRow)
    }
}

// 是否可以在 board[row][col] 放置皇后
func isValid(board []string, row, col int) bool {
    n := len(board)
    // 检查列是否冲突
    for i := 0; i < row; i ++ {
        if board[i][col] == 'Q' {
            return false
        }
    }
    // 检查右上方是否冲突
    for i, j := row-1, col+1; i >= 0 && j < n; i, j = i-1, j+1 {
        if board[i][j] == 'Q' {
            return false
        }
    }
    // 检查左上方是否冲突
    for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 {
        if board[i][j] == 'Q' {
            return false
        }
    }
    return true
}

func main() {
    // 测试用例
    testCases := []struct {
        n        int
        expected [][]string
    }{
        {
            n: 4,
            expected: [][]string{
                {".Q..", "...Q", "Q...", "..Q."},
                {"..Q.", "Q...", "...Q", ".Q.."},
            },
        },
        {
            n: 1,
            expected: [][]string{
                {"Q"},
            },
        },
    }

	for i, tc := range testCases {
        fmt.Printf("Test Case %d, Input: n = %d\n", i+1, tc.n)
		result := solveNQueens(tc.n)

        if reflect.DeepEqual(result, tc.expected) {
            fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, result)
        } else {
            fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, result, tc.expected)
        }
	}
}