The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.



Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

Example:


Input: 4
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

Difficulty: MEDIUM_HARD
Tags: Data structures

Complete search
Skill types: Data structures

Complete search

Starter code:
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        

Solutions:
class Solution:

	def helper(self, n, currentIndex, aux, rowsWithQueen, alll):
		for i in range(n):
			if i not in rowsWithQueen:
				(x, y) = (currentIndex - 1, i - 1)
				while aux[x][y] != 'Q' and x >= 0 and (y >= 0):
					x -= 1
					y -= 1
				if x != -1 and y != -1:
					continue
				(x, y) = (currentIndex - 1, i + 1)
				while x >= 0 and y < n and (aux[x][y] != 'Q'):
					x -= 1
					y += 1
				if x != -1 and y != n:
					continue
				aux[currentIndex][i] = 'Q'
				rowsWithQueen.append(i)
				if currentIndex == n - 1:
					aw = [[0 for i in range(n)] for j in range(n)]
					for a in range(n):
						for b in range(n):
							aw[a][b] = aux[a][b]
					alll.append(aw)
				else:
					self.helper(n, currentIndex + 1, aux, rowsWithQueen, alll)
				aux[currentIndex][i] = '.'
				rowsWithQueen.pop()

	def solveNQueens(self, n):
		aux = [['.' for i in range(n)] for j in range(n)]
		rowsWithQueen = []
		alll = []
		self.helper(n, 0, aux, rowsWithQueen, alll)
		aux = []
		for sol in alll:
			ax = []
			for i in sol:
				i = ''.join(i)
				ax.append(i)
			aux.append(ax)
		return aux


class Solution:

	def solveNQueens(self, n):

		def DFS(queens, xy_dif, xy_sum):
			p = len(queens)
			if p == n:
				result.append(queens)
				return None
			for q in range(n):
				if q not in queens and p - q not in xy_dif and (p + q not in xy_sum):
					DFS(queens + [q], xy_dif + [p - q], xy_sum + [p + q])
		result = []
		DFS([], [], [])
		return [['.' * i + 'Q' + '.' * (n - i - 1) for i in sol] for sol in result]


class Solution:

	def __init__(self):
		self.board = []
		self.col_status = []
		self.row_status = []
		self.dia_status_1 = []
		self.dia_status_2 = []
		self.result = []

	def placeQueen(self, row, n):
		if row == n:
			tmp = [''.join(el) for el in self.board]
			self.result.append(tmp)
			return
		for i in range(n):
			if self.col_status[i] and self.dia_status_1[i + row] and self.dia_status_2[row - i]:
				self.board[row][i] = 'Q'
				self.col_status[i] = False
				self.dia_status_1[i + row] = False
				self.dia_status_2[row - i] = False
				self.placeQueen(row + 1, n)
				self.board[row][i] = '.'
				self.col_status[i] = True
				self.dia_status_1[i + row] = True
				self.dia_status_2[row - i] = True

	def solveNQueens(self, n):
		self.board = [['.' for i in range(n)] for j in range(n)]
		self.col_status = [True for i in range(n)]
		self.row_status = [True for i in range(n)]
		self.dia_status_1 = [True for i in range(2 * n - 1)]
		self.dia_status_2 = [True for i in range(2 * n - 1)]
		self.placeQueen(0, n)
		return self.result


class Solution:

	def solveNQueens(self, n):
		if n == 1:
			return [['Q']]
		elif n == 2 or n == 3:
			return []
		elif n == 4:
			return [['.Q..', '...Q', 'Q...', '..Q.'], ['..Q.', 'Q...', '...Q', '.Q..']]
		elif n == 5:
			return [['Q....', '..Q..', '....Q', '.Q...', '...Q.'], ['Q....', '...Q.', '.Q...', '....Q', '..Q..'], ['.Q...', '...Q.', 'Q....', '..Q..', '....Q'], ['.Q...', '....Q', '..Q..', 'Q....', '...Q.'], ['..Q..', 'Q....', '...Q.', '.Q...', '....Q'], ['..Q..', '....Q', '.Q...', '...Q.', 'Q....'], ['...Q.', 'Q....', '..Q..', '....Q', '.Q...'], ['...Q.', '.Q...', '....Q', '..Q..', 'Q....'], ['....Q', '.Q...', '...Q.', 'Q....', '..Q..'], ['....Q', '..Q..', 'Q....', '...Q.', '.Q...']]
		elif n == 6:
			return [['.Q....', '...Q..', '.....Q', 'Q.....', '..Q...', '....Q.'], ['..Q...', '.....Q', '.Q....', '....Q.', 'Q.....', '...Q..'], ['...Q..', 'Q.....', '....Q.', '.Q....', '.....Q', '..Q...'], ['....Q.', '..Q...', 'Q.....', '.....Q', '...Q..', '.Q....']]
		elif n == 7:
			return [['Q......', '..Q....', '....Q..', '......Q', '.Q.....', '...Q...', '.....Q.'], ['Q......', '...Q...', '......Q', '..Q....', '.....Q.', '.Q.....', '....Q..'], ['Q......', '....Q..', '.Q.....', '.....Q.', '..Q....', '......Q', '...Q...'], ['Q......', '.....Q.', '...Q...', '.Q.....', '......Q', '....Q..', '..Q....'], ['.Q.....', '...Q...', 'Q......', '......Q', '....Q..', '..Q....', '.....Q.'], ['.Q.....', '...Q...', '.....Q.', 'Q......', '..Q....', '....Q..', '......Q'], ['.Q.....', '....Q..', 'Q......', '...Q...', '......Q', '..Q....', '.....Q.'], ['.Q.....', '....Q..', '..Q....', 'Q......', '......Q', '...Q...', '.....Q.'], ['.Q.....', '....Q..', '......Q', '...Q...', 'Q......', '..Q....', '.....Q.'], ['.Q.....', '.....Q.', '..Q....', '......Q', '...Q...', 'Q......', '....Q..'], ['.Q.....', '......Q', '....Q..', '..Q....', 'Q......', '.....Q.', '...Q...'], ['..Q....', 'Q......', '.....Q.', '.Q.....', '....Q..', '......Q', '...Q...'], ['..Q....', 'Q......', '.....Q.', '...Q...', '.Q.....', '......Q', '....Q..'], ['..Q....', '....Q..', '......Q', '.Q.....', '...Q...', '.....Q.', 'Q......'], ['..Q....', '.....Q.', '.Q.....', '....Q..', 'Q......', '...Q...', '......Q'], ['..Q....', '......Q', '.Q.....', '...Q...', '.....Q.', 'Q......', '....Q..'], ['..Q....', '......Q', '...Q...', 'Q......', '....Q..', '.Q.....', '.....Q.'], ['...Q...', 'Q......', '..Q....', '.....Q.', '.Q.....', '......Q', '....Q..'], ['...Q...', 'Q......', '....Q..', '.Q.....', '.....Q.', '..Q....', '......Q'], ['...Q...', '.Q.....', '......Q', '....Q..', '..Q....', 'Q......', '.....Q.'], ['...Q...', '.....Q.', 'Q......', '..Q....', '....Q..', '......Q', '.Q.....'], ['...Q...', '......Q', '..Q....', '.....Q.', '.Q.....', '....Q..', 'Q......'], ['...Q...', '......Q', '....Q..', '.Q.....', '.....Q.', 'Q......', '..Q....'], ['....Q..', 'Q......', '...Q...', '......Q', '..Q....', '.....Q.', '.Q.....'], ['....Q..', 'Q......', '.....Q.', '...Q...', '.Q.....', '......Q', '..Q....'], ['....Q..', '.Q.....', '.....Q.', '..Q....', '......Q', '...Q...', 'Q......'], ['....Q..', '..Q....', 'Q......', '.....Q.', '...Q...', '.Q.....', '......Q'], ['....Q..', '......Q', '.Q.....', '...Q...', '.....Q.', 'Q......', '..Q....'], ['....Q..', '......Q', '.Q.....', '.....Q.', '..Q....', 'Q......', '...Q...'], ['.....Q.', 'Q......', '..Q....', '....Q..', '......Q', '.Q.....', '...Q...'], ['.....Q.', '.Q.....', '....Q..', 'Q......', '...Q...', '......Q', '..Q....'], ['.....Q.', '..Q....', 'Q......', '...Q...', '......Q', '....Q..', '.Q.....'], ['.....Q.', '..Q....', '....Q..', '......Q', 'Q......', '...Q...', '.Q.....'], ['.....Q.', '..Q....', '......Q', '...Q...', 'Q......', '....Q..', '.Q.....'], ['.....Q.', '...Q...', '.Q.....', '......Q', '....Q..', '..Q....', 'Q......'], ['.....Q.', '...Q...', '......Q', 'Q......', '..Q....', '....Q..', '.Q.....'], ['......Q', '.Q.....', '...Q...', '.....Q.', 'Q......', '..Q....', '....Q..'], ['......Q', '..Q....', '.....Q.', '.Q.....', '....Q..', 'Q......', '...Q...'], ['......Q', '...Q...', 'Q......', '....Q..', '.Q.....', '.....Q.', '..Q....'], ['......Q', '....Q..', '..Q....', 'Q......', '.....Q.', '...Q...', '.Q.....']]
		elif n == 8:
			return [['Q.......', '....Q...', '.......Q', '.....Q..', '..Q.....', '......Q.', '.Q......', '...Q....'], ['Q.......', '.....Q..', '.......Q', '..Q.....', '......Q.', '...Q....', '.Q......', '....Q...'], ['Q.......', '......Q.', '...Q....', '.....Q..', '.......Q', '.Q......', '....Q...', '..Q.....'], ['Q.......', '......Q.', '....Q...', '.......Q', '.Q......', '...Q....', '.....Q..', '..Q.....'], ['.Q......', '...Q....', '.....Q..', '.......Q', '..Q.....', 'Q.......', '......Q.', '....Q...'], ['.Q......', '....Q...', '......Q.', 'Q.......', '..Q.....', '.......Q', '.....Q..', '...Q....'], ['.Q......', '....Q...', '......Q.', '...Q....', 'Q.......', '.......Q', '.....Q..', '..Q.....'], ['.Q......', '.....Q..', 'Q.......', '......Q.', '...Q....', '.......Q', '..Q.....', '....Q...'], ['.Q......', '.....Q..', '.......Q', '..Q.....', 'Q.......', '...Q....', '......Q.', '....Q...'], ['.Q......', '......Q.', '..Q.....', '.....Q..', '.......Q', '....Q...', 'Q.......', '...Q....'], ['.Q......', '......Q.', '....Q...', '.......Q', 'Q.......', '...Q....', '.....Q..', '..Q.....'], ['.Q......', '.......Q', '.....Q..', 'Q.......', '..Q.....', '....Q...', '......Q.', '...Q....'], ['..Q.....', 'Q.......', '......Q.', '....Q...', '.......Q', '.Q......', '...Q....', '.....Q..'], ['..Q.....', '....Q...', '.Q......', '.......Q', 'Q.......', '......Q.', '...Q....', '.....Q..'], ['..Q.....', '....Q...', '.Q......', '.......Q', '.....Q..', '...Q....', '......Q.', 'Q.......'], ['..Q.....', '....Q...', '......Q.', 'Q.......', '...Q....', '.Q......', '.......Q', '.....Q..'], ['..Q.....', '....Q...', '.......Q', '...Q....', 'Q.......', '......Q.', '.Q......', '.....Q..'], ['..Q.....', '.....Q..', '.Q......', '....Q...', '.......Q', 'Q.......', '......Q.', '...Q....'], ['..Q.....', '.....Q..', '.Q......', '......Q.', 'Q.......', '...Q....', '.......Q', '....Q...'], ['..Q.....', '.....Q..', '.Q......', '......Q.', '....Q...', 'Q.......', '.......Q', '...Q....'], ['..Q.....', '.....Q..', '...Q....', 'Q.......', '.......Q', '....Q...', '......Q.', '.Q......'], ['..Q.....', '.....Q..', '...Q....', '.Q......', '.......Q', '....Q...', '......Q.', 'Q.......'], ['..Q.....', '.....Q..', '.......Q', 'Q.......', '...Q....', '......Q.', '....Q...', '.Q......'], ['..Q.....', '.....Q..', '.......Q', 'Q.......', '....Q...', '......Q.', '.Q......', '...Q....'], ['..Q.....', '.....Q..', '.......Q', '.Q......', '...Q....', 'Q.......', '......Q.', '....Q...'], ['..Q.....', '......Q.', '.Q......', '.......Q', '....Q...', 'Q.......', '...Q....', '.....Q..'], ['..Q.....', '......Q.', '.Q......', '.......Q', '.....Q..', '...Q....', 'Q.......', '....Q...'], ['..Q.....', '.......Q', '...Q....', '......Q.', 'Q.......', '.....Q..', '.Q......', '....Q...'], ['...Q....', 'Q.......', '....Q...', '.......Q', '.Q......', '......Q.', '..Q.....', '.....Q..'], ['...Q....', 'Q.......', '....Q...', '.......Q', '.....Q..', '..Q.....', '......Q.', '.Q......'], ['...Q....', '.Q......', '....Q...', '.......Q', '.....Q..', 'Q.......', '..Q.....', '......Q.'], ['...Q....', '.Q......', '......Q.', '..Q.....', '.....Q..', '.......Q', 'Q.......', '....Q...'], ['...Q....', '.Q......', '......Q.', '..Q.....', '.....Q..', '.......Q', '....Q...', 'Q.......'], ['...Q....', '.Q......', '......Q.', '....Q...', 'Q.......', '.......Q', '.....Q..', '..Q.....'], ['...Q....', '.Q......', '.......Q', '....Q...', '......Q.', 'Q.......', '..Q.....', '.....Q..'], ['...Q....', '.Q......', '.......Q', '.....Q..', 'Q.......', '..Q.....', '....Q...', '......Q.'], ['...Q....', '.....Q..', 'Q.......', '....Q...', '.Q......', '.......Q', '..Q.....', '......Q.'], ['...Q....', '.....Q..', '.......Q', '.Q......', '......Q.', 'Q.......', '..Q.....', '....Q...'], ['...Q....', '.....Q..', '.......Q', '..Q.....', 'Q.......', '......Q.', '....Q...', '.Q......'], ['...Q....', '......Q.', 'Q.......', '.......Q', '....Q...', '.Q......', '.....Q..', '..Q.....'], ['...Q....', '......Q.', '..Q.....', '.......Q', '.Q......', '....Q...', 'Q.......', '.....Q..'], ['...Q....', '......Q.', '....Q...', '.Q......', '.....Q..', 'Q.......', '..Q.....', '.......Q'], ['...Q....', '......Q.', '....Q...', '..Q.....', 'Q.......', '.....Q..', '.......Q', '.Q......'], ['...Q....', '.......Q', 'Q.......', '..Q.....', '.....Q..', '.Q......', '......Q.', '....Q...'], ['...Q....', '.......Q', 'Q.......', '....Q...', '......Q.', '.Q......', '.....Q..', '..Q.....'], ['...Q....', '.......Q', '....Q...', '..Q.....', 'Q.......', '......Q.', '.Q......', '.....Q..'], ['....Q...', 'Q.......', '...Q....', '.....Q..', '.......Q', '.Q......', '......Q.', '..Q.....'], ['....Q...', 'Q.......', '.......Q', '...Q....', '.Q......', '......Q.', '..Q.....', '.....Q..'], ['....Q...', 'Q.......', '.......Q', '.....Q..', '..Q.....', '......Q.', '.Q......', '...Q....'], ['....Q...', '.Q......', '...Q....', '.....Q..', '.......Q', '..Q.....', 'Q.......', '......Q.'], ['....Q...', '.Q......', '...Q....', '......Q.', '..Q.....', '.......Q', '.....Q..', 'Q.......'], ['....Q...', '.Q......', '.....Q..', 'Q.......', '......Q.', '...Q....', '.......Q', '..Q.....'], ['....Q...', '.Q......', '.......Q', 'Q.......', '...Q....', '......Q.', '..Q.....', '.....Q..'], ['....Q...', '..Q.....', 'Q.......', '.....Q..', '.......Q', '.Q......', '...Q....', '......Q.'], ['....Q...', '..Q.....', 'Q.......', '......Q.', '.Q......', '.......Q', '.....Q..', '...Q....'], ['....Q...', '..Q.....', '.......Q', '...Q....', '......Q.', 'Q.......', '.....Q..', '.Q......'], ['....Q...', '......Q.', 'Q.......', '..Q.....', '.......Q', '.....Q..', '...Q....', '.Q......'], ['....Q...', '......Q.', 'Q.......', '...Q....', '.Q......', '.......Q', '.....Q..', '..Q.....'], ['....Q...', '......Q.', '.Q......', '...Q....', '.......Q', 'Q.......', '..Q.....', '.....Q..'], ['....Q...', '......Q.', '.Q......', '.....Q..', '..Q.....', 'Q.......', '...Q....', '.......Q'], ['....Q...', '......Q.', '.Q......', '.....Q..', '..Q.....', 'Q.......', '.......Q', '...Q....'], ['....Q...', '......Q.', '...Q....', 'Q.......', '..Q.....', '.......Q', '.....Q..', '.Q......'], ['....Q...', '.......Q', '...Q....', 'Q.......', '..Q.....', '.....Q..', '.Q......', '......Q.'], ['....Q...', '.......Q', '...Q....', 'Q.......', '......Q.', '.Q......', '.....Q..', '..Q.....'], ['.....Q..', 'Q.......', '....Q...', '.Q......', '.......Q', '..Q.....', '......Q.', '...Q....'], ['.....Q..', '.Q......', '......Q.', 'Q.......', '..Q.....', '....Q...', '.......Q', '...Q....'], ['.....Q..', '.Q......', '......Q.', 'Q.......', '...Q....', '.......Q', '....Q...', '..Q.....'], ['.....Q..', '..Q.....', 'Q.......', '......Q.', '....Q...', '.......Q', '.Q......', '...Q....'], ['.....Q..', '..Q.....', 'Q.......', '.......Q', '...Q....', '.Q......', '......Q.', '....Q...'], ['.....Q..', '..Q.....', 'Q.......', '.......Q', '....Q...', '.Q......', '...Q....', '......Q.'], ['.....Q..', '..Q.....', '....Q...', '......Q.', 'Q.......', '...Q....', '.Q......', '.......Q'], ['.....Q..', '..Q.....', '....Q...', '.......Q', 'Q.......', '...Q....', '.Q......', '......Q.'], ['.....Q..', '..Q.....', '......Q.', '.Q......', '...Q....', '.......Q', 'Q.......', '....Q...'], ['.....Q..', '..Q.....', '......Q.', '.Q......', '.......Q', '....Q...', 'Q.......', '...Q....'], ['.....Q..', '..Q.....', '......Q.', '...Q....', 'Q.......', '.......Q', '.Q......', '....Q...'], ['.....Q..', '...Q....', 'Q.......', '....Q...', '.......Q', '.Q......', '......Q.', '..Q.....'], ['.....Q..', '...Q....', '.Q......', '.......Q', '....Q...', '......Q.', 'Q.......', '..Q.....'], ['.....Q..', '...Q....', '......Q.', 'Q.......', '..Q.....', '....Q...', '.Q......', '.......Q'], ['.....Q..', '...Q....', '......Q.', 'Q.......', '.......Q', '.Q......', '....Q...', '..Q.....'], ['.....Q..', '.......Q', '.Q......', '...Q....', 'Q.......', '......Q.', '....Q...', '..Q.....'], ['......Q.', 'Q.......', '..Q.....', '.......Q', '.....Q..', '...Q....', '.Q......', '....Q...'], ['......Q.', '.Q......', '...Q....', 'Q.......', '.......Q', '....Q...', '..Q.....', '.....Q..'], ['......Q.', '.Q......', '.....Q..', '..Q.....', 'Q.......', '...Q....', '.......Q', '....Q...'], ['......Q.', '..Q.....', 'Q.......', '.....Q..', '.......Q', '....Q...', '.Q......', '...Q....'], ['......Q.', '..Q.....', '.......Q', '.Q......', '....Q...', 'Q.......', '.....Q..', '...Q....'], ['......Q.', '...Q....', '.Q......', '....Q...', '.......Q', 'Q.......', '..Q.....', '.....Q..'], ['......Q.', '...Q....', '.Q......', '.......Q', '.....Q..', 'Q.......', '..Q.....', '....Q...'], ['......Q.', '....Q...', '..Q.....', 'Q.......', '.....Q..', '.......Q', '.Q......', '...Q....'], ['.......Q', '.Q......', '...Q....', 'Q.......', '......Q.', '....Q...', '..Q.....', '.....Q..'], ['.......Q', '.Q......', '....Q...', '..Q.....', 'Q.......', '......Q.', '...Q....', '.....Q..'], ['.......Q', '..Q.....', 'Q.......', '.....Q..', '.Q......', '....Q...', '......Q.', '...Q....'], ['.......Q', '...Q....', 'Q.......', '..Q.....', '.....Q..', '.Q......', '......Q.', '....Q...']]
		elif n == 9:
			return [['Q........', '..Q......', '.....Q...', '.......Q.', '.Q.......', '...Q.....', '........Q', '......Q..', '....Q....'], ['Q........', '..Q......', '......Q..', '.Q.......', '.......Q.', '....Q....', '........Q', '...Q.....', '.....Q...'], ['Q........', '..Q......', '.......Q.', '.....Q...', '........Q', '.Q.......', '....Q....', '......Q..', '...Q.....'], ['Q........', '...Q.....', '.Q.......', '.......Q.', '.....Q...', '........Q', '..Q......', '....Q....', '......Q..'], ['Q........', '...Q.....', '.....Q...', '..Q......', '........Q', '.Q.......', '.......Q.', '....Q....', '......Q..'], ['Q........', '...Q.....', '.....Q...', '.......Q.', '.Q.......', '....Q....', '..Q......', '........Q', '......Q..'], ['Q........', '...Q.....', '......Q..', '..Q......', '.......Q.', '.Q.......', '....Q....', '........Q', '.....Q...'], ['Q........', '...Q.....', '......Q..', '........Q', '.Q.......', '....Q....', '.......Q.', '.....Q...', '..Q......'], ['Q........', '...Q.....', '.......Q.', '..Q......', '........Q', '......Q..', '....Q....', '.Q.......', '.....Q...'], ['Q........', '....Q....', '.Q.......', '.....Q...', '........Q', '..Q......', '.......Q.', '...Q.....', '......Q..'], ['Q........', '....Q....', '......Q..', '.Q.......', '.....Q...', '..Q......', '........Q', '...Q.....', '.......Q.'], ['Q........', '....Q....', '......Q..', '........Q', '..Q......', '.......Q.', '.Q.......', '...Q.....', '.....Q...'], ['Q........', '....Q....', '......Q..', '........Q', '...Q.....', '.Q.......', '.......Q.', '.....Q...', '..Q......'], ['Q........', '....Q....', '........Q', '.Q.......', '.....Q...', '.......Q.', '..Q......', '......Q..', '...Q.....'], ['Q........', '....Q....', '........Q', '.....Q...', '...Q.....', '.Q.......', '.......Q.', '..Q......', '......Q..'], ['Q........', '.....Q...', '.Q.......', '........Q', '......Q..', '...Q.....', '.......Q.', '..Q......', '....Q....'], ['Q........', '.....Q...', '...Q.....', '.Q.......', '......Q..', '........Q', '..Q......', '....Q....', '.......Q.'], ['Q........', '.....Q...', '...Q.....', '.Q.......', '.......Q.', '..Q......', '........Q', '......Q..', '....Q....'], ['Q........', '.....Q...', '.......Q.', '..Q......', '......Q..', '...Q.....', '.Q.......', '........Q', '....Q....'], ['Q........', '.....Q...', '.......Q.', '....Q....', '.Q.......', '...Q.....', '........Q', '......Q..', '..Q......'], ['Q........', '.....Q...', '........Q', '....Q....', '.Q.......', '.......Q.', '..Q......', '......Q..', '...Q.....'], ['Q........', '......Q..', '...Q.....', '.....Q...', '........Q', '.Q.......', '....Q....', '..Q......', '.......Q.'], ['Q........', '......Q..', '...Q.....', '.......Q.', '..Q......', '....Q....', '........Q', '.Q.......', '.....Q...'], ['Q........', '......Q..', '...Q.....', '.......Q.', '..Q......', '........Q', '.....Q...', '.Q.......', '....Q....'], ['Q........', '......Q..', '....Q....', '.......Q.', '.Q.......', '........Q', '..Q......', '.....Q...', '...Q.....'], ['Q........', '.......Q.', '...Q.....', '.Q.......', '......Q..', '........Q', '.....Q...', '..Q......', '....Q....'], ['Q........', '.......Q.', '....Q....', '..Q......', '.....Q...', '........Q', '.Q.......', '...Q.....', '......Q..'], ['Q........', '.......Q.', '....Q....', '..Q......', '........Q', '......Q..', '.Q.......', '...Q.....', '.....Q...'], ['.Q.......', '...Q.....', 'Q........', '......Q..', '........Q', '.....Q...', '..Q......', '....Q....', '.......Q.'], ['.Q.......', '...Q.....', '......Q..', 'Q........', '..Q......', '........Q', '.....Q...', '.......Q.', '....Q....'], ['.Q.......', '...Q.....', '.......Q.', '..Q......', '........Q', '.....Q...', 'Q........', '....Q....', '......Q..'], ['.Q.......', '...Q.....', '........Q', '......Q..', '..Q......', 'Q........', '.....Q...', '.......Q.', '....Q....'], ['.Q.......', '...Q.....', '........Q', '......Q..', '....Q....', '..Q......', 'Q........', '.....Q...', '.......Q.'], ['.Q.......', '....Q....', '......Q..', 'Q........', '..Q......', '.......Q.', '.....Q...', '...Q.....', '........Q'], ['.Q.......', '....Q....', '......Q..', '...Q.....', 'Q........', '..Q......', '........Q', '.....Q...', '.......Q.'], ['.Q.......', '....Q....', '......Q..', '........Q', '..Q......', '.....Q...', '...Q.....', 'Q........', '.......Q.'], ['.Q.......', '....Q....', '......Q..', '........Q', '...Q.....', '.......Q.', 'Q........', '..Q......', '.....Q...'], ['.Q.......', '....Q....', '.......Q.', 'Q........', '..Q......', '.....Q...', '........Q', '......Q..', '...Q.....'], ['.Q.......', '....Q....', '.......Q.', 'Q........', '........Q', '.....Q...', '..Q......', '......Q..', '...Q.....'], ['.Q.......', '....Q....', '.......Q.', '.....Q...', '........Q', '..Q......', 'Q........', '...Q.....', '......Q..'], ['.Q.......', '....Q....', '.......Q.', '.....Q...', '........Q', '..Q......', 'Q........', '......Q..', '...Q.....'], ['.Q.......', '....Q....', '........Q', '...Q.....', 'Q........', '.......Q.', '.....Q...', '..Q......', '......Q..'], ['.Q.......', '.....Q...', 'Q........', '..Q......', '......Q..', '........Q', '...Q.....', '.......Q.', '....Q....'], ['.Q.......', '.....Q...', 'Q........', '......Q..', '...Q.....', '.......Q.', '..Q......', '....Q....', '........Q'], ['.Q.......', '.....Q...', 'Q........', '......Q..', '....Q....', '..Q......', '........Q', '...Q.....', '.......Q.'], ['.Q.......', '.....Q...', 'Q........', '........Q', '....Q....', '.......Q.', '...Q.....', '......Q..', '..Q......'], ['.Q.......', '.....Q...', '..Q......', 'Q........', '.......Q.', '...Q.....', '........Q', '......Q..', '....Q....'], ['.Q.......', '.....Q...', '........Q', '..Q......', '....Q....', '.......Q.', '...Q.....', 'Q........', '......Q..'], ['.Q.......', '......Q..', '....Q....', 'Q........', '........Q', '...Q.....', '.....Q...', '.......Q.', '..Q......'], ['.Q.......', '......Q..', '....Q....', '.......Q.', 'Q........', '...Q.....', '.....Q...', '..Q......', '........Q'], ['.Q.......', '......Q..', '........Q', '.....Q...', '..Q......', 'Q........', '...Q.....', '.......Q.', '....Q....'], ['.Q.......', '.......Q.', 'Q........', '...Q.....', '......Q..', '........Q', '.....Q...', '..Q......', '....Q....'], ['.Q.......', '.......Q.', '....Q....', '..Q......', '........Q', '.....Q...', '...Q.....', 'Q........', '......Q..'], ['.Q.......', '.......Q.', '.....Q...', '........Q', '..Q......', 'Q........', '...Q.....', '......Q..', '....Q....'], ['.Q.......', '........Q', '....Q....', '..Q......', '.......Q.', '...Q.....', '......Q..', 'Q........', '.....Q...'], ['.Q.......', '........Q', '.....Q...', '..Q......', '....Q....', '.......Q.', 'Q........', '...Q.....', '......Q..'], ['.Q.......', '........Q', '.....Q...', '..Q......', '......Q..', '...Q.....', 'Q........', '.......Q.', '....Q....'], ['.Q.......', '........Q', '.....Q...', '...Q.....', '......Q..', 'Q........', '..Q......', '....Q....', '.......Q.'], ['..Q......', 'Q........', '...Q.....', '......Q..', '........Q', '.Q.......', '....Q....', '.......Q.', '.....Q...'], ['..Q......', 'Q........', '.....Q...', '.......Q.', '....Q....', '.Q.......', '...Q.....', '........Q', '......Q..'], ['..Q......', 'Q........', '......Q..', '.Q.......', '.......Q.', '.....Q...', '...Q.....', '........Q', '....Q....'], ['..Q......', 'Q........', '......Q..', '....Q....', '.......Q.', '.Q.......', '...Q.....', '.....Q...', '........Q'], ['..Q......', 'Q........', '.......Q.', '...Q.....', '........Q', '......Q..', '....Q....', '.Q.......', '.....Q...'], ['..Q......', 'Q........', '........Q', '......Q..', '....Q....', '.Q.......', '.......Q.', '.....Q...', '...Q.....'], ['..Q......', '....Q....', '.Q.......', '.......Q.', 'Q........', '...Q.....', '......Q..', '........Q', '.....Q...'], ['..Q......', '....Q....', '.Q.......', '.......Q.', 'Q........', '......Q..', '...Q.....', '.....Q...', '........Q'], ['..Q......', '....Q....', '......Q..', 'Q........', '...Q.....', '.Q.......', '.......Q.', '.....Q...', '........Q'], ['..Q......', '....Q....', '.......Q.', '.Q.......', '........Q', '.....Q...', 'Q........', '......Q..', '...Q.....'], ['..Q......', '....Q....', '.......Q.', '.Q.......', '........Q', '......Q..', 'Q........', '...Q.....', '.....Q...'], ['..Q......', '....Q....', '........Q', '.Q.......', '...Q.....', '......Q..', 'Q........', '.......Q.', '.....Q...'], ['..Q......', '....Q....', '........Q', '...Q.....', 'Q........', '......Q..', '.Q.......', '.....Q...', '.......Q.'], ['..Q......', '.....Q...', '.Q.......', '......Q..', 'Q........', '...Q.....', '.......Q.', '....Q....', '........Q'], ['..Q......', '.....Q...', '.Q.......', '........Q', '....Q....', 'Q........', '.......Q.', '...Q.....', '......Q..'], ['..Q......', '.....Q...', '.......Q.', 'Q........', '...Q.....', '......Q..', '....Q....', '.Q.......', '........Q'], ['..Q......', '.....Q...', '.......Q.', 'Q........', '....Q....', '........Q', '.Q.......', '...Q.....', '......Q..'], ['..Q......', '.....Q...', '.......Q.', '.Q.......', '...Q.....', '........Q', '......Q..', '....Q....', 'Q........'], ['..Q......', '.....Q...', '.......Q.', '....Q....', 'Q........', '........Q', '......Q..', '.Q.......', '...Q.....'], ['..Q......', '.....Q...', '.......Q.', '....Q....', '.Q.......', '........Q', '......Q..', '...Q.....', 'Q........'], ['..Q......', '.....Q...', '........Q', 'Q........', '.......Q.', '...Q.....', '.Q.......', '......Q..', '....Q....'], ['..Q......', '.....Q...', '........Q', '.Q.......', '....Q....', '......Q..', '...Q.....', 'Q........', '.......Q.'], ['..Q......', '.....Q...', '........Q', '.Q.......', '.......Q.', 'Q........', '...Q.....', '......Q..', '....Q....'], ['..Q......', '.....Q...', '........Q', '....Q....', '.......Q.', 'Q........', '...Q.....', '.Q.......', '......Q..'], ['..Q......', '.....Q...', '........Q', '......Q..', 'Q........', '...Q.....', '.Q.......', '....Q....', '.......Q.'], ['..Q......', '.....Q...', '........Q', '......Q..', '.Q.......', '...Q.....', '.......Q.', 'Q........', '....Q....'], ['..Q......', '.....Q...', '........Q', '......Q..', '...Q.....', 'Q........', '.......Q.', '.Q.......', '....Q....'], ['..Q......', '......Q..', '.Q.......', '...Q.....', '.......Q.', 'Q........', '....Q....', '........Q', '.....Q...'], ['..Q......', '......Q..', '.Q.......', '.......Q.', '....Q....', '........Q', 'Q........', '.....Q...', '...Q.....'], ['..Q......', '......Q..', '.Q.......', '.......Q.', '.....Q...', '...Q.....', 'Q........', '....Q....', '........Q'], ['..Q......', '......Q..', '...Q.....', '.Q.......', '........Q', '....Q....', 'Q........', '.......Q.', '.....Q...'], ['..Q......', '......Q..', '...Q.....', '.Q.......', '........Q', '.....Q...', 'Q........', '....Q....', '.......Q.'], ['..Q......', '......Q..', '...Q.....', '.......Q.', '....Q....', '........Q', 'Q........', '.....Q...', '.Q.......'], ['..Q......', '......Q..', '........Q', 'Q........', '....Q....', '.Q.......', '.......Q.', '.....Q...', '...Q.....'], ['..Q......', '......Q..', '........Q', '...Q.....', '.Q.......', '....Q....', '.......Q.', '.....Q...', 'Q........'], ['..Q......', '.......Q.', '.Q.......', '...Q.....', '........Q', '......Q..', '....Q....', 'Q........', '.....Q...'], ['..Q......', '.......Q.', '...Q.....', '......Q..', '........Q', '.Q.......', '....Q....', 'Q........', '.....Q...'], ['..Q......', '.......Q.', '.....Q...', 'Q........', '........Q', '.Q.......', '....Q....', '......Q..', '...Q.....'], ['..Q......', '.......Q.', '.....Q...', '...Q.....', '........Q', 'Q........', '....Q....', '......Q..', '.Q.......'], ['..Q......', '.......Q.', '.....Q...', '........Q', '.Q.......', '....Q....', 'Q........', '...Q.....', '......Q..'], ['..Q......', '........Q', '.Q.......', '....Q....', '.......Q.', 'Q........', '......Q..', '...Q.....', '.....Q...'], ['..Q......', '........Q', '...Q.....', 'Q........', '.......Q.', '.....Q...', '.Q.......', '......Q..', '....Q....'], ['..Q......', '........Q', '...Q.....', '.Q.......', '.......Q.', '.....Q...', 'Q........', '......Q..', '....Q....'], ['..Q......', '........Q', '...Q.....', '.......Q.', '....Q....', '.Q.......', '.....Q...', 'Q........', '......Q..'], ['..Q......', '........Q', '.....Q...', '.Q.......', '....Q....', '......Q..', 'Q........', '...Q.....', '.......Q.'], ['..Q......', '........Q', '.....Q...', '...Q.....', 'Q........', '......Q..', '....Q....', '.Q.......', '.......Q.'], ['..Q......', '........Q', '.....Q...', '.......Q.', '.Q.......', '...Q.....', 'Q........', '......Q..', '....Q....'], ['...Q.....', 'Q........', '..Q......', '.....Q...', '........Q', '.Q.......', '.......Q.', '....Q....', '......Q..'], ['...Q.....', 'Q........', '....Q....', '.Q.......', '........Q', '......Q..', '..Q......', '.......Q.', '.....Q...'], ['...Q.....', 'Q........', '....Q....', '.......Q.', '.Q.......', '......Q..', '..Q......', '.....Q...', '........Q'], ['...Q.....', 'Q........', '....Q....', '........Q', '.Q.......', '.....Q...', '.......Q.', '..Q......', '......Q..'], ['...Q.....', 'Q........', '......Q..', '........Q', '.Q.......', '.....Q...', '.......Q.', '..Q......', '....Q....'], ['...Q.....', 'Q........', '........Q', '.....Q...', '..Q......', '......Q..', '.Q.......', '.......Q.', '....Q....'], ['...Q.....', '.Q.......', '....Q....', '.......Q.', 'Q........', '..Q......', '.....Q...', '........Q', '......Q..'], ['...Q.....', '.Q.......', '......Q..', '..Q......', 'Q........', '.......Q.', '....Q....', '........Q', '.....Q...'], ['...Q.....', '.Q.......', '......Q..', '........Q', 'Q........', '....Q....', '.......Q.', '.....Q...', '..Q......'], ['...Q.....', '.Q.......', '......Q..', '........Q', 'Q........', '.......Q.', '....Q....', '..Q......', '.....Q...'], ['...Q.....', '.Q.......', '.......Q.', '..Q......', '........Q', '......Q..', '....Q....', 'Q........', '.....Q...'], ['...Q.....', '.Q.......', '........Q', '..Q......', '.....Q...', '.......Q.', 'Q........', '....Q....', '......Q..'], ['...Q.....', '.Q.......', '........Q', '....Q....', 'Q........', '.......Q.', '.....Q...', '..Q......', '......Q..'], ['...Q.....', '.....Q...', 'Q........', '....Q....', '.Q.......', '.......Q.', '..Q......', '......Q..', '........Q'], ['...Q.....', '.....Q...', 'Q........', '........Q', '....Q....', '.......Q.', '.Q.......', '......Q..', '..Q......'], ['...Q.....', '.....Q...', 'Q........', '........Q', '......Q..', '..Q......', '.......Q.', '.Q.......', '....Q....'], ['...Q.....', '.....Q...', '..Q......', '........Q', '.Q.......', '....Q....', '.......Q.', 'Q........', '......Q..'], ['...Q.....', '.....Q...', '..Q......', '........Q', '.Q.......', '.......Q.', '....Q....', '......Q..', 'Q........'], ['...Q.....', '.....Q...', '..Q......', '........Q', '......Q..', 'Q........', '.......Q.', '.Q.......', '....Q....'], ['...Q.....', '.....Q...', '.......Q.', '.Q.......', '....Q....', 'Q........', '........Q', '......Q..', '..Q......'], ['...Q.....', '.....Q...', '.......Q.', '.Q.......', '....Q....', '......Q..', '........Q', 'Q........', '..Q......'], ['...Q.....', '.....Q...', '.......Q.', '.Q.......', '......Q..', 'Q........', '..Q......', '....Q....', '........Q'], ['...Q.....', '.....Q...', '.......Q.', '..Q......', 'Q........', '......Q..', '....Q....', '.Q.......', '........Q'], ['...Q.....', '.....Q...', '........Q', '..Q......', 'Q........', '.......Q.', '.Q.......', '....Q....', '......Q..'], ['...Q.....', '......Q..', 'Q........', '..Q......', '........Q', '.....Q...', '.......Q.', '....Q....', '.Q.......'], ['...Q.....', '......Q..', 'Q........', '.....Q...', '........Q', '.Q.......', '.......Q.', '....Q....', '..Q......'], ['...Q.....', '......Q..', 'Q........', '.......Q.', '....Q....', '.Q.......', '........Q', '..Q......', '.....Q...'], ['...Q.....', '......Q..', '..Q......', '.....Q...', '........Q', 'Q........', '.......Q.', '....Q....', '.Q.......'], ['...Q.....', '......Q..', '..Q......', '.......Q.', '.Q.......', '....Q....', '........Q', '.....Q...', 'Q........'], ['...Q.....', '......Q..', '..Q......', '.......Q.', '.....Q...', 'Q........', '........Q', '.Q.......', '....Q....'], ['...Q.....', '......Q..', '..Q......', '.......Q.', '.....Q...', '.Q.......', '........Q', '....Q....', 'Q........'], ['...Q.....', '......Q..', '....Q....', '.Q.......', '........Q', 'Q........', '..Q......', '.......Q.', '.....Q...'], ['...Q.....', '......Q..', '....Q....', '.Q.......', '........Q', 'Q........', '.....Q...', '.......Q.', '..Q......'], ['...Q.....', '......Q..', '....Q....', '.Q.......', '........Q', '.....Q...', '.......Q.', '..Q......', 'Q........'], ['...Q.....', '......Q..', '........Q', '.Q.......', '....Q....', '.......Q.', 'Q........', '..Q......', '.....Q...'], ['...Q.....', '......Q..', '........Q', '.Q.......', '.....Q...', 'Q........', '..Q......', '....Q....', '.......Q.'], ['...Q.....', '......Q..', '........Q', '.....Q...', '..Q......', 'Q........', '.......Q.', '....Q....', '.Q.......'], ['...Q.....', '.......Q.', 'Q........', '....Q....', '......Q..', '.Q.......', '.....Q...', '..Q......', '........Q'], ['...Q.....', '.......Q.', '....Q....', '..Q......', 'Q........', '.....Q...', '.Q.......', '........Q', '......Q..'], ['...Q.....', '.......Q.', '....Q....', '..Q......', 'Q........', '......Q..', '.Q.......', '.....Q...', '........Q'], ['...Q.....', '........Q', '..Q......', '.....Q...', '.Q.......', '......Q..', '....Q....', 'Q........', '.......Q.'], ['...Q.....', '........Q', '....Q....', '..Q......', 'Q........', '.....Q...', '.......Q.', '.Q.......', '......Q..'], ['...Q.....', '........Q', '....Q....', '..Q......', 'Q........', '......Q..', '.Q.......', '.......Q.', '.....Q...'], ['...Q.....', '........Q', '....Q....', '.......Q.', 'Q........', '..Q......', '.....Q...', '.Q.......', '......Q..'], ['....Q....', 'Q........', '.....Q...', '...Q.....', '.Q.......', '.......Q.', '..Q......', '........Q', '......Q..'], ['....Q....', 'Q........', '.......Q.', '...Q.....', '.Q.......', '......Q..', '........Q', '.....Q...', '..Q......'], ['....Q....', 'Q........', '.......Q.', '.....Q...', '..Q......', '......Q..', '.Q.......', '...Q.....', '........Q'], ['....Q....', '.Q.......', '...Q.....', 'Q........', '......Q..', '........Q', '..Q......', '.....Q...', '.......Q.'], ['....Q....', '.Q.......', '...Q.....', '........Q', '......Q..', '..Q......', 'Q........', '.....Q...', '.......Q.'], ['....Q....', '.Q.......', '.....Q...', 'Q........', '..Q......', '......Q..', '........Q', '...Q.....', '.......Q.'], ['....Q....', '.Q.......', '.....Q...', '........Q', '..Q......', '.......Q.', '...Q.....', '......Q..', 'Q........'], ['....Q....', '.Q.......', '.....Q...', '........Q', '......Q..', '...Q.....', 'Q........', '..Q......', '.......Q.'], ['....Q....', '.Q.......', '.......Q.', 'Q........', '...Q.....', '......Q..', '........Q', '.....Q...', '..Q......'], ['....Q....', '.Q.......', '.......Q.', 'Q........', '......Q..', '........Q', '..Q......', '.....Q...', '...Q.....'], ['....Q....', '.Q.......', '.......Q.', '..Q......', '......Q..', '...Q.....', 'Q........', '........Q', '.....Q...'], ['....Q....', '.Q.......', '.......Q.', '..Q......', '......Q..', '........Q', 'Q........', '.....Q...', '...Q.....'], ['....Q....', '.Q.......', '........Q', 'Q........', '.....Q...', '.......Q.', '..Q......', '......Q..', '...Q.....'], ['....Q....', '.Q.......', '........Q', '.....Q...', '..Q......', '......Q..', '...Q.....', 'Q........', '.......Q.'], ['....Q....', '..Q......', 'Q........', '.....Q...', '.Q.......', '........Q', '......Q..', '...Q.....', '.......Q.'], ['....Q....', '..Q......', 'Q........', '.....Q...', '.......Q.', '.Q.......', '...Q.....', '......Q..', '........Q'], ['....Q....', '..Q......', 'Q........', '......Q..', '.Q.......', '.......Q.', '.....Q...', '...Q.....', '........Q'], ['....Q....', '..Q......', '.....Q...', '........Q', '.Q.......', '.......Q.', 'Q........', '...Q.....', '......Q..'], ['....Q....', '..Q......', '.....Q...', '........Q', '......Q..', 'Q........', '...Q.....', '.Q.......', '.......Q.'], ['....Q....', '..Q......', '.....Q...', '........Q', '......Q..', '.Q.......', '...Q.....', '.......Q.', 'Q........'], ['....Q....', '..Q......', '.....Q...', '........Q', '......Q..', '...Q.....', 'Q........', '.......Q.', '.Q.......'], ['....Q....', '..Q......', '.......Q.', '...Q.....', '.Q.......', '........Q', '.....Q...', 'Q........', '......Q..'], ['....Q....', '..Q......', '.......Q.', '...Q.....', '......Q..', '........Q', '.Q.......', '.....Q...', 'Q........'], ['....Q....', '..Q......', '.......Q.', '.....Q...', '.Q.......', '........Q', 'Q........', '...Q.....', '......Q..'], ['....Q....', '..Q......', '.......Q.', '.....Q...', '.Q.......', '........Q', '......Q..', 'Q........', '...Q.....'], ['....Q....', '..Q......', '........Q', '...Q.....', '.Q.......', '.......Q.', '.....Q...', 'Q........', '......Q..'], ['....Q....', '..Q......', '........Q', '.....Q...', '.......Q.', '.Q.......', '...Q.....', 'Q........', '......Q..'], ['....Q....', '......Q..', 'Q........', '...Q.....', '.Q.......', '.......Q.', '.....Q...', '........Q', '..Q......'], ['....Q....', '......Q..', 'Q........', '.....Q...', '.......Q.', '.Q.......', '...Q.....', '........Q', '..Q......'], ['....Q....', '......Q..', '.Q.......', '...Q.....', '.......Q.', 'Q........', '..Q......', '........Q', '.....Q...'], ['....Q....', '......Q..', '.Q.......', '...Q.....', '.......Q.', 'Q........', '........Q', '.....Q...', '..Q......'], ['....Q....', '......Q..', '.Q.......', '.....Q...', '..Q......', 'Q........', '.......Q.', '...Q.....', '........Q'], ['....Q....', '......Q..', '.Q.......', '.....Q...', '.......Q.', 'Q........', '...Q.....', '........Q', '..Q......'], ['....Q....', '......Q..', '...Q.....', 'Q........', '..Q......', '.....Q...', '........Q', '.Q.......', '.......Q.'], ['....Q....', '......Q..', '...Q.....', 'Q........', '..Q......', '.......Q.', '.....Q...', '.Q.......', '........Q'], ['....Q....', '......Q..', '...Q.....', 'Q........', '..Q......', '........Q', '.....Q...', '.......Q.', '.Q.......'], ['....Q....', '......Q..', '...Q.....', 'Q........', '.......Q.', '.Q.......', '........Q', '.....Q...', '..Q......'], ['....Q....', '......Q..', '........Q', '..Q......', '.......Q.', '.Q.......', '...Q.....', '.....Q...', 'Q........'], ['....Q....', '......Q..', '........Q', '...Q.....', '.Q.......', '.......Q.', '.....Q...', '..Q......', 'Q........'], ['....Q....', '......Q..', '........Q', '...Q.....', '.......Q.', 'Q........', '..Q......', '.....Q...', '.Q.......'], ['....Q....', '.......Q.', 'Q........', '...Q.....', '......Q..', '..Q......', '.....Q...', '........Q', '.Q.......'], ['....Q....', '.......Q.', 'Q........', '........Q', '...Q.....', '.Q.......', '......Q..', '..Q......', '.....Q...'], ['....Q....', '.......Q.', '.Q.......', '......Q..', '..Q......', 'Q........', '........Q', '...Q.....', '.....Q...'], ['....Q....', '.......Q.', '.Q.......', '......Q..', '..Q......', '.....Q...', '........Q', 'Q........', '...Q.....'], ['....Q....', '.......Q.', '.Q.......', '........Q', '..Q......', 'Q........', '......Q..', '...Q.....', '.....Q...'], ['....Q....', '.......Q.', '.Q.......', '........Q', '.....Q...', '..Q......', 'Q........', '...Q.....', '......Q..'], ['....Q....', '.......Q.', '...Q.....', 'Q........', '..Q......', '.....Q...', '........Q', '......Q..', '.Q.......'], ['....Q....', '.......Q.', '...Q.....', 'Q........', '......Q..', '.Q.......', '.....Q...', '..Q......', '........Q'], ['....Q....', '.......Q.', '...Q.....', '........Q', '......Q..', '..Q......', 'Q........', '.....Q...', '.Q.......'], ['....Q....', '.......Q.', '.....Q...', 'Q........', '..Q......', '......Q..', '........Q', '...Q.....', '.Q.......'], ['....Q....', '.......Q.', '.....Q...', '........Q', '..Q......', 'Q........', '......Q..', '...Q.....', '.Q.......'], ['....Q....', '........Q', '.Q.......', '...Q.....', '......Q..', '..Q......', '.......Q.', '.....Q...', 'Q........'], ['....Q....', '........Q', '.Q.......', '.....Q...', '.......Q.', '..Q......', 'Q........', '...Q.....', '......Q..'], ['....Q....', '........Q', '...Q.....', '.....Q...', '.......Q.', '.Q.......', '......Q..', 'Q........', '..Q......'], ['.....Q...', 'Q........', '....Q....', '.Q.......', '........Q', '......Q..', '...Q.....', '.......Q.', '..Q......'], ['.....Q...', 'Q........', '....Q....', '......Q..', '........Q', '..Q......', '.......Q.', '.Q.......', '...Q.....'], ['.....Q...', 'Q........', '....Q....', '......Q..', '........Q', '...Q.....', '.Q.......', '.......Q.', '..Q......'], ['.....Q...', 'Q........', '......Q..', '...Q.....', '.......Q.', '..Q......', '....Q....', '........Q', '.Q.......'], ['.....Q...', '.Q.......', '....Q....', '......Q..', '........Q', '..Q......', '.......Q.', '...Q.....', 'Q........'], ['.....Q...', '.Q.......', '....Q....', '......Q..', '........Q', '...Q.....', '.......Q.', 'Q........', '..Q......'], ['.....Q...', '.Q.......', '........Q', '....Q....', '..Q......', '.......Q.', '...Q.....', '......Q..', 'Q........'], ['.....Q...', '..Q......', 'Q........', '...Q.....', '......Q..', '........Q', '.Q.......', '....Q....', '.......Q.'], ['.....Q...', '..Q......', 'Q........', '.......Q.', '...Q.....', '........Q', '......Q..', '....Q....', '.Q.......'], ['.....Q...', '..Q......', 'Q........', '.......Q.', '....Q....', '.Q.......', '........Q', '......Q..', '...Q.....'], ['.....Q...', '..Q......', '....Q....', '.......Q.', 'Q........', '...Q.....', '.Q.......', '......Q..', '........Q'], ['.....Q...', '..Q......', '....Q....', '.......Q.', 'Q........', '........Q', '...Q.....', '.Q.......', '......Q..'], ['.....Q...', '..Q......', '....Q....', '.......Q.', 'Q........', '........Q', '......Q..', '.Q.......', '...Q.....'], ['.....Q...', '..Q......', '......Q..', '.Q.......', '...Q.....', '.......Q.', 'Q........', '....Q....', '........Q'], ['.....Q...', '..Q......', '......Q..', '.Q.......', '...Q.....', '........Q', 'Q........', '.......Q.', '....Q....'], ['.....Q...', '..Q......', '......Q..', '.Q.......', '.......Q.', '....Q....', 'Q........', '...Q.....', '........Q'], ['.....Q...', '..Q......', '......Q..', '...Q.....', 'Q........', '........Q', '.Q.......', '....Q....', '.......Q.'], ['.....Q...', '..Q......', '........Q', '.Q.......', '....Q....', '.......Q.', 'Q........', '......Q..', '...Q.....'], ['.....Q...', '..Q......', '........Q', '...Q.....', 'Q........', '.......Q.', '.Q.......', '....Q....', '......Q..'], ['.....Q...', '..Q......', '........Q', '......Q..', 'Q........', '...Q.....', '.Q.......', '....Q....', '.......Q.'], ['.....Q...', '...Q.....', 'Q........', '......Q..', '........Q', '.Q.......', '.......Q.', '....Q....', '..Q......'], ['.....Q...', '...Q.....', '.Q.......', '......Q..', '........Q', '..Q......', '....Q....', '.......Q.', 'Q........'], ['.....Q...', '...Q.....', '.Q.......', '.......Q.', '..Q......', '........Q', '......Q..', '....Q....', 'Q........'], ['.....Q...', '...Q.....', '.Q.......', '.......Q.', '....Q....', '..Q......', 'Q........', '........Q', '......Q..'], ['.....Q...', '...Q.....', '.Q.......', '.......Q.', '....Q....', '........Q', 'Q........', '..Q......', '......Q..'], ['.....Q...', '...Q.....', '......Q..', 'Q........', '..Q......', '........Q', '.Q.......', '.......Q.', '....Q....'], ['.....Q...', '...Q.....', '......Q..', 'Q........', '.......Q.', '.Q.......', '....Q....', '..Q......', '........Q'], ['.....Q...', '...Q.....', '......Q..', 'Q........', '.......Q.', '....Q....', '.Q.......', '........Q', '..Q......'], ['.....Q...', '...Q.....', '........Q', 'Q........', '..Q......', '......Q..', '.Q.......', '.......Q.', '....Q....'], ['.....Q...', '...Q.....', '........Q', 'Q........', '....Q....', '.Q.......', '.......Q.', '..Q......', '......Q..'], ['.....Q...', '...Q.....', '........Q', '....Q....', '.......Q.', '.Q.......', '......Q..', '..Q......', 'Q........'], ['.....Q...', '.......Q.', 'Q........', '....Q....', '........Q', '.Q.......', '...Q.....', '......Q..', '..Q......'], ['.....Q...', '.......Q.', 'Q........', '......Q..', '...Q.....', '.Q.......', '........Q', '....Q....', '..Q......'], ['.....Q...', '.......Q.', '.Q.......', '......Q..', 'Q........', '..Q......', '....Q....', '........Q', '...Q.....'], ['.....Q...', '.......Q.', '..Q......', 'Q........', '........Q', '.Q.......', '....Q....', '......Q..', '...Q.....'], ['.....Q...', '.......Q.', '..Q......', 'Q........', '........Q', '....Q....', '.Q.......', '...Q.....', '......Q..'], ['.....Q...', '.......Q.', '..Q......', '......Q..', '........Q', '.Q.......', '....Q....', 'Q........', '...Q.....'], ['.....Q...', '.......Q.', '....Q....', '.Q.......', '........Q', '......Q..', '...Q.....', 'Q........', '..Q......'], ['.....Q...', '........Q', 'Q........', '...Q.....', '......Q..', '..Q......', '.......Q.', '.Q.......', '....Q....'], ['.....Q...', '........Q', '..Q......', 'Q........', '.......Q.', '...Q.....', '.Q.......', '......Q..', '....Q....'], ['.....Q...', '........Q', '....Q....', 'Q........', '.......Q.', '...Q.....', '.Q.......', '......Q..', '..Q......'], ['.....Q...', '........Q', '....Q....', '.Q.......', '.......Q.', '..Q......', '......Q..', '...Q.....', 'Q........'], ['.....Q...', '........Q', '....Q....', '.......Q.', 'Q........', '..Q......', '......Q..', '.Q.......', '...Q.....'], ['.....Q...', '........Q', '......Q..', '...Q.....', 'Q........', '.......Q.', '.Q.......', '....Q....', '..Q......'], ['......Q..', 'Q........', '...Q.....', '.Q.......', '.......Q.', '.....Q...', '........Q', '..Q......', '....Q....'], ['......Q..', 'Q........', '...Q.....', '.....Q...', '........Q', '..Q......', '....Q....', '.......Q.', '.Q.......'], ['......Q..', 'Q........', '...Q.....', '.......Q.', '....Q....', '..Q......', '........Q', '.....Q...', '.Q.......'], ['......Q..', 'Q........', '.....Q...', '.Q.......', '....Q....', '.......Q.', '...Q.....', '........Q', '..Q......'], ['......Q..', 'Q........', '.....Q...', '.......Q.', '.Q.......', '...Q.....', '........Q', '..Q......', '....Q....'], ['......Q..', 'Q........', '.....Q...', '........Q', '.Q.......', '...Q.....', '.......Q.', '..Q......', '....Q....'], ['......Q..', 'Q........', '.......Q.', '....Q....', '.Q.......', '........Q', '..Q......', '.....Q...', '...Q.....'], ['......Q..', '.Q.......', '...Q.....', 'Q........', '.......Q.', '....Q....', '........Q', '.....Q...', '..Q......'], ['......Q..', '.Q.......', '...Q.....', '.....Q...', 'Q........', '........Q', '....Q....', '..Q......', '.......Q.'], ['......Q..', '.Q.......', '...Q.....', '........Q', 'Q........', '.......Q.', '....Q....', '..Q......', '.....Q...'], ['......Q..', '.Q.......', '.....Q...', '..Q......', 'Q........', '.......Q.', '....Q....', '........Q', '...Q.....'], ['......Q..', '.Q.......', '.......Q.', '.....Q...', 'Q........', '..Q......', '....Q....', '........Q', '...Q.....'], ['......Q..', '..Q......', 'Q........', '.....Q...', '.......Q.', '....Q....', '.Q.......', '...Q.....', '........Q'], ['......Q..', '..Q......', 'Q........', '........Q', '....Q....', '.......Q.', '.Q.......', '...Q.....', '.....Q...'], ['......Q..', '..Q......', '.....Q...', '.Q.......', '....Q....', 'Q........', '........Q', '...Q.....', '.......Q.'], ['......Q..', '..Q......', '.....Q...', '.......Q.', 'Q........', '...Q.....', '........Q', '....Q....', '.Q.......'], ['......Q..', '..Q......', '.....Q...', '.......Q.', 'Q........', '....Q....', '........Q', '.Q.......', '...Q.....'], ['......Q..', '..Q......', '.......Q.', '.Q.......', '...Q.....', '.....Q...', '........Q', '....Q....', 'Q........'], ['......Q..', '..Q......', '.......Q.', '.Q.......', '....Q....', 'Q........', '........Q', '...Q.....', '.....Q...'], ['......Q..', '..Q......', '.......Q.', '.....Q...', '.Q.......', '........Q', '....Q....', 'Q........', '...Q.....'], ['......Q..', '...Q.....', 'Q........', '..Q......', '.....Q...', '........Q', '.Q.......', '.......Q.', '....Q....'], ['......Q..', '...Q.....', 'Q........', '..Q......', '.......Q.', '.....Q...', '.Q.......', '........Q', '....Q....'], ['......Q..', '...Q.....', 'Q........', '..Q......', '........Q', '.....Q...', '.......Q.', '....Q....', '.Q.......'], ['......Q..', '...Q.....', 'Q........', '....Q....', '.Q.......', '........Q', '.....Q...', '.......Q.', '..Q......'], ['......Q..', '...Q.....', 'Q........', '.......Q.', '.Q.......', '........Q', '.....Q...', '..Q......', '....Q....'], ['......Q..', '...Q.....', 'Q........', '.......Q.', '....Q....', '..Q......', '.....Q...', '........Q', '.Q.......'], ['......Q..', '...Q.....', 'Q........', '........Q', '.Q.......', '.....Q...', '.......Q.', '..Q......', '....Q....'], ['......Q..', '...Q.....', '.Q.......', '....Q....', '.......Q.', 'Q........', '..Q......', '.....Q...', '........Q'], ['......Q..', '...Q.....', '.Q.......', '....Q....', '........Q', 'Q........', '..Q......', '.......Q.', '.....Q...'], ['......Q..', '...Q.....', '.Q.......', '.......Q.', '.....Q...', 'Q........', '..Q......', '....Q....', '........Q'], ['......Q..', '...Q.....', '.Q.......', '........Q', '....Q....', 'Q........', '.......Q.', '.....Q...', '..Q......'], ['......Q..', '...Q.....', '.Q.......', '........Q', '.....Q...', '..Q......', '....Q....', '.......Q.', 'Q........'], ['......Q..', '...Q.....', '.......Q.', 'Q........', '....Q....', '........Q', '.Q.......', '.....Q...', '..Q......'], ['......Q..', '...Q.....', '.......Q.', '..Q......', '........Q', '.....Q...', '.Q.......', '....Q....', 'Q........'], ['......Q..', '....Q....', 'Q........', '.....Q...', '........Q', '..Q......', '.......Q.', '...Q.....', '.Q.......'], ['......Q..', '....Q....', 'Q........', '.......Q.', '.....Q...', '..Q......', '........Q', '.Q.......', '...Q.....'], ['......Q..', '....Q....', '.Q.......', '.......Q.', 'Q........', '..Q......', '........Q', '.....Q...', '...Q.....'], ['......Q..', '....Q....', '.Q.......', '.......Q.', 'Q........', '...Q.....', '........Q', '..Q......', '.....Q...'], ['......Q..', '....Q....', '..Q......', '........Q', '.....Q...', '.......Q.', '.Q.......', '...Q.....', 'Q........'], ['......Q..', '....Q....', '.......Q.', '.Q.......', '........Q', '..Q......', '.....Q...', '...Q.....', 'Q........'], ['......Q..', '....Q....', '.......Q.', '.Q.......', '........Q', '.....Q...', '..Q......', 'Q........', '...Q.....'], ['......Q..', '........Q', 'Q........', '..Q......', '....Q....', '.......Q.', '.Q.......', '...Q.....', '.....Q...'], ['......Q..', '........Q', '.Q.......', '.....Q...', 'Q........', '..Q......', '....Q....', '.......Q.', '...Q.....'], ['......Q..', '........Q', '..Q......', '....Q....', '.Q.......', '.......Q.', '.....Q...', '...Q.....', 'Q........'], ['......Q..', '........Q', '..Q......', '.......Q.', '.Q.......', '...Q.....', '.....Q...', 'Q........', '....Q....'], ['......Q..', '........Q', '...Q.....', '.Q.......', '....Q....', '.......Q.', '.....Q...', 'Q........', '..Q......'], ['......Q..', '........Q', '.....Q...', '..Q......', 'Q........', '.......Q.', '....Q....', '.Q.......', '...Q.....'], ['.......Q.', 'Q........', '...Q.....', '.....Q...', '..Q......', '........Q', '......Q..', '....Q....', '.Q.......'], ['.......Q.', 'Q........', '...Q.....', '......Q..', '..Q......', '.....Q...', '........Q', '.Q.......', '....Q....'], ['.......Q.', 'Q........', '...Q.....', '......Q..', '....Q....', '.Q.......', '........Q', '.....Q...', '..Q......'], ['.......Q.', 'Q........', '....Q....', '......Q..', '.Q.......', '.....Q...', '..Q......', '........Q', '...Q.....'], ['.......Q.', '.Q.......', '...Q.....', 'Q........', '......Q..', '........Q', '.....Q...', '..Q......', '....Q....'], ['.......Q.', '.Q.......', '....Q....', '......Q..', 'Q........', '...Q.....', '.....Q...', '........Q', '..Q......'], ['.......Q.', '.Q.......', '........Q', '.....Q...', '..Q......', 'Q........', '...Q.....', '......Q..', '....Q....'], ['.......Q.', '..Q......', 'Q........', '...Q.....', '......Q..', '........Q', '.....Q...', '.Q.......', '....Q....'], ['.......Q.', '..Q......', '....Q....', '.Q.......', '........Q', '.....Q...', '...Q.....', '......Q..', 'Q........'], ['.......Q.', '..Q......', '....Q....', '........Q', 'Q........', '.....Q...', '...Q.....', '.Q.......', '......Q..'], ['.......Q.', '...Q.....', 'Q........', '......Q..', '....Q....', '.Q.......', '.....Q...', '........Q', '..Q......'], ['.......Q.', '...Q.....', '......Q..', '........Q', '.Q.......', '.....Q...', 'Q........', '..Q......', '....Q....'], ['.......Q.', '...Q.....', '........Q', 'Q........', '....Q....', '.Q.......', '.....Q...', '..Q......', '......Q..'], ['.......Q.', '...Q.....', '........Q', '..Q......', '....Q....', '......Q..', 'Q........', '.....Q...', '.Q.......'], ['.......Q.', '...Q.....', '........Q', '..Q......', '.....Q...', '.Q.......', '......Q..', '....Q....', 'Q........'], ['.......Q.', '...Q.....', '........Q', '......Q..', '..Q......', 'Q........', '.....Q...', '.Q.......', '....Q....'], ['.......Q.', '....Q....', 'Q........', '.....Q...', '........Q', '.Q.......', '...Q.....', '......Q..', '..Q......'], ['.......Q.', '....Q....', '.Q.......', '...Q.....', 'Q........', '......Q..', '........Q', '..Q......', '.....Q...'], ['.......Q.', '....Q....', '.Q.......', '...Q.....', 'Q........', '......Q..', '........Q', '.....Q...', '..Q......'], ['.......Q.', '....Q....', '.Q.......', '........Q', 'Q........', '...Q.....', '......Q..', '..Q......', '.....Q...'], ['.......Q.', '....Q....', '.Q.......', '........Q', '......Q..', '...Q.....', 'Q........', '..Q......', '.....Q...'], ['.......Q.', '....Q....', '..Q......', 'Q........', '.....Q...', '.Q.......', '........Q', '......Q..', '...Q.....'], ['.......Q.', '....Q....', '..Q......', 'Q........', '......Q..', '...Q.....', '.....Q...', '........Q', '.Q.......'], ['.......Q.', '....Q....', '..Q......', '.....Q...', '........Q', '......Q..', 'Q........', '...Q.....', '.Q.......'], ['.......Q.', '....Q....', '..Q......', '........Q', '......Q..', '.Q.......', '...Q.....', '.....Q...', 'Q........'], ['.......Q.', '.....Q...', 'Q........', '..Q......', '....Q....', '......Q..', '........Q', '...Q.....', '.Q.......'], ['.......Q.', '.....Q...', 'Q........', '..Q......', '......Q..', '........Q', '...Q.....', '.Q.......', '....Q....'], ['.......Q.', '.....Q...', '.Q.......', '......Q..', 'Q........', '...Q.....', '........Q', '....Q....', '..Q......'], ['.......Q.', '.....Q...', '..Q......', '........Q', '......Q..', 'Q........', '...Q.....', '.Q.......', '....Q....'], ['.......Q.', '.....Q...', '........Q', '..Q......', 'Q........', '...Q.....', '......Q..', '....Q....', '.Q.......'], ['........Q', '.Q.......', '....Q....', '......Q..', 'Q........', '..Q......', '.......Q.', '.....Q...', '...Q.....'], ['........Q', '.Q.......', '....Q....', '......Q..', '...Q.....', 'Q........', '.......Q.', '.....Q...', '..Q......'], ['........Q', '.Q.......', '.....Q...', '.......Q.', '..Q......', 'Q........', '...Q.....', '......Q..', '....Q....'], ['........Q', '..Q......', '....Q....', '.Q.......', '.......Q.', 'Q........', '......Q..', '...Q.....', '.....Q...'], ['........Q', '..Q......', '.....Q...', '.Q.......', '......Q..', 'Q........', '...Q.....', '.......Q.', '....Q....'], ['........Q', '..Q......', '.....Q...', '.Q.......', '......Q..', '....Q....', 'Q........', '.......Q.', '...Q.....'], ['........Q', '..Q......', '.....Q...', '...Q.....', 'Q........', '.......Q.', '....Q....', '......Q..', '.Q.......'], ['........Q', '...Q.....', 'Q........', '....Q....', '.......Q.', '.Q.......', '......Q..', '..Q......', '.....Q...'], ['........Q', '...Q.....', '.Q.......', '....Q....', '.......Q.', '.....Q...', 'Q........', '..Q......', '......Q..'], ['........Q', '...Q.....', '.Q.......', '......Q..', '..Q......', '.....Q...', '.......Q.', 'Q........', '....Q....'], ['........Q', '...Q.....', '.....Q...', '.......Q.', '.Q.......', '......Q..', 'Q........', '..Q......', '....Q....'], ['........Q', '...Q.....', '.....Q...', '.......Q.', '..Q......', 'Q........', '......Q..', '....Q....', '.Q.......'], ['........Q', '...Q.....', '.......Q.', 'Q........', '..Q......', '.....Q...', '.Q.......', '......Q..', '....Q....'], ['........Q', '....Q....', 'Q........', '...Q.....', '.....Q...', '.......Q.', '.Q.......', '......Q..', '..Q......'], ['........Q', '....Q....', 'Q........', '.......Q.', '...Q.....', '.Q.......', '......Q..', '..Q......', '.....Q...'], ['........Q', '....Q....', '..Q......', 'Q........', '.....Q...', '.......Q.', '.Q.......', '...Q.....', '......Q..'], ['........Q', '....Q....', '..Q......', 'Q........', '......Q..', '.Q.......', '.......Q.', '.....Q...', '...Q.....'], ['........Q', '....Q....', '..Q......', '.......Q.', '...Q.....', '......Q..', 'Q........', '.....Q...', '.Q.......'], ['........Q', '....Q....', '.......Q.', '...Q.....', 'Q........', '......Q..', '.Q.......', '.....Q...', '..Q......'], ['........Q', '.....Q...', '.Q.......', '......Q..', 'Q........', '..Q......', '....Q....', '.......Q.', '...Q.....'], ['........Q', '.....Q...', '..Q......', 'Q........', '.......Q.', '....Q....', '.Q.......', '...Q.....', '......Q..'], ['........Q', '.....Q...', '..Q......', '......Q..', '.Q.......', '.......Q.', '....Q....', 'Q........', '...Q.....'], ['........Q', '.....Q...', '...Q.....', '.Q.......', '.......Q.', '....Q....', '......Q..', 'Q........', '..Q......'], ['........Q', '.....Q...', '...Q.....', '......Q..', 'Q........', '.......Q.', '.Q.......', '....Q....', '..Q......'], ['........Q', '.....Q...', '.......Q.', '.Q.......', '...Q.....', 'Q........', '......Q..', '....Q....', '..Q......'], ['........Q', '......Q..', '.Q.......', '...Q.....', 'Q........', '.......Q.', '....Q....', '..Q......', '.....Q...'], ['........Q', '......Q..', '..Q......', '.......Q.', '.Q.......', '....Q....', 'Q........', '.....Q...', '...Q.....'], ['........Q', '......Q..', '...Q.....', '.Q.......', '.......Q.', '.....Q...', 'Q........', '..Q......', '....Q....']]


class Solution:

	def solveNQueens(self, n):

		def dfs(queens, xy_dif, xy_sum):
			p = len(queens)
			if p == n:
				res.append(queens)
				return
			for i in range(n):
				if i not in queens and p - i not in xy_dif and (p + i not in xy_sum):
					dfs(queens + [i], xy_dif + [p - i], xy_sum + [p + i])
		res = []
		dfs([], [], [])
		return [['.' * i + 'Q' + '.' * (n - i - 1) for i in sol] for sol in res]


class Solution:

	def solveNQueens(self, n):

		def dfs(cols, diag_45, diag_135, depth=0):
			row = len(cols)
			if row == n:
				result.append(cols)
				return
			for col in range(n):
				if col not in cols and row - col not in diag_45 and (row + col not in diag_135):
					dfs(cols + [col], diag_45 + [row - col], diag_135 + [row + col], depth + 1)
			else:
				pass
		result = []
		dfs([], [], [])
		return [['.' * i + 'Q' + '.' * (n - i - 1) for i in sol] for sol in result]


class Solution:

	def solveNQueens(self, n):
		result = []
		visits = [0, 0, 0]
		board = [['.' for j in range(n)] for i in range(n)]
		self.find(visits, n, 0, board, result)
		return result + [[row[::-1] for row in board] for board in result if n & 1 == 0 or (n & 1 == 1 and board[0][n >> 1] != 'Q')]

	def find(self, visits, n, k, board, result):
		if k >= n:
			result.append([''.join((x for x in row)) for row in board])
			return
		for j in range(n if k > 0 else n + 1 >> 1):
			if self.isInvalid(visits, k, j, n):
				continue
			self.toggleVisit(visits, k, j, n)
			board[k][j] = 'Q'
			self.find(visits, n, k + 1, board, result)
			self.toggleVisit(visits, k, j, n)
			board[k][j] = '.'

	def toggleVisit(self, visits, i, j, n):
		visits[0] ^= 1 << j
		visits[1] ^= 1 << i - j + n - 1
		visits[2] ^= 1 << i + j

	def isInvalid(self, visits, i, j, n):
		return visits[0] & 1 << j > 0 or visits[1] & 1 << i - j + n - 1 > 0 or visits[2] & 1 << i + j > 0


class Solution:

	def solveNQueens(self, n):

		def dfs(n, a, b, c, ans, d):
			if n == 0:
				ans = ans.append([i * '.' + 'Q' + (len(a) - i - 1) * '.' for i in d])
				return None
			for i in range(len(a)):
				if a[i] or b[n - 1 + i] or c[len(a) - 1 - i + n - 1]:
					continue
				(a[i], b[n - 1 + i], c[len(a) - 1 - i + n - 1]) = (True, True, True)
				d[n - 1] = i
				dfs(n - 1, a, b, c, ans, d)
				(a[i], b[n - 1 + i], c[len(a) - 1 - i + n - 1]) = (False, False, False)
			return None
		a = [False for i in range(n)]
		b = [False for i in range(n * 2 - 1)]
		c = [False for i in range(n * 2 - 1)]
		d = [0 for i in range(n)]
		ans = []
		dfs(n, a, b, c, ans, d)
		return ans


class Solution:

	def solveNQueens(self, n):
		row = [x for x in range(n)]
		table = []
		for i in range(n):
			table.append(row.copy())
		result = self.solve(table, 0)
		result_str = []
		for x in result:
			table_str = []
			for y in x:
				table_str.append('.' * y + 'Q' + '.' * (n - y - 1))
			result_str.append(table_str)
		return result_str

	def solve(self, table, n):
		if table[n] == []:
			return []
		elif n == len(table) - 1:
			table[n] = table[n][0]
			return [table]
		else:
			result = []
			for x in table[n]:
				table1 = [x if type(x) == int else x.copy() for x in table]
				table1[n] = x
				for row in range(n + 1, len(table)):
					if x in table1[row]:
						table1[row].remove(x)
					if x + row - n in table1[row]:
						table1[row].remove(x + row - n)
					if x - (row - n) in table1[row]:
						table1[row].remove(x - (row - n))
				result.extend(self.solve(table1, n + 1))
			return result


class Solution:

	def __init__(self):
		self.result = []
		self.visited = None

	def solveNQueens(self, n):
		self.visited = [0 for i in range(n)]
		self.__solve_n_queues(n, 0, [])
		return self.result

	@staticmethod
	def __not_diagonal(x, y, curr_answer):
		for (c_x, c_y) in enumerate(curr_answer):
			if abs(c_x - x) == abs(c_y - y):
				return False
		return True

	@staticmethod
	def visualize(curr_answer, n):
		answer = []
		for pos in curr_answer:
			answer.append('.' * pos + 'Q' + '.' * (n - pos - 1))
		return answer

	def __solve_n_queues(self, n, level, curr_answer):
		if level == n:
			self.result.append(Solution.visualize(curr_answer, n))
			return
		for i in range(n):
			if not self.visited[i] and Solution.__not_diagonal(level, i, curr_answer):
				self.visited[i] = 1
				curr_answer.append(i)
				self.__solve_n_queues(n, level + 1, curr_answer)
				curr_answer.pop()
				self.visited[i] = 0


class Solution:

	def solveNQueens(self, n):
		queens = []
		res = []

		def backtracking(n, k, queens):
			if k > n:
				return
			elif len(queens) == n and k < n:
				return
			elif len(queens) == n and k == n:
				temp = queens[:]
				res.append(temp)
			else:
				row = [0] * n
				temp_q = queens[:]
				for each in temp_q:
					(x, y) = (each[0], each[1])
					row[y] = 1
					if y + k - x < n:
						row[y + k - x] = 1
					if y - k + x >= 0:
						row[y - k + x] = 1
				for i in range(n):
					if row[i] == 0:
						temp_q.append((k, i))
						backtracking(n, k + 1, temp_q)
						temp_q.pop()
		backtracking(n, 0, queens)
		layout = []
		for q in res:
			temp = []
			for each in q:
				_row = '.' * each[1] + 'Q' + '.' * (n - each[1] - 1)
				temp.append(_row)
			layout.append(temp)
		return layout