#!/usr/bin/python
# -*- coding: utf-8 -*-
# @Time    : 2020/3/16
# @Author  : xujun
"""
N皇后
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

输入: 4
输出: [
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。
"""


class Solution:
    def solveNQueens(self, n: int):
        def could_place(row, col):
            return not (cols[col] + hill_diagonals[row - col] + dale_diagonals[row + col])

        def place_queen(row, col):
            queens.add((row, col))
            cols[col] = 1
            hill_diagonals[row - col] = 1
            dale_diagonals[row + col] = 1

        def remove_queen(row, col):
            queens.remove((row, col))
            cols[col] = 0
            hill_diagonals[row - col] = 0
            dale_diagonals[row + col] = 0

        def add_solution():
            solution = []
            for _, col in sorted(queens):
                solution.append('.' * col + 'Q' + '.' * (n - col - 1))
            output.append(solution)

        def backtrack(row=0):
            # 循环列并且试图在每个 column 中放置皇后.
            for col in range(n):
                # 如果方格 (row, column) 不在攻击范围内, 排除对应行，列和两个对角线的位置
                if could_place(row, col):
                    # 在 (row, column) 方格上放置皇后
                    place_queen(row, col)
                    # If 所有的行被考虑过，row == N
                    if row + 1 == n:
                        add_solution()
                    else:
                        backtrack(row + 1)
                    # 回溯：将在 (row, column) 方格的皇后移除.
                    remove_queen(row, col)

        cols = [0] * n
        hill_diagonals = [0] * (2 * n - 1)
        dale_diagonals = [0] * (2 * n - 1)
        queens = set()
        output = []
        backtrack()
        return output
