#
# @lc app=leetcode id=51 lang=python3
#
# [51] N-Queens
#
from typing import List
# @lc code=start
class Solution:
    def solveNQueensStraight(self, n: int) -> List[List[str]]:
        self.res = []
        self.queens = [['.' for _ in range(n)] for _ in range(n)]
        self.helper(0)
        return self.res

    def helper(self, curRow):
        # print(self.queens)
        n = len(self.queens)
        if curRow == n:
            self.res.append([''.join(i) for i in self.queens])
            return
        for i in range(n):
            if self.isValid(curRow, i):
                self.queens[curRow][i] = 'Q'
                self.helper(curRow+1)
                self.queens[curRow][i] = '.'

    def isValid(self, row, col):
        # check col
        for i in range(row):
            if self.queens[i][col] == 'Q':
                return False
        # check dia
        i = row-1
        j = col-1
        while i>=0 and j>=0:
            if self.queens[i][j] == 'Q':
                return False
            i -= 1
            j -= 1
        # check back dia
        i = row-1
        j = col+1
        while i>=0 and j<len(self.queens):
            if self.queens[i][j] == 'Q':
                return False
            i -= 1
            j += 1
        return True

    def solveNQueens(self, n: int) -> List[List[str]]:
        res = []
        qCol = [-1 for _ in range(n)]
        self.helper2(0, qCol, res)
        return res

    def helper2(self, curRow, qCol, res):
        n = len(qCol)
        if curRow == n:
            tmp = []
            for i in range(n):
                tmpRow = '.'*qCol[i]+'Q'+'.'*(n-qCol[i]-1)
                tmp.append(tmpRow)
            res.append(tmp)
        for i in range(n):
            if self.isValid2(qCol, curRow, i):
                qCol[curRow] = i
                self.helper2(curRow+1, qCol, res)
                qCol[curRow] = -1

    def isValid2(self, qCol, row, col):
        for i in range(row):
            if col==qCol[i] or abs(row-i)==abs(col-qCol[i]):
                return False
        return True

# @lc code=end

res = Solution().solveNQueens(4)
print(res)
f08aa3a10939cedc65ae9d8feca4073a8c94938e
<mask token>


class Solution:
    <mask token>

    def helper(self, curRow):
        n = len(self.queens)
        if curRow == n:
            self.res.append([''.join(i) for i in self.queens])
            return
        for i in range(n):
            if self.isValid(curRow, i):
                self.queens[curRow][i] = 'Q'
                self.helper(curRow + 1)
                self.queens[curRow][i] = '.'
    <mask token>

    def solveNQueens(self, n: int) ->List[List[str]]:
        res = []
        qCol = [(-1) for _ in range(n)]
        self.helper2(0, qCol, res)
        return res

    def helper2(self, curRow, qCol, res):
        n = len(qCol)
        if curRow == n:
            tmp = []
            for i in range(n):
                tmpRow = '.' * qCol[i] + 'Q' + '.' * (n - qCol[i] - 1)
                tmp.append(tmpRow)
            res.append(tmp)
        for i in range(n):
            if self.isValid2(qCol, curRow, i):
                qCol[curRow] = i
                self.helper2(curRow + 1, qCol, res)
                qCol[curRow] = -1
    <mask token>


<mask token>

<mask token>


class Solution:

    def solveNQueensStraight(self, n: int) ->List[List[str]]:
        self.res = []
        self.queens = [['.' for _ in range(n)] for _ in range(n)]
        self.helper(0)
        return self.res

    def helper(self, curRow):
        n = len(self.queens)
        if curRow == n:
            self.res.append([''.join(i) for i in self.queens])
            return
        for i in range(n):
            if self.isValid(curRow, i):
                self.queens[curRow][i] = 'Q'
                self.helper(curRow + 1)
                self.queens[curRow][i] = '.'

    def isValid(self, row, col):
        for i in range(row):
            if self.queens[i][col] == 'Q':
                return False
        i = row - 1
        j = col - 1
        while i >= 0 and j >= 0:
            if self.queens[i][j] == 'Q':
                return False
            i -= 1
            j -= 1
        i = row - 1
        j = col + 1
        while i >= 0 and j < len(self.queens):
            if self.queens[i][j] == 'Q':
                return False
            i -= 1
            j += 1
        return True

    def solveNQueens(self, n: int) ->List[List[str]]:
        res = []
        qCol = [(-1) for _ in range(n)]
        self.helper2(0, qCol, res)
        return res

    def helper2(self, curRow, qCol, res):
        n = len(qCol)
        if curRow == n:
            tmp = []
            for i in range(n):
                tmpRow = '.' * qCol[i] + 'Q' + '.' * (n - qCol[i] - 1)
                tmp.append(tmpRow)
            res.append(tmp)
        for i in range(n):
            if self.isValid2(qCol, curRow, i):
                qCol[curRow] = i
                self.helper2(curRow + 1, qCol, res)
                qCol[curRow] = -1

    def isValid2(self, qCol, row, col):
        for i in range(row):
            if col == qCol[i] or abs(row - i) == abs(col - qCol[i]):
                return False
        return True


<mask token>

<mask token>


class Solution:

    def solveNQueensStraight(self, n: int) ->List[List[str]]:
        self.res = []
        self.queens = [['.' for _ in range(n)] for _ in range(n)]
        self.helper(0)
        return self.res

    def helper(self, curRow):
        n = len(self.queens)
        if curRow == n:
            self.res.append([''.join(i) for i in self.queens])
            return
        for i in range(n):
            if self.isValid(curRow, i):
                self.queens[curRow][i] = 'Q'
                self.helper(curRow + 1)
                self.queens[curRow][i] = '.'

    def isValid(self, row, col):
        for i in range(row):
            if self.queens[i][col] == 'Q':
                return False
        i = row - 1
        j = col - 1
        while i >= 0 and j >= 0:
            if self.queens[i][j] == 'Q':
                return False
            i -= 1
            j -= 1
        i = row - 1
        j = col + 1
        while i >= 0 and j < len(self.queens):
            if self.queens[i][j] == 'Q':
                return False
            i -= 1
            j += 1
        return True

    def solveNQueens(self, n: int) ->List[List[str]]:
        res = []
        qCol = [(-1) for _ in range(n)]
        self.helper2(0, qCol, res)
        return res

    def helper2(self, curRow, qCol, res):
        n = len(qCol)
        if curRow == n:
            tmp = []
            for i in range(n):
                tmpRow = '.' * qCol[i] + 'Q' + '.' * (n - qCol[i] - 1)
                tmp.append(tmpRow)
            res.append(tmp)
        for i in range(n):
            if self.isValid2(qCol, curRow, i):
                qCol[curRow] = i
                self.helper2(curRow + 1, qCol, res)
                qCol[curRow] = -1

    def isValid2(self, qCol, row, col):
        for i in range(row):
            if col == qCol[i] or abs(row - i) == abs(col - qCol[i]):
                return False
        return True


<mask token>
print(res)

from typing import List


class Solution:

    def solveNQueensStraight(self, n: int) ->List[List[str]]:
        self.res = []
        self.queens = [['.' for _ in range(n)] for _ in range(n)]
        self.helper(0)
        return self.res

    def helper(self, curRow):
        n = len(self.queens)
        if curRow == n:
            self.res.append([''.join(i) for i in self.queens])
            return
        for i in range(n):
            if self.isValid(curRow, i):
                self.queens[curRow][i] = 'Q'
                self.helper(curRow + 1)
                self.queens[curRow][i] = '.'

    def isValid(self, row, col):
        for i in range(row):
            if self.queens[i][col] == 'Q':
                return False
        i = row - 1
        j = col - 1
        while i >= 0 and j >= 0:
            if self.queens[i][j] == 'Q':
                return False
            i -= 1
            j -= 1
        i = row - 1
        j = col + 1
        while i >= 0 and j < len(self.queens):
            if self.queens[i][j] == 'Q':
                return False
            i -= 1
            j += 1
        return True

    def solveNQueens(self, n: int) ->List[List[str]]:
        res = []
        qCol = [(-1) for _ in range(n)]
        self.helper2(0, qCol, res)
        return res

    def helper2(self, curRow, qCol, res):
        n = len(qCol)
        if curRow == n:
            tmp = []
            for i in range(n):
                tmpRow = '.' * qCol[i] + 'Q' + '.' * (n - qCol[i] - 1)
                tmp.append(tmpRow)
            res.append(tmp)
        for i in range(n):
            if self.isValid2(qCol, curRow, i):
                qCol[curRow] = i
                self.helper2(curRow + 1, qCol, res)
                qCol[curRow] = -1

    def isValid2(self, qCol, row, col):
        for i in range(row):
            if col == qCol[i] or abs(row - i) == abs(col - qCol[i]):
                return False
        return True


res = Solution().solveNQueens(4)
print(res)

#
# @lc app=leetcode id=51 lang=python3
#
# [51] N-Queens
#
from typing import List
# @lc code=start
class Solution:
    def solveNQueensStraight(self, n: int) -> List[List[str]]:
        self.res = []
        self.queens = [['.' for _ in range(n)] for _ in range(n)]
        self.helper(0)
        return self.res

    def helper(self, curRow):
        # print(self.queens)
        n = len(self.queens)
        if curRow == n:
            self.res.append([''.join(i) for i in self.queens])
            return
        for i in range(n):
            if self.isValid(curRow, i):
                self.queens[curRow][i] = 'Q'
                self.helper(curRow+1)
                self.queens[curRow][i] = '.'

    def isValid(self, row, col):
        # check col
        for i in range(row):
            if self.queens[i][col] == 'Q':
                return False
        # check dia
        i = row-1
        j = col-1
        while i>=0 and j>=0:
            if self.queens[i][j] == 'Q':
                return False
            i -= 1
            j -= 1
        # check back dia
        i = row-1
        j = col+1
        while i>=0 and j<len(self.queens):
            if self.queens[i][j] == 'Q':
                return False
            i -= 1
            j += 1
        return True

    def solveNQueens(self, n: int) -> List[List[str]]:
        res = []
        qCol = [-1 for _ in range(n)]
        self.helper2(0, qCol, res)
        return res

    def helper2(self, curRow, qCol, res):
        n = len(qCol)
        if curRow == n:
            tmp = []
            for i in range(n):
                tmpRow = '.'*qCol[i]+'Q'+'.'*(n-qCol[i]-1)
                tmp.append(tmpRow)
            res.append(tmp)
        for i in range(n):
            if self.isValid2(qCol, curRow, i):
                qCol[curRow] = i
                self.helper2(curRow+1, qCol, res)
                qCol[curRow] = -1

    def isValid2(self, qCol, row, col):
        for i in range(row):
            if col==qCol[i] or abs(row-i)==abs(col-qCol[i]):
                return False
        return True

# @lc code=end

res = Solution().solveNQueens(4)
print(res)