n皇后非递归

n皇后问题是一个经典的回溯算法问题，可以通过回溯算法解决。而非递归的方式则可以利用栈的数据结构实现。下面是非递归的n皇后实现代码：

def n_queen(n: int):
    # 初始化棋盘
    board = [['.' for _ in range(n)] for _ in range(n)]
    # 棋盘每一列已经放置的皇后数
    col_count = [0] * n
    # 棋盘左上角到右下角的对角线已经放置的皇后数
    diag1_count = [0] * (2 * n - 1)
    # 棋盘右上角到左下角的对角线已经放置的皇后数
    diag2_count = [0] * (2 * n - 1)

    # 定义一个栈用于存储每一行已经放置的皇后位置
    stack = [(0, 0)]
    while stack:
        row, col = stack.pop()
        # 将皇后放置在棋盘上
        board[row][col] = 'Q'
        col_count[col] += 1
        diag1_count[row + col] += 1
        diag2_count[row - col + n - 1] += 1

        # 如果已经放置了n个皇后，则找到一组可行解
        if len(stack) == n - 1:
            yield [''.join(row) for row in board]

        # 否则，继续尝试在下一行放置皇后
        else:
            for next_col in range(n):
                # 判断下一行放置皇后的合法性
                if col_count[next_col] == 0 and diag1_count[row + next_col] == 0 and diag2_count[row - next_col + n - 1] == 0:
                    stack.append((row + 1, next_col))

        # 回溯
        board[row][col] = '.'
        col_count[col] -= 1
        diag1_count[row + col] -= 1
        diag2_count[row - col + n - 1] -= 1

该算法的时间复杂度为 $O(n!)$，空间复杂度为 $O(n)$。