LeetCode 面试题 08.12. 八皇后

Categories:

题目描述
思路分析
1. 解法一：回溯（推荐）
相似题目

题目描述

✅ 面试题 08.12. 八皇后

思路分析

解法一：回溯（推荐）

核心思路：

逐行放置皇后，每行只放一个。

用列、主对角线、副对角线集合判断是否合法。

递归到第 8 行时生成棋盘方案。

复杂度分析：

时间复杂度：O(8!)，常数规模回溯。

空间复杂度：O(8)，递归栈与标记数组。

// 回溯生成八皇后解
class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        boolean[] cols = new boolean[n];
        boolean[] diag1 = new boolean[2 * n];
        boolean[] diag2 = new boolean[2 * n];
        int[] path = new int[n];
        backtrack(0, n, cols, diag1, diag2, path, res);
        return res;
    }

    private void backtrack(int row, int n, boolean[] cols, boolean[] diag1, boolean[] diag2,
                           int[] path, List<List<String>> res) {
        if (row == n) {
            res.add(buildBoard(path, n));
            return;
        }

        for (int col = 0; col < n; col++) {
            int d1 = row - col + n;
            int d2 = row + col;
            if (cols[col] || diag1[d1] || diag2[d2]) {
                continue;
            }
            cols[col] = true;
            diag1[d1] = true;
            diag2[d2] = true;
            path[row] = col;

            backtrack(row + 1, n, cols, diag1, diag2, path, res);

            cols[col] = false;
            diag1[d1] = false;
            diag2[d2] = false;
        }
    }

    private List<String> buildBoard(int[] path, int n) {
        List<String> board = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[path[i]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }
}

// 回溯生成八皇后解
func solveNQueens(n int) [][]string {
	res := make([][]string, 0)
	cols := make([]bool, n)
	diag1 := make([]bool, 2*n)
	diag2 := make([]bool, 2*n)
	path := make([]int, n)

	var backtrack func(int)
	backtrack = func(row int) {
		if row == n {
			res = append(res, buildBoard(path, n))
			return
		}

		for col := 0; col < n; col++ {
			d1 := row - col + n
			d2 := row + col
			if cols[col] || diag1[d1] || diag2[d2] {
				continue
			}
			cols[col] = true
			diag1[d1] = true
			diag2[d2] = true
			path[row] = col

			backtrack(row + 1)

			cols[col] = false
			diag1[d1] = false
			diag2[d2] = false
		}
	}

	backtrack(0)
	return res
}

func buildBoard(path []int, n int) []string {
	board := make([]string, n)
	for i := 0; i < n; i++ {
		row := make([]byte, n)
		for j := 0; j < n; j++ {
			row[j] = '.'
		}
		row[path[i]] = 'Q'
		board[i] = string(row)
	}
	return board
}

相似题目

题目	难度	考察点
51. N 皇后	困难	回溯
52. N 皇后 II	困难	回溯
37. 解数独	困难	回溯
46. 全排列	中等	回溯
77. 组合	中等	回溯

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/89520914