The n-queens puzzle is the problem of placing n queens on a (n×n) chessboard such that no two queens can attack each other.
Given an integer n, find all distinct solutions to the n-queens puzzle. Each solution contains distinct board configurations of the n-queens’ placement, where the solutions are a permutation of [1,2,3..n] in increasing order, here the number in the ith place denotes that the ith-column queen is placed in the row with that number. For eg below figure represents a chessboard [3 1 4 2].
 
Example 1:
Input:
1
Output:
[1]
Explaination:
Only one queen can be placed 
in the single cell available.
Example 2:
Input:
4
Output:
[2 4 1 3 ] [3 1 4 2 ]
Explaination:
These are the 2 possible solutions.
 
Your Task:
You do not need to read input or print anything. Your task is to complete the function nQueen() which takes n as input parameter and returns a list containing all the possible chessboard configurations in sorted order. Return an empty list if no solution exists.
 
Expected Time Complexity: O(n!)
Expected Auxiliary Space: O(n^{2}) 
 
Constraints:
1 ≤ n ≤ 10

Difficulty: MEDIUM_HARD
Tags: Complete search
Skill types: Complete search
Expected Time Complexity: O(n!)
Expected Auxiliary Space: O(n^{2})

Starter code:
#User function Template for python3

class Solution:
    def nQueen(self, n):
        # code here

Solutions:
class Solution:

	def nQueen(self, n):
		board = [[0 for _ in range(n)] for _ in range(n)]
		ans = []
		self.solveQueen(0, n, board, ans)
		return ans

	def solveQueen(self, row, n, board, ans):
		if row == n:
			temp = []
			for r in range(n):
				for c in range(n):
					if board[r][c] == 1:
						temp.append(c + 1)
			ans.append(temp)
			return
		for col in range(n):
			if self.isSafe(row, col, board, n):
				board[row][col] = 1
				self.solveQueen(row + 1, n, board, ans)
				board[row][col] = 0

	def isSafe(self, row, col, board, n):
		i = 0
		while i < row:
			if board[i][col]:
				return False
			i += 1
		i = row
		j = col
		while i >= 0 and j >= 0:
			if board[i][j]:
				return False
			j -= 1
			i -= 1
		i = row
		j = col
		while i >= 0 and j < n:
			if board[i][j]:
				return False
			j += 1
			i -= 1
		return True


from collections import defaultdict

class Solution:

	def placeQueen(self, row_check, updiag_check, lowdiag_check, n, queenid, seq):
		if queenid == n:
			self.res.append(seq)
			return
		for i in range(n):
			if row_check[i] != 1 and updiag_check[n - 1 + i - queenid] != 1 and (lowdiag_check[i + queenid] != 1):
				row_check[i] = 1
				updiag_check[n - 1 + i - queenid] = 1
				lowdiag_check[i + queenid] = 1
				self.placeQueen(row_check, updiag_check, lowdiag_check, n, queenid + 1, seq + [i + 1])
				row_check[i] = 0
				updiag_check[n - 1 + i - queenid] = 0
				lowdiag_check[i + queenid] = 0

	def nQueen(self, n):
		row_check = defaultdict(int)
		updiag_check = defaultdict(int)
		lowdiag_check = defaultdict(int)
		self.res = []
		self.placeQueen(row_check, updiag_check, lowdiag_check, n, 0, [])
		return self.res


class Solution:

	def ispossible(self, board, n, row, col):
		for i in range(col):
			if board[row][i] == 1:
				return False
		(i, j) = (row - 1, col - 1)
		while i >= 0 and j >= 0:
			if board[i][j] == 1:
				return False
			i -= 1
			j -= 1
		(i, j) = (row + 1, col - 1)
		while i < n and j >= 0:
			if board[i][j] == 1:
				return False
			i += 1
			j -= 1
		return True

	def placeQueen(self, board, n, queenid, seq):
		if queenid == n:
			self.res.append(seq)
			return
		for i in range(n):
			if self.ispossible(board, n, i, queenid):
				board[i][queenid] = 1
				self.placeQueen(board, n, queenid + 1, seq + [i + 1])
				board[i][queenid] = 0

	def nQueen(self, n):
		board = [[0 for _ in range(n)] for _ in range(n)]
		self.res = []
		self.placeQueen(board, n, 0, [])
		return self.res


class Solution:

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

	def solve(self, board, row, n, ans, temp_ans):
		if row == n:
			ans.append(temp_ans.copy())
			return
		for col in range(n):
			if self.is_safe(board, row, col, n):
				board[row][col] = 'Q'
				temp_ans.append(col + 1)
				self.solve(board, row + 1, n, ans, temp_ans)
				board[row][col] = '.'
				temp_ans.pop()

	def nQueen(self, n):
		board_row = ['.'] * n
		board = []
		for i in range(n):
			board.append(board_row.copy())
		ans = []
		self.solve(board, 0, n, ans, [])
		return ans


class Solution:

	def nQueen(self, n):
		final = []

		def isSafe(temp):
			if len(temp) == 1:
				return True
			m = len(temp) - 1
			last = temp.pop()
			if last in temp:
				return False
			for i in range(m):
				if temp[i] == last + (m - i):
					return False
				if temp[i] == last - (m - i):
					return False
			temp.append(last)
			return True

		def queen(ans):
			if len(ans) == n:
				ans = [i + 1 for i in ans]
				final.append(ans)
			for i in range(n):
				ans.append(i)
				temp = ans.copy()
				if isSafe(temp):
					if queen(temp):
						return True
				ans.pop()
			return False
		queen([])
		return sorted(final)


class Solution:

	def isValid(self, i, j, grid, n):
		(r, c) = (i, j)
		while j >= 0:
			if grid[i][j] == 1:
				return False
			j -= 1
		(i, j) = (r, c)
		while i >= 0 and j >= 0:
			if grid[i][j] == 1:
				return False
			i -= 1
			j -= 1
		(i, j) = (r, c)
		while i < n and j >= 0:
			if grid[i][j] == 1:
				return False
			i += 1
			j -= 1
		return True

	def solve(self, col, res, curr, grid, n):
		if col == n:
			res.append(curr[:])
			return
		for i in range(n):
			if self.isValid(i, col, grid, n):
				grid[i][col] = 1
				curr.append(i + 1)
				self.solve(col + 1, res, curr, grid, n)
				grid[i][col] = 0
				curr.pop()

	def nQueen(self, n):
		grid = [[0 for j in range(n)] for i in range(n)]
		res = []
		curr = []
		col = 0
		self.solve(col, res, curr, grid, n)
		return res


class Solution:

	def nQueen(self, n):
		arr = [[0] * n for i in range(n)]
		self.res = []
		self.check(arr, 0, n)
		return self.res

	def check(self, arr, s, n):
		if s == n:
			f = []
			for i in range(n):
				for j in range(n):
					if arr[i][j] == 1:
						f.append(j + 1)
			self.res.append(f)
			return
		for i in range(n):
			arr[s][i] = 1
			if not self.valid(arr, s, i, n):
				arr[s][i] = 0
				continue
			self.check(arr, s + 1, n)
			arr[s][i] = 0

	def valid(self, arr, x, y, n):
		d = [[-1, -1], [-1, 0], [0, -1], [0, 1], [-1, 1]]
		for i in d:
			r = x
			c = y
			while r + i[0] > -1 and -1 < c + i[1] < n:
				r = r + i[0]
				c = c + i[1]
				if arr[r][c] == 1:
					return False
		return True


class Solution:

	def getAns(self, col, ans, res, n, LR, ULD, LLD):
		if col == n:
			res.append(ans[:])
			return
		for row in range(n):
			if LR[row] == 0 and LLD[row + col] == 0 and (ULD[n - 1 + col - row] == 0):
				ans.append(row + 1)
				LR[row] = 1
				LLD[row + col] = 1
				ULD[n - 1 + col - row] = 1
				self.getAns(col + 1, ans, res, n, LR, ULD, LLD)
				ans.pop()
				LR[row] = 0
				LLD[row + col] = 0
				ULD[n - 1 + col - row] = 0

	def nQueen(self, n):
		LR = [0] * n
		LLD = [0] * (2 * n - 1)
		ULD = [0] * (2 * n - 1)
		res = []
		self.getAns(0, [], res, n, LR, ULD, LLD)
		return res


class Solution:

	def isSafe(self, row, col, temp, n):
		for i in range(col, -1, -1):
			if temp[row][i] == 1:
				return False
		x = row - 1
		y = col - 1
		while x >= 0 and y >= 0:
			if temp[x][y] == 1:
				return False
			x -= 1
			y -= 1
		x = row + 1
		y = col - 1
		while x < n and y >= 0:
			if temp[x][y] == 1:
				return False
			x += 1
			y -= 1
		return True

	def helper(self, ans, temp, col, n):
		if col == n:
			board = []
			for i in range(n):
				for j in range(n):
					if temp[j][i] == 1:
						board.append(j + 1)
			ans.append(board)
			return
		for row in range(n):
			if self.isSafe(row, col, temp, n):
				temp[row][col] = 1
				self.helper(ans, temp, col + 1, n)
				temp[row][col] = 0

	def nQueen(self, n):
		ans = []
		temp = []
		for i in range(n):
			row = []
			for j in range(n):
				row.append(0)
			temp.append(row)
		self.helper(ans, temp, 0, n)
		return ans


def canPlace(mat, i, j, n):
	for row in range(0, i):
		if mat[row][j] == 1:
			return False
	row = i
	col = j
	while row >= 0 and col >= 0:
		if mat[row][col] == 1:
			return False
		row -= 1
		col -= 1
	row = i
	col = j
	while row >= 0 and col < n:
		if mat[row][col] == 1:
			return False
		row -= 1
		col += 1
	return True

def findPerm(mat, i, n, cur, ans):
	if i == n:
		ans.append([x for x in cur])
		return
	for j in range(n):
		if canPlace(mat, i, j, n):
			mat[i][j] = 1
			cur[i] = j + 1
			findPerm(mat, i + 1, n, cur, ans)
			cur[i] = 0
			mat[i][j] = 0

class Solution:

	def nQueen(self, n):
		mat = [[0 for _ in range(n)] for i in range(n)]
		ans = []
		findPerm(mat, 0, n, [0] * n, ans)
		return ans


class Solution:

	def isSafe(self, board, row, col, n):
		for i in range(col):
			if board[row][i] == 1:
				return False
		for (i, j) in zip(range(row, -1, -1), range(col, -1, -1)):
			if board[i][j] == 1:
				return False
		for (i, j) in zip(range(row, n, 1), range(col, -1, -1)):
			if board[i][j] == 1:
				return False
		return True

	def solveQueens(self, board, col, n, res):
		if col == n:
			temp = []
			for c in range(n):
				for r in range(n):
					if board[r][c] == 1:
						temp.append(r + 1)
			res.append(temp)
			return
		for i in range(n):
			if self.isSafe(board, i, col, n):
				board[i][col] = 1
				self.solveQueens(board, col + 1, n, res)
				board[i][col] = 0

	def nQueen(self, n):
		board = [[0 for _ in range(n)] for _ in range(n)]
		res = []
		self.solveQueens(board, 0, n, res)
		return res


class Solution:

	def place(self, r, c):
		for prev in range(c):
			if self.row[prev] == r or abs(self.row[prev] - r) == abs(prev - c):
				return False
		return True

	def bt(self, c, n):
		if n == 2 or n == 3:
			return
		if c == n:
			v = []
			for i in range(n):
				v.append(self.row[i] + 1)
			self.result.append(v)
			self.k += 1
		for i in range(n):
			if self.place(i, c):
				self.row[c] = i
				self.bt(c + 1, n)

	def nQueen(self, n):
		self.result = []
		self.row = [0] * 10
		self.k = 0
		self.bt(0, n)
		return self.result


class Solution:

	def addans(self, board, ans):
		temp = []
		for sub in board:
			for j in range(len(sub)):
				if sub[j] == 'Q':
					temp.append(j + 1)
					break
		ans.append(temp)

	def solve(self, col, board, ans, lrow, lowerd, upperd, n):
		if col == n:
			self.addans(board, ans)
			return
		for row in range(n):
			if lrow[row] == 0 and upperd[n - 1 + col - row] == 0 and (lowerd[row + col] == 0):
				board[row][col] = 'Q'
				lrow[row] = 1
				upperd[n - 1 + col - row] = 1
				lowerd[row + col] = 1
				self.solve(col + 1, board, ans, lrow, lowerd, upperd, n)
				board[row][col] = 0
				lrow[row] = 0
				upperd[n - 1 + col - row] = 0
				lowerd[row + col] = 0

	def nQueen(self, n):
		board = [[0 for i in range(n)] for j in range(n)]
		ans = []
		lrow = [0] * n
		upperd = [0] * (2 * n - 1)
		lowerd = [0] * (2 * n - 1)
		self.solve(0, board, ans, lrow, lowerd, upperd, n)
		ans.sort()
		return ans


class Solution:

	def nQueen(self, n):
		rows = set()
		cols = set()
		diags1 = set()
		diags2 = set()
		solutions = []
		self.solve(n, rows, cols, diags1, diags2, [], solutions)
		return solutions

	def solve(self, n, rows, cols, diags1, diags2, queens, solutions):
		if len(queens) == n:
			solutions.append(list(queens))
			return
		row = len(queens)
		for col in range(n):
			diag1 = row + col
			diag2 = row - col
			if row not in rows and col not in cols and (diag1 not in diags1) and (diag2 not in diags2):
				rows.add(row)
				cols.add(col)
				diags1.add(diag1)
				diags2.add(diag2)
				queens.append(col + 1)
				self.solve(n, rows, cols, diags1, diags2, queens, solutions)
				queens.pop()
				diags2.remove(diag2)
				diags1.remove(diag1)
				cols.remove(col)
				rows.remove(row)


class Solution:
	ans = []
	arr = []

	def issafe(self, n, visited, i, j):
		ic = i
		jc = j
		while ic >= 0:
			if visited[ic][jc] == 1:
				return 0
			ic -= 1
		ic = i
		jc = j
		while jc >= 0 and ic >= 0:
			if visited[ic][jc] == 1:
				return 0
			ic -= 1
			jc -= 1
		ic = i
		jc = j
		while ic >= 0 and jc < n:
			if visited[ic][jc] == 1:
				return 0
			ic -= 1
			jc += 1
		return 1

	def gen(self, n, visited, i, j):
		if i == n:
			g = self.arr.copy()
			self.ans.append(g)
			return
		for k in range(n):
			if self.issafe(n, visited, i, k):
				visited[i][k] = 1
				self.arr.append(k + 1)
				self.gen(n, visited, i + 1, k)
				self.arr.pop()
				visited[i][k] = 0

	def nQueen(self, n):
		self.ans = []
		self.arr = []
		visited = []
		for i in range(n):
			a = []
			for j in range(n):
				a.append(0)
			visited.append(a)
		self.gen(n, visited, 0, 0)
		return self.ans


class Solution:

	def nQueen(self, n):
		result = []
		board = [['.' for j in range(n)] for i in range(n)]
		left = [False] * n
		ld = [False] * (2 * n - 1)
		ud = [False] * (2 * n - 1)
		self.solve(0, board, left, ud, ld, result, n)
		result.sort()
		return result

	def solve(self, col, board, left, ud, ld, result, n):
		if col == n:
			temp = []
			for i in range(n):
				for j in range(n):
					if board[i][j] == 'Q':
						temp.append(j + 1)
			result.append(temp)
			return
		for row in range(n):
			if board[row][col] == '.' and (not left[row]) and (not ld[row + col]) and (not ud[n - 1 + col - row]):
				board[row][col] = 'Q'
				left[row] = True
				ld[row + col] = True
				ud[n - 1 + col - row] = True
				self.solve(col + 1, board, left, ud, ld, result, n)
				left[row] = False
				ld[row + col] = False
				ud[n - 1 + col - row] = False
				board[row][col] = '.'


import copy

def solve(col, board, leftRow, leftDiagonal, rightDiagonal, ans, n, temp):
	if col == n:
		res = copy.deepcopy(temp)
		ans.append(res)
		return
	for row in range(n):
		if leftRow[row] == False and leftDiagonal[row + col] == False and (rightDiagonal[n - 1 + col - row] == False):
			board[row][col] = 'Q'
			temp.append(row + 1)
			leftRow[row] = True
			leftDiagonal[row + col] = True
			rightDiagonal[n - 1 + col - row] = True
			solve(col + 1, board, leftRow, leftDiagonal, rightDiagonal, ans, n, temp)
			board[row][col] = '.'
			temp.pop()
			leftRow[row] = False
			leftDiagonal[row + col] = False
			rightDiagonal[n - 1 + col - row] = False

class Solution:

	def nQueen(self, n):
		board = [['.' for _ in range(n)] for _ in range(n)]
		leftRow = [False for _ in range(n)]
		leftDiagonal = [False for _ in range(2 * n - 1)]
		rightDiagonal = [False for _ in range(2 * n - 1)]
		ans = []
		temp = []
		solve(0, board, leftRow, leftDiagonal, rightDiagonal, ans, n, temp)
		ans.sort()
		return ans


class Solution:

	def nQueen(self, n):
		ans = []
		board = [0] * n
		col_attack = [False] * n
		diag_up_attack = [False] * (2 * n - 1)
		diag_down_attack = [False] * (2 * n - 1)
		self.solve_board(0, n, board, ans, col_attack, diag_up_attack, diag_down_attack)
		return ans

	def solve_board(self, col, n, board, ans, col_attack, diag_up_attack, diag_down_attack):
		if col == n:
			ans.append([row + 1 for row in board])
			return
		for row in range(n):
			if not col_attack[row] and (not diag_up_attack[col - row + n - 1]) and (not diag_down_attack[col + row]):
				board[col] = row
				col_attack[row] = diag_up_attack[col - row + n - 1] = diag_down_attack[col + row] = True
				self.solve_board(col + 1, n, board, ans, col_attack, diag_up_attack, diag_down_attack)
				col_attack[row] = diag_up_attack[col - row + n - 1] = diag_down_attack[col + row] = False


class Solution:

	def nQueen(self, n):
		board = [[None] * n for i in range(n)]
		ans = []
		self.solve_board(board, ans, 0, n, [])
		return ans

	def solve_board(self, board, ans, from_col, n, this_ans):
		if from_col + 1 > n:
			ans.append(this_ans[:])
			return
		for i in range(n):
			if board[i][from_col] == None:
				new_ans = this_ans + [i + 1]
				new_board = self.fil_board(board, i, from_col, n)
				self.solve_board(new_board, ans, from_col + 1, n, new_ans)
		return

	def fil_board(self, old_board, at_row, at_col, n):
		new_board = [row[:] for row in old_board]
		(diag_up, diag_down) = (at_row, at_row)
		for col in range(at_col + 1, n):
			diag_up -= 1
			diag_down += 1
			if diag_up >= 0:
				new_board[diag_up][col] = 0
			if diag_down < n:
				new_board[diag_down][col] = 0
			new_board[at_row][col] = 0
		return new_board


class Solution:

	def nQueen(self, n):

		def backtrack(row, diagonals, anti_diagonals, cols, state):
			if row == n:
				ans.append(state)
				return
			for col in range(n):
				curr_diagonal = row - col
				curr_anti_diagonal = row + col
				if col in cols or curr_diagonal in diagonals or curr_anti_diagonal in anti_diagonals:
					continue
				cols.add(col)
				diagonals.add(curr_diagonal)
				anti_diagonals.add(curr_anti_diagonal)
				backtrack(row + 1, diagonals, anti_diagonals, cols, state + [col + 1])
				cols.remove(col)
				diagonals.remove(curr_diagonal)
				anti_diagonals.remove(curr_anti_diagonal)
		ans = []
		backtrack(0, set(), set(), set(), [])
		return ans


class Solution:

	def nQueen(self, n):
		col = set()
		posDiag = set()
		negDiag = set()
		res = []
		board = [[-1] * n for i in range(n)]

		def backtrack(r):
			if r == n:
				copy = [0] * n
				for row in range(n):
					for c in range(n):
						if board[row][c] != -1:
							copy[row] = c + 1
				res.append(copy)
				return
			for c in range(n):
				if c in col or r + c in posDiag or r - c in negDiag:
					continue
				col.add(c)
				posDiag.add(r + c)
				negDiag.add(r - c)
				board[r][c] = c
				backtrack(r + 1)
				col.remove(c)
				posDiag.remove(r + c)
				negDiag.remove(r - c)
				board[r][c] = -1
		backtrack(0)
		return res


class Solution:

	def is_safe(self, row, col, board, n):
		(x, y) = (row - 1, col - 1)
		while x >= 0 and y >= 0:
			if board[x][y] == 1:
				return False
			x -= 1
			y -= 1
		y = col - 1
		while y >= 0:
			if board[row][y] == 1:
				return False
			y -= 1
		(x, y) = (row + 1, col - 1)
		while x < n and y >= 0:
			if board[x][y] == 1:
				return False
			x += 1
			y -= 1
		return True

	def solve(self, col, n, board, path, ans):
		if col == n:
			temp = [i + 1 for r in board for (i, c) in enumerate(r) if c == 1]
			ans.append(temp)
			return
		for row in range(n):
			if self.is_safe(row, col, board, n):
				board[row][col] = 1
				path.append(col)
				self.solve(col + 1, n, board, path, ans)
				board[row][col] = 0
				path.pop()

	def nQueen(self, n):
		board = [[0 for _ in range(n)] for _ in range(n)]
		ans = []
		path = []
		self.solve(0, n, board, path, ans)
		ans.sort()
		return ans


class Solution:

	def nQueen(self, n):

		def isValid(output, i, depth):
			for out_depth in range(len(output)):
				out_i = output[out_depth]
				if i == out_i or i == out_i - (depth - out_depth) or i == out_i + (depth - out_depth):
					return False
			return True

		def findPosition(index, output, paths):
			if len(output) == n:
				paths.append(list(map(lambda x: x + 1, output)))
			for i in range(0, n):
				if isValid(output, i, index):
					output.append(i)
					findPosition(index + 1, output, paths)
					output.pop()
		paths = []
		findPosition(0, [], paths)
		return paths


class Solution:

	def nQueen(self, n):
		ans = []

		def queen(board, r):
			if r == n:
				ans.append(board[:])
				return
			for c in range(1, n + 1):
				board[r] = c
				for p in range(r):
					if board[p] == c or abs(board[p] - c) == abs(r - p):
						break
				else:
					queen(board, r + 1)
				board[r] = None
		queen([None] * n, 0)
		return ans


class Solution:

	def nQueen(self, n):

		def issafe(r, c):
			n = len(board)
			for i in range(n):
				if board[i][c] == 'Q':
					return False
				if r - i >= 0 and c - i >= 0 and (board[r - i][c - i] == 'Q'):
					return False
				if r - i >= 0 and c + i < n and (board[r - i][c + i] == 'Q'):
					return False
			return True
		board = [['.' for _ in range(n)] for _ in range(n)]
		res = []

		def f(r):
			if r >= n:
				ans = []
				for i in range(n):
					for j in range(n):
						if board[i][j] == 'Q':
							ans.append(j + 1)
				res.append(ans)
				return
			for c in range(n):
				if issafe(r, c):
					board[r][c] = 'Q'
					f(r + 1)
					board[r][c] = '.'
		f(0)
		return res


class Solution:

	def nQueen(self, n):

		def isSafe(row, col, board, n, bottomDia, upperDia, horizontalRow):
			if bottomDia[row + col] == 1 or upperDia[n - 1 + col - row] == 1 or horizontalRow[row] == 1:
				return 0
			return 1

		def solve(col, board, ds, ans, n, bottomDia, upperDia, horizontalRow):
			if col == n:
				ans.append(ds.copy())
				ds = []
				return
			for row in range(n):
				if isSafe(row, col, board, n, bottomDia, upperDia, horizontalRow):
					board[row][col] = 'Q'
					ds.append(row + 1)
					bottomDia[row + col] = 1
					upperDia[n - 1 + col - row] = 1
					horizontalRow[row] = 1
					solve(col + 1, board, ds, ans, n, bottomDia, upperDia, horizontalRow)
					board[row][col] = '.'
					ds.pop()
					bottomDia[row + col] = 0
					upperDia[n - 1 + col - row] = 0
					horizontalRow[row] = 0
		ans = []
		board = []
		N = 2 * n - 1
		bottomDia = [0] * N
		upperDia = [0] * N
		horizontalRow = [0] * N
		ds = []
		for i in range(n):
			s = ['.'] * n
			board.append(s)
		solve(0, board, ds, ans, n, bottomDia, upperDia, horizontalRow)
		return ans


class Solution:

	def __init__(self):
		self.answer = []

	def nQueen(self, n):
		for i in range(n):
			self.helper(0, i, n, n, [], n, n)
		return self.answer

	def helper(self, i, j, ROW, COL, cols, n, q):
		if q == 0:
			ans = [w + 1 for w in cols]
			if not ans in self.answer:
				self.answer.append(ans)
			return
		if not 0 <= i < ROW or not 0 <= j < COL or (not self.check(cols, i, j, n, n - q)):
			return
		cols.append(j)
		for k in range(COL):
			self.helper(i + 1, k, ROW, COL, cols, n, q - 1)
		cols.pop()

	def check(self, cols, i, j, n, p):
		for k in range(p):
			if j == cols[k] or i - j == k - cols[k] or i + j == k + cols[k]:
				return False
		return True


class Solution:

	def __init__(self):
		self.ans = []

	def nQueen(self, n):
		board = [['0'] * n for i in range(n)]
		self.queens(board, row=0)
		return self.ans

	def issafe(self, board, row, col):
		for i in range(row):
			if board[i][col] == '1':
				return False
		max_left = min(row, col)
		for i in range(1, max_left + 1):
			if board[row - i][col - i] == '1':
				return False
		max_right = min(row, len(board) - col - 1)
		for i in range(1, max_right + 1):
			if board[row - i][col + i] == '1':
				return False
		return True

	def queens(self, board, row):
		if row == len(board):
			l = []
			for i in board:
				l.append(i.index('1') + 1)
			self.ans.append(l)
		for col in range(len(board)):
			if self.issafe(board, row, col):
				board[row][col] = '1'
				self.queens(board, row + 1)
				board[row][col] = '0'


class Solution:

	def nQueen(self, n):

		def safe(i, j, arr, n):
			k = i
			m = j
			while k >= 0:
				if arr[k][j] == 'T':
					return False
				k = k - 1
			k = i
			m = j
			while k >= 0 and m >= 0:
				if arr[k][m] == 'T':
					return False
				k = k - 1
				m = m - 1
			k = i
			m = j
			while k >= 0 and m < n:
				if arr[k][m] == 'T':
					return False
				k = k - 1
				m = m + 1
			return True
		arr = [['F' for i in range(n)] for j in range(n)]
		arr1 = []

		def function(arr, n, i, arr1):
			if i >= n:
				arr2 = []
				for i in range(n):
					for j in range(n):
						if arr[i][j] == 'T':
							arr2.append(j + 1)
				arr1.append(arr2)
			for j in range(n):
				if safe(i, j, arr, n) is True:
					arr[i][j] = 'T'
					function(arr, n, i + 1, arr1)
					arr[i][j] = 'F'
			return
		function(arr, n, 0, arr1)
		return arr1


def queen_path(board: [[]], n, row, result_arr: [[]]):
	if row == n:
		path = []
		for i in range(0, n):
			for j in range(0, n):
				if board[i][j] == 1:
					path.append(j + 1)
		result_arr.append(path)
		return
	for i in range(0, n):
		if is_safe(board, row, i, n):
			board[row][i] = 1
			queen_path(board, n, row + 1, result_arr)
			board[row][i] = 0

def is_safe(board: [[]], row, col, n):
	for i in range(0, row):
		if board[i][col] == 1:
			return False
	cur_row = row - 1
	cur_col = col - 1
	while cur_col >= 0 and cur_row >= 0:
		if board[cur_row][cur_col] == 1:
			return False
		cur_row = cur_row - 1
		cur_col = cur_col - 1
	cur_row = row - 1
	cur_col = col + 1
	while cur_row >= 0 and cur_col < n:
		if board[cur_row][cur_col] == 1:
			return False
		cur_row = cur_row - 1
		cur_col = cur_col + 1
	return True

def queen_path_main(n):
	board_arr = [[0] * n for i in range(n)]
	result_arr = []
	queen_path(board_arr, n, 0, result_arr)
	return result_arr

class Solution:

	def nQueen(self, n):
		return queen_path_main(n)


class Solution:

	def nQueen(self, n):
		board = [[0 for j in range(n + 1)] for i in range(n + 1)]
		ans = []
		s = []

		def check(row, col):
			for i in range(col):
				if board[row][i] == 1:
					return False
			for (i, j) in zip(range(row, -1, -1), range(col, -1, -1)):
				if board[i][j] == 1:
					return False
			for (i, j) in zip(range(row, n + 1, 1), range(col, -1, -1)):
				if board[i][j] == 1:
					return False
			return True

		def solve(col):
			if col >= n + 1:
				ans.append(list(s))
			for row in range(1, n + 1):
				if check(row, col) == True:
					board[row][col] = 1
					s.append(row)
					solve(col + 1)
					s.remove(row)
					board[row][col] = 0
		solve(1)
		return ans


class Solution:

	def nQueen(self, n):

		def safe(row, col, board, n):
			rCopy = row
			cCopy = col
			while col >= 0:
				if board[row][col] == 'Q':
					return False
				col -= 1
			row = rCopy
			col = cCopy
			while row >= 0 and col >= 0:
				if board[row][col] == 'Q':
					return False
				row -= 1
				col -= 1
			row = rCopy
			col = cCopy
			while row < n and col >= 0:
				if board[row][col] == 'Q':
					return False
				row += 1
				col -= 1
			return True

		def solve(col, board, ans, n, curr):
			if col == n:
				ans.append(curr[:])
				return
			for row in range(n):
				if safe(row, col, board, n):
					curr.append(row + 1)
					board[row] = board[row][:col] + 'Q' + board[row][col + 1:]
					solve(col + 1, board, ans, n, curr)
					curr.pop()
					board[row] = board[row][:col] + '.' + board[row][col + 1:]
		ans = []
		board = ['.' * n for i in range(n)]
		solve(0, board, ans, n, [])
		return ans


class Solution:

	def nQueen(self, n):
		board = [[0 for i in range(n)] for i in range(n)]
		leftrow = [0 for i in range(n)]
		lowerdiag = [0 for i in range(2 * n - 1)]
		upperdiag = [0 for i in range(2 * n - 1)]
		res = []

		def isvalid(row, col, board):
			(i, j) = (row, col)
			while j >= 0:
				if board[i][j] == 1:
					return False
				j -= 1
			(i, j) = (row, col)
			while i >= 0 and j >= 0:
				if board[i][j] == 1:
					return False
				i -= 1
				j -= 1
			(i, j) = (row, col)
			while i < n and j < n:
				if board[i][j] == 1:
					return False
				i += 1
				j -= 1
			return True

		def rec(col, board, lowerdiag, leftrow, upperdiag, res):
			if col == n:
				ds = []
				for i in range(n):
					for j in range(n):
						if board[i][j] == 1:
							ds.append(j + 1)
				res.append(list(ds))
				return
			for row in range(n):
				if isvalid(row, col, board):
					board[row][col] = 1
					rec(col + 1, board, lowerdiag, leftrow, upperdiag, res)
					board[row][col] = 0
			return sorted(res)
		return rec(0, board, lowerdiag, leftrow, upperdiag, res)


class Solution:

	def solve(self, board, n, col, ans, hashrow, lowertriangle, uppertriangle):
		if col == n:
			k = []
			for i in board:
				for j in range(0, len(i)):
					if i[j] == 'Q':
						k.append(j + 1)
			ans.append(list(k))
			return
		for row in range(0, n):
			if hashrow[row] == 0 and lowertriangle[row + col] == 0 and (uppertriangle[n - 1 + col - row] == 0):
				hashrow[row] = 1
				lowertriangle[row + col] = 1
				uppertriangle[n - 1 + col - row] = 1
				board[row] = board[row][:col] + 'Q' + board[row][col + 1:]
				self.solve(board, n, col + 1, ans, hashrow, lowertriangle, uppertriangle)
				board[row] = board[row][:col] + '.' + board[row][col + 1:]
				hashrow[row] = 0
				lowertriangle[row + col] = 0
				uppertriangle[n - 1 + col - row] = 0

	def nQueen(self, n):
		board = ['.' * n for _ in range(n)]
		hashrow = [0] * n
		lowertriangle = [0] * (2 * n - 1)
		uppertriangle = [0] * (2 * n - 1)
		ans = []
		self.solve(board, n, 0, ans, hashrow, lowertriangle, uppertriangle)
		res = []
		ans.sort()
		return ans


class Solution:

	def nQueen(self, n):
		sol = []
		res = []
		cols = [False] * n
		diag1 = [False] * (2 * n - 1)
		diag2 = [False] * (2 * n - 1)

		def check(res, row):
			if row == n:
				sol.append(list(res))
				return
			for col in range(n):
				if not cols[col] and (not diag1[row + col]) and (not diag2[row - col + n - 1]):
					res.append(col)
					cols[col] = True
					diag1[row + col] = True
					diag2[row - col + n - 1] = True
					check(res, row + 1)
					res.pop()
					cols[col] = False
					diag1[row + col] = False
					diag2[row - col + n - 1] = False
		check(res, 0)
		sol = [[i + 1 for i in row] for row in sol]
		return sol


def helper(col, board, n, ans, leftCheck, upperDiagonal, lowerDiagonal):
	if col == n:
		temp = []
		for i in range(n):
			for j in range(n):
				if board[i][j] == 'Q':
					temp.append(j + 1)
		ans.append(temp)
	for row in range(n):
		if leftCheck[row] == 0 and lowerDiagonal[row + col] == 0 and (upperDiagonal[n - 1 + col - row] == 0):
			board[row][col] = 'Q'
			leftCheck[row] = 1
			lowerDiagonal[row + col] = 1
			upperDiagonal[n - 1 + col - row] = 1
			helper(col + 1, board, n, ans, leftCheck, upperDiagonal, lowerDiagonal)
			board[row][col] = '.'
			leftCheck[row] = 0
			lowerDiagonal[row + col] = 0
			upperDiagonal[n - 1 + col - row] = 0

class Solution:

	def nQueen(self, n):
		ans = []
		board = [['.'] * n for i in range(n)]
		leftCheck = [0] * n
		upperDiagonal = [0] * (n * 2 - 1)
		lowerDiagonal = [0] * (n * 2 - 1)
		helper(0, board, n, ans, leftCheck, upperDiagonal, lowerDiagonal)
		ans.sort()
		return ans


class Solution:

	def nQueen(self, n):

		def backtrack(r):
			if r == n:
				result.append(output[:])
				return
			for c in range(n):
				if c in col or r + c in diagonal or r - c in antidiagonal:
					continue
				col.add(c)
				diagonal.add(r + c)
				antidiagonal.add(r - c)
				output.append(c + 1)
				backtrack(r + 1)
				col.remove(c)
				diagonal.remove(r + c)
				antidiagonal.remove(r - c)
				output.pop()
		col = set()
		diagonal = set()
		antidiagonal = set()
		output = []
		result = []
		backtrack(0)
		return result


class Solution:

	def nQueen(self, n):

		def solve(col, board, n, l, ans):

			def is_safe(row, col, n):
				(r1, c1) = (row, col)
				while r1 >= 0 and c1 >= 0:
					if board[r1][c1] == 'Q':
						return False
					r1 -= 1
					c1 -= 1
				(r, c) = (row, col)
				while c >= 0:
					if board[r][c] == 'Q':
						return False
					c -= 1
				(r, c) = (row, col)
				while r < n and c >= 0:
					if board[r][c] == 'Q':
						return False
					r += 1
					c -= 1
				return True
			if col == n:
				ans.append(l.copy())
				return
			for row in range(n):
				if is_safe(row, col, n):
					board[row][col] = 'Q'
					l.append(row + 1)
					solve(col + 1, board, n, l, ans)
					board[row][col] = '.'
					l.pop()
		board = [['.'] * n for _ in range(n)]
		ans = []
		solve(0, board, n, [], ans)
		return ans


class Solution:

	def nQueen(self, n):
		ans = []

		def arrangeboard(board):
			newBoard = []
			for i in range(len(board)):
				s = ''
				for j in range(len(board)):
					s += board[i][j]
				newBoard.append(s)
			return newBoard

		def solve(row, cols, diagonals, anti_diagonals, board):
			if row == len(board):
				ans.append(arrangeboard(board))
				return
			for col in range(len(board)):
				cur_diag = row - col
				cur_anti_diag = row + col
				if col in cols or cur_diag in diagonals or cur_anti_diag in anti_diagonals:
					continue
				cols.add(col)
				diagonals.add(cur_diag)
				anti_diagonals.add(cur_anti_diag)
				board[row][col] = 'Q'
				solve(row + 1, cols, diagonals, anti_diagonals, board)
				cols.remove(col)
				diagonals.remove(cur_diag)
				anti_diagonals.remove(cur_anti_diag)
				board[row][col] = '.'
		initialBoard = [['.' for i in range(n)] for j in range(n)]
		solve(0, set(), set(), set(), initialBoard)
		m = []
		for i in ans:
			res = []
			for j in i:
				for k in range(len(j)):
					if j[k] == 'Q':
						res.append(k + 1)
			m.append(res)
		return m


class Solution:

	def nQueen(self, n):

		def dfs(cols, neg, pos):
			p = len(cols)
			if p == n:
				result.append(list(map(lambda x: x + 1, cols)))
				return
			for i in range(n):
				if i not in cols and p - i not in neg and (p + i not in pos):
					dfs(cols + [i], neg + [p - i], pos + [p + i])
		result = []
		dfs([], [], [])
		return result


class Solution:

	def nQueen(self, n):
		board = [['.' for i in range(n)] for j in range(n)]
		res = []

		def check(row, col):
			r = row
			c = col
			while r >= 0 and c >= 0:
				if board[r][c] == 'Q':
					return False
				r -= 1
				c -= 1
			r = row
			c = col
			while r < n and c >= 0:
				if board[r][c] == 'Q':
					return False
				c -= 1
				r += 1
			r = row
			c = col
			while c >= 0:
				if board[r][c] == 'Q':
					return False
				c -= 1
			return True

		def myqueens(col, ans):
			if col == n:
				res.append(ans.copy())
				return
			for r in range(n):
				if check(r, col):
					board[r][col] = 'Q'
					ans.append(r + 1)
					myqueens(col + 1, ans)
					board[r][col] = '.'
					ans.pop()
		ans = []
		myqueens(0, ans)
		return res


class Solution:

	def backtrack(self, col, stLeftCheck, upperLeftDiagCheck, lowerLeftDiagCheck, ans, lst, n):
		if col == n:
			ans.append(lst[:])
			return
		for row in range(n):
			if stLeftCheck[row] == 0 and upperLeftDiagCheck[row - col] == 0 and (lowerLeftDiagCheck[row + col] == 0):
				stLeftCheck[row] = 1
				upperLeftDiagCheck[row - col] = 1
				lowerLeftDiagCheck[row + col] = 1
				lst.append(row + 1)
				self.backtrack(col + 1, stLeftCheck, upperLeftDiagCheck, lowerLeftDiagCheck, ans, lst, n)
				lst.pop()
				stLeftCheck[row] = 0
				upperLeftDiagCheck[row - col] = 0
				lowerLeftDiagCheck[row + col] = 0

	def nQueen(self, n):
		stLeftCheck = [0] * n
		upperLeftDiagCheck = [0] * (2 * n - 1)
		lowerLeftDiagCheck = [0] * (2 * n)
		lst = []
		ans = []
		self.backtrack(0, stLeftCheck, upperLeftDiagCheck, lowerLeftDiagCheck, ans, lst, n)
		return ans


class Solution:

	def nQueen(self, n):
		row = set()
		posd = set()
		negd = set()
		res = []

		def queen(c, temp):
			if c == n:
				res.append(temp.copy())
				return
			for i in range(n):
				if i in row or i + c in posd or i - c in negd:
					continue
				row.add(i)
				posd.add(i + c)
				negd.add(i - c)
				temp.append(i + 1)
				queen(c + 1, temp)
				row.remove(i)
				posd.remove(i + c)
				negd.remove(i - c)
				temp.pop()
		queen(0, [])
		return res


def isSafe(board, row, col):
	for i in range(row):
		if board[i][col]:
			return False
	i = row
	j = col
	while i >= 0 and j >= 0:
		if board[i][j]:
			return False
		i -= 1
		j -= 1
	i = row
	j = col
	while j < len(board) and i >= 0:
		if board[i][j]:
			return False
		i = i - 1
		j = j + 1
	return True

def rec(mat, i, res, ans):
	if i == len(mat):
		ans.append(res.copy())
		return
	for j in range(len(mat)):
		if isSafe(mat, i, j):
			mat[i][j] = 1
			res.append(j + 1)
			rec(mat, i + 1, res, ans)
			res.pop()
			mat[i][j] = 0
	return False

class Solution:

	def nQueen(self, n):
		mat = [[0 for i in range(n)] for j in range(n)]
		ans = []
		rec(mat, 0, [], ans)
		return ans


class Solution:

	def nQueen(self, n):
		board = [[0 for i in range(n)] for i in range(n)]
		ans = []
		(left, left_up, left_down) = ([True] * n, [True] * (2 * n - 1), [True] * (2 * n - 1))

		def solve(col, board, ans, left, left_up, left_down, n):
			if col == n:
				k = []
				for i in range(len(board)):
					for j in range(len(board[i])):
						if board[i][j] == 1:
							k.append(j + 1)
				ans.append(k)
				return
			for row in range(n):
				if left[row] and left_up[n - 1 + row - col] and left_down[row + col]:
					board[row][col] = 1
					left[row] = False
					left_up[n - 1 + row - col] = False
					left_down[row + col] = False
					solve(col + 1, board, ans, left, left_up, left_down, n)
					board[row][col] = 0
					left[row] = True
					left_up[n - 1 + row - col] = True
					left_down[row + col] = True
		solve(0, board, ans, left, left_up, left_down, n)
		return sorted(ans)


class Solution:

	def is_safe(self, row, col, board, n):
		(x, y) = (row, col)
		while y >= 0:
			if board[x][y] == 1:
				return False
			y -= 1
		(x, y) = (row, col)
		while x >= 0 and y >= 0:
			if board[x][y] == 1:
				return False
			x -= 1
			y -= 1
		(x, y) = (row, col)
		while x < n and y >= 0:
			if board[x][y] == 1:
				return False
			x += 1
			y -= 1
		return True

	def solve1(self, col, board, ans, n):
		if col == n:
			temp = [i + 1 for r in board for (i, c) in enumerate(r) if c == 1]
			ans.append(temp)
			return
		for row in range(n):
			if self.is_safe(row, col, board, n):
				board[row][col] = 1
				self.solve(col + 1, board, ans, n)
				board[row][col] = 0

	def solve(self, col, board, ans, n, left_row, upper_left_diagonal, lower_left_diagonal):
		if col == n:
			temp = [i + 1 for r in board for (i, c) in enumerate(r) if c == 1]
			ans.append(temp)
			return
		for row in range(n):
			if left_row.get(row, 0) == 0 and upper_left_diagonal.get(n - 1 + col - row, 0) == 0 and (lower_left_diagonal.get(row + col, 0) == 0):
				board[row][col] = 1
				left_row[row] = 1
				upper_left_diagonal[n - 1 + col - row] = 1
				lower_left_diagonal[row + col] = 1
				self.solve(col + 1, board, ans, n, left_row, upper_left_diagonal, lower_left_diagonal)
				board[row][col] = 0
				left_row[row] = 0
				upper_left_diagonal[n - 1 + col - row] = 0
				lower_left_diagonal[row + col] = 0

	def nQueen(self, n):
		board = [[0 for j in range(n)] for i in range(n)]
		ans = []
		left_row = {}
		upper_left_diagonal = {}
		lower_left_diagonal = {}
		self.solve(0, board, ans, n, left_row, upper_left_diagonal, lower_left_diagonal)
		ans.sort()
		return ans


class Solution:

	def is_safe(self, row, col, board, n):
		x = row
		y = col
		while y >= 0:
			if board[x][y] == 1:
				return False
			y -= 1
		x = row
		y = col
		while x >= 0 and y >= 0:
			if board[x][y] == 1:
				return False
			x -= 1
			y -= 1
		x = row
		y = col
		while x < n and y >= 0:
			if board[x][y] == 1:
				return False
			x += 1
			y -= 1
		return True

	def solve1(self, col, board, ans, n):
		try:
			if col == n:
				temp = [[board[i][j] for j in range(n)] for i in range(n)]
				ans.append(temp)
				return
			for row in range(n):
				if self.is_safe(row, col, board, n):
					board[row][col] = 1
					self.solve(col + 1, board, ans, n)
					board[row][col] = 0
		except Exception as e:
			print(e)

	def solve(self, col, board, ans, n, left, upper, lower):
		try:
			if col == n:
				temp = [[board[i][j] for j in range(n)] for i in range(n)]
				ans.append(temp)
				return
			for row in range(n):
				if left[row] == 0 and lower[row + col] == 0 and (upper[n - 1 + col - row] == 0):
					board[row][col] = 1
					left[row] = 1
					lower[row + col] = 1
					upper[n - 1 + col - row] = 1
					self.solve(col + 1, board, ans, n, left, upper, lower)
					board[row][col] = 0
					left[row] = 0
					lower[row + col] = 0
					upper[n - 1 + col - row] = 0
		except Exception as e:
			print('Error: ', e)

	def nQueen(self, n):
		ans = []
		left = [0] * n
		upper = [0] * (2 * n - 1)
		lower = [0] * (2 * n - 1)
		board = [[0 for j in range(n)] for i in range(n)]
		self.solve(0, board, ans, n, left, upper, lower)
		output = []
		for mat in ans:
			temp = []
			for row in mat:
				for (i, r) in enumerate(row):
					if r == 1:
						temp.append(i + 1)
			output.append(temp)
		output.sort()
		return output


class Solution:

	def solve(self, col, board, n, ans, leftRow, leftUpperDiagonal, leftLowerDiagonal):
		if col == n:
			temp = []
			for i in range(n):
				for j in range(n):
					if board[i][j] == 1:
						temp.append(j + 1)
			ans.append(temp)
			return
		for row in range(n):
			if row not in leftRow and row + col not in leftLowerDiagonal and (row - col not in leftUpperDiagonal):
				board[row][col] = 1
				leftRow.add(row)
				leftLowerDiagonal.add(row + col)
				leftUpperDiagonal.add(row - col)
				self.solve(col + 1, board, n, ans, leftRow, leftUpperDiagonal, leftLowerDiagonal)
				board[row][col] = 0
				leftRow.remove(row)
				leftLowerDiagonal.remove(row + col)
				leftUpperDiagonal.remove(row - col)

	def nQueen(self, n):
		board = [[0 for j in range(n)] for i in range(n)]
		ans = []
		leftRow = set()
		leftUpperDiagonal = set()
		leftLowerDiagonal = set()
		self.solve(0, board, n, ans, leftRow, leftUpperDiagonal, leftLowerDiagonal)
		ans.sort()
		return ans


class Solution:

	def nQueen(self, n):
		row = set()
		posDiag = set()
		negDiag = set()
		res = []

		def helper(c, temp):
			if c == n:
				res.append(temp.copy())
				return
			for r in range(n):
				if r in row or r + c in posDiag or r - c in negDiag:
					continue
				row.add(r)
				posDiag.add(r + c)
				negDiag.add(r - c)
				temp.append(r + 1)
				helper(c + 1, temp)
				row.remove(r)
				posDiag.remove(r + c)
				negDiag.remove(r - c)
				temp.pop()
		helper(0, [])
		return res


class Solution:

	def nQueen(self, n):
		col = set()
		posdiag = set()
		negdiag = set()
		board = [['.' for i in range(n)] for j in range(n)]
		res = []
		copy = []

		def backtrack(r):
			if r == n:
				for i in range(n):
					for j in range(n):
						if board[i][j] == 'Q':
							copy.append(j + 1)
				x = copy.copy()
				res.append(x)
				copy.clear()
			for c in range(n):
				if c in col or r + c in posdiag or r - c in negdiag:
					continue
				col.add(c)
				posdiag.add(r + c)
				negdiag.add(r - c)
				board[r][c] = 'Q'
				backtrack(r + 1)
				col.remove(c)
				posdiag.remove(r + c)
				negdiag.remove(r - c)
				board[r][c] = '.'
		backtrack(0)
		return res


class Solution:

	def nQueen(self, n):
		ans = []
		board = [['.' for i in range(n)] for j in range(n)]

		def res(board, ans, n):
			temp = []
			for i in range(len(board)):
				j = 0
				for j in range(len(board[0])):
					if board[i][j] == 'Q':
						temp.append(j + 1)
			ans.append(temp)

		def safe(row, col, board, n):
			i = row
			j = col
			while j >= 0:
				if board[i][j] == 'Q':
					return False
				else:
					j -= 1
			i = row
			j = col
			while i >= 0 and j >= 0:
				if board[i][j] == 'Q':
					return False
				else:
					i -= 1
					j -= 1
			i = row
			j = col
			while i < n and j >= 0:
				if board[i][j] == 'Q':
					return False
				else:
					i += 1
					j -= 1
			return True

		def solve(col, n, ans, board):
			if col == n:
				res(board, ans, n)
				return
			else:
				for i in range(n):
					if safe(i, col, board, n):
						board[i][col] = 'Q'
						solve(col + 1, n, ans, board)
						board[i][col] = '.'
		solve(0, n, ans, board)
		ans.sort()
		return ans


class Solution:

	def nQueen(self, n):
		dig1 = [0] * 3 * n
		dig2 = [0] * 3 * n
		nodes = list(range(1, n + 1))
		output = []
		for i in range(1, n + 1):
			output += self.helper([i], dig1.copy(), dig2.copy(), nodes.copy(), n)
		return output

	def helper(self, path, dig1, dig2, nodes, n):
		if dig1[path[-1] - len(path)]:
			return []
		dig1[path[-1] - len(path)] = 1
		if dig2[path[-1] + len(path)]:
			return []
		dig2[path[-1] + len(path)] = 1
		nodes.remove(path[-1])
		if len(path) == n:
			return [path]
		output = []
		for item in nodes:
			output += self.helper(path.copy() + [item], dig1.copy(), dig2.copy(), nodes.copy(), n)
		return output


def n_queen(n, solns):

	def initialize():
		return {'q': [], 'r': [False for i in range(n)], 'ld': [False for i in range(2 * n - 1)], 'rd': [False for i in range(2 * n - 1)]}

	def isSolution(p):
		return len(p['q']) == n

	def actions(p):
		if isSolution(p):
			return []
		c = len(p['q'])
		return [r for r in range(n) if not (p['r'][r] or p['ld'][n - 1 + r - c] or p['rd'][r + c])]

	def take_action(p, a):
		c = len(p['q'])
		r = a
		ld = n - 1 + r - c
		rd = r + c
		p['q'].append(r)
		p['r'][r] = True
		p['ld'][ld] = True
		p['rd'][rd] = True

	def undo_action(p, a):
		c = len(p['q']) - 1
		r = a
		ld = n - 1 + r - c
		rd = r + c
		p['q'].pop()
		p['r'][r] = False
		p['ld'][ld] = False
		p['rd'][rd] = False

	def process(p):
		solns.append([x + 1 for x in p['q']])
	partial = initialize()

	def inner():
		if isSolution(partial):
			process(partial)
		else:
			for a in actions(partial):
				take_action(partial, a)
				inner()
				undo_action(partial, a)
	inner()

class Solution:

	def nQueen(self, n):
		solns = []
		n_queen(n, solns)
		return solns


class Solution:

	def solve(self, col, board, ans, n, temp, lp, up):
		if col == n:
			ans.append(temp.copy())
			return
		for row in range(0, n):
			if 1 not in board[row] and lp[row + col] == 0 and (up[n - 1 + col - row] == 0):
				board[row][col] = 1
				temp[row] = col + 1
				lp[row + col] = 1
				up[n - 1 + col - row] = 1
				self.solve(col + 1, board, ans, n, temp, lp, up)
				board[row][col] = 0
				temp[row] = 0
				lp[row + col] = 0
				up[n - 1 + col - row] = 0

	def nQueen(self, n):
		board = [[0 for i in range(n)] for i in range(n)]
		temp = [0 for i in range(n)]
		ans = list()
		lp = [0 for i in range(2 * n - 1)]
		up = [0 for i in range(2 * n - 1)]
		self.solve(0, board, ans, n, temp, lp, up)
		ans.sort()
		return ans


class Solution:

	def N_Queens(self, col, board, res, n, leftRow, uperDiagonal, downDiagonal):
		if col == n:
			temp = []
			for col in range(n):
				for row in range(n):
					if board[row][col] == 1:
						temp.append(row + 1)
			res.append(temp)
			return
		for row in range(n):
			if leftRow[row] == 0 and downDiagonal[col + row] == 0 and (uperDiagonal[n - 1 + col - row] == 0):
				board[row][col] = 1
				leftRow[row] = 1
				downDiagonal[col + row] = 1
				uperDiagonal[n - 1 + (col - row)] = 1
				self.N_Queens(col + 1, board, res, n, leftRow, uperDiagonal, downDiagonal)
				board[row][col] = 0
				leftRow[row] = 0
				downDiagonal[col + row] = 0
				uperDiagonal[n - 1 + col - row] = 0

	def nQueen(self, n):
		res = []
		board = [[0 for _ in range(n)] for _ in range(n)]
		leftRow = [0 for _ in range(n)]
		uperDiagonal = [0 for _ in range(2 * n)]
		downDiagonal = [0 for _ in range(2 * n)]
		self.N_Queens(0, board, res, n, leftRow, uperDiagonal, downDiagonal)
		return res


class Solution:

	def nQueen(self, n):
		board = [[0] * n for i in range(n)]

		def checkvalid(i, j, n):
			row = i
			col = j
			while row >= 0:
				if board[row][col] == 1:
					return False
				row -= 1
			row = i
			while col >= 0:
				if board[row][col] == 1:
					return False
				col -= 1
			col = j
			while col >= 0 and row >= 0:
				if board[row][col] == 1:
					return False
				col -= 1
				row -= 1
			row = i
			col = j
			while col >= 0 and row < n:
				if board[row][col] == 1:
					return False
				col -= 1
				row += 1
			return True
		res = []
		comb = []

		def findsol(col, n):
			if col >= n:
				temp = [i for i in comb]
				res.append(temp)
				return
			for r in range(n):
				if checkvalid(r, col, n):
					comb.append(r + 1)
					board[r][col] = 1
					findsol(col + 1, n)
					board[r][col] = 0
					comb.pop(-1)
		findsol(0, n)
		return res


class Solution:

	def nQueen(self, n):
		ans = []

		def is_safe(row, col, board):
			dcol = col
			while dcol >= 0:
				if board[row][dcol] == 'Q':
					return False
				dcol -= 1
			(dcol, drow) = (col, row)
			while dcol >= 0 and drow >= 0:
				if board[drow][dcol] == 'Q':
					return False
				drow -= 1
				dcol -= 1
			(dcol, drow) = (col, row)
			while dcol >= 0 and drow < n:
				if board[drow][dcol] == 'Q':
					return False
				drow += 1
				dcol -= 1
			return True

		def solve(col, board, pos):
			if col == n:
				ans.append(pos)
				return
			for row in range(n):
				if is_safe(row, col, board):
					board[row][col] = 'Q'
					solve(col + 1, board, pos + [row + 1])
					board[row][col] = '.'
		board = [['.' for _ in range(n)] for _ in range(n)]
		solve(0, board, [])
		return ans


class Solution:

	def nQueen(self, n):
		board = [['.' for j in range(n)] for i in range(n)]
		lc = [False] * n
		udc = [False] * (2 * n - 1)
		ldc = [False] * (2 * n - 1)
		result = []
		self.solve(0, n, board, lc, udc, ldc, result)
		result.sort()
		return result

	def solve(self, col, n, board, lc, udc, ldc, result):
		if col == n:
			temp = []
			for i in range(n):
				for j in range(n):
					if board[i][j] == 'Q':
						temp.append(j + 1)
			result.append(temp[:])
			return
		for row in range(n):
			if board[row][col] == '.' and (not lc[row]) and (not ldc[row + col]) and (not udc[n - 1 + col - row]):
				board[row][col] = 'Q'
				lc[row] = True
				ldc[row + col] = True
				udc[n - 1 + (col - row)] = True
				self.solve(col + 1, n, board, lc, udc, ldc, result)
				board[row][col] = '.'
				lc[row] = False
				ldc[row + col] = False
				udc[n - 1 + (col - row)] = False


class Solution:

	def nQueen(self, n):
		res = []

		def isSafe(r, c, board):
			temp_row = r
			temp_col = c
			while c >= 0 and r >= 1:
				if board[c] == r:
					return False
				r -= 1
				c -= 1
			r = temp_row
			c = temp_col
			while c >= 0:
				if board[c] == r:
					return False
				c -= 1
			r = temp_row
			c = temp_col
			while c >= 0 and r <= n:
				if board[c] == r:
					return False
				r += 1
				c -= 1
			return True

		def RecurPlace(col, board):
			if col == n:
				res.append(board.copy())
				return
			for row in range(1, n + 1):
				if isSafe(row, col, board):
					board[col] = row
					RecurPlace(col + 1, board)
					board[col] = -1
		board = [-1] * n
		RecurPlace(0, board)
		return res


class Solution:

	def nQueen(self, n):
		result = []
		board = [['.' for i in range(n)] for j in range(n)]
		leftcheck = [False] * n
		upperdiagonal = [False] * (2 * n - 1)
		lowerdiagonal = [False] * (2 * n - 1)
		self.solve(0, board, result, n, leftcheck, upperdiagonal, lowerdiagonal)
		result.sort()
		return result

	def solve(self, col, board, result, n, leftcheck, upperdiagonal, lowerdiagonal):
		if col == n:
			temp = []
			for i in range(n):
				for j in range(n):
					if board[i][j] == 'Q':
						temp.append(j + 1)
			result.append(temp[:])
			return
		for row in range(n):
			if not leftcheck[row] and (not lowerdiagonal[row + col]) and (not upperdiagonal[n - 1 + (col - row)]):
				board[row][col] = 'Q'
				leftcheck[row] = True
				lowerdiagonal[row + col] = True
				upperdiagonal[n - 1 + (col - row)] = True
				self.solve(col + 1, board, result, n, leftcheck, upperdiagonal, lowerdiagonal)
				board[row][col] = '.'
				leftcheck[row] = False
				lowerdiagonal[row + col] = False
				upperdiagonal[n - 1 + (col - row)] = False


class Solution:

	def nQueen(self, n):
		global b
		b = [[0 for j in range(n)] for i in range(n)]
		global l
		l = []

		def isSafe(i, j):
			for x in range(j):
				if b[i][x] == 1:
					return False
			for (x, y) in zip(range(i - 1, -1, -1), range(j - 1, -1, -1)):
				if b[x][y] == 1:
					return False
			for (x, y) in zip(range(i + 1, n), range(j - 1, -1, -1)):
				if b[x][y] == 1:
					return False
			return True

		def solve(j, ls):
			if j == n:
				a = []
				for i in ls:
					a.append(i)
				l.append(a)
				return
			for i in range(n):
				if isSafe(i, j):
					b[i][j] = 1
					ls.append(i + 1)
					solve(j + 1, ls)
					b[i][j] = 0
					ls.pop()
		solve(0, [])
		return l