n皇后问题非递归回溯算法

一、问题描述

n皇后问题是一个经典的回溯算法问题，其目标是在一个n*n的棋盘上放置n个皇后，使得它们互相之间不能攻击。即任意两个皇后都不能处于同一行、同一列或者同一斜线上。

二、问题分析

1. 回溯算法思路

回溯算法是一种通过穷举所有可能情况来找到所有解的算法。在遍历过程中，如果发现当前状态不符合要求，则回溯到上一个状态进行下一步尝试。

2. 非递归实现

传统的n皇后问题解法大多采用递归实现，但是递归实现会存在栈溢出等问题。因此，我们可以采用非递归实现方式来避免这些问题。

三、算法设计

1. 状态表示

我们可以用一个数组board来表示当前棋盘状态，其中board[i]表示第i行皇后所在的列数。

2. 状态转移

在每一行中，我们依次尝试将皇后放置在每一个位置上。如果当前位置不符合要求，则继续尝试下一个位置；如果当前位置符合要求，则将该位置标记为已占用，并将当前状态入栈进入下一层搜索。当搜索到第n层时，说明找到了一组解，将该解保存并回溯到上一层继续搜索。

3. 剪枝优化

为了减少不必要的搜索，我们可以采用以下两种剪枝策略：

（1）列冲突剪枝：如果当前位置所在列已经有皇后，则直接跳过该位置。

（2）斜线冲突剪枝：如果当前位置所在的左上、右上斜线已经有皇后，则直接跳过该位置。

四、代码实现

1. 初始化

首先，我们需要定义一个栈来保存状态，并将第一行的所有位置都尝试一遍。同时，我们还需要定义一个二维数组visited来保存哪些列和哪些斜线已经被占用。

```python

def solveNQueens(n: int) -> List[List[str]]: res = [] stack = []

visited = [[False] * n for _ in range(3)] for i in range(n): stack.append([i]) visited[0][i] = True

visited[1][i - 0 + n - 1] = True visited[2][i + 0] = True ```

2. 回溯搜索

在搜索过程中，我们不断取出栈顶状态进行扩展。如果当前状态已经到达第n层，则说明找到了一组解，将其添加到结果集中。否则，依次尝试将皇后放置在每个位置上，并进行剪枝。

```python while stack:

board = stack.pop() row = len(board) if row == n:

res.append(['.' * i + 'Q' + '.' * (n - i - 1) for i in board]) continue for col in range(n):

if not visited[0][col] and not visited[1][row - col + n - 1] and not visited[2][row + col]:

stack.append(board + [col]) visited[0][col] = True

visited[1][row - col + n - 1] = True visited[2][row + col] = True ```

3. 完整代码

```python

from typing import List

def solveNQueens(n: int) -> List[List[str]]: res = [] stack = []

visited = [[False] * n for _ in range(3)] for i in range(n): stack.append([i]) visited[0][i] = True

visited[1][i - 0 + n - 1] = True visited[2][i + 0] = True

while stack:

board = stack.pop() row = len(board) if row == n:

res.append(['.' * i + 'Q' + '.' * (n - i - 1) for i in board]) continue for col in range(n):

if not visited[0][col] and not visited[1][row - col + n - 1] and not visited[2][row + col]:

stack.append(board + [col]) visited[0][col] = True

visited[1][row - col + n - 1] = True visited[2][row + col] = True return res ``` 五、总结

本文介绍了n皇后问题的非递归回溯算法实现，通过状态表示、状态转移和剪枝优化等方式，避免了递归实现可能存在的栈溢出问题。该算法的时间复杂度为O(n^n)，空间复杂度为O(n)。