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 the number of distinct solutions to the n-queens puzzle.

Example:


Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Complete search

Starter code: class Solution:
    def totalNQueens(self, n: int) -> int:
        

Solutions:
class Solution:

	def totalNQueens(self, n):

		def dfs(lst, xy_dif, xy_sum):
			p = len(lst)
			if p == n:
				res.append(lst)
			for q in range(n):
				if q not in lst and p - q not in xy_dif and (p + q not in xy_sum):
					dfs(lst + [q], xy_dif + [p - q], xy_sum + [p + q])
		res = []
		dfs([], [], [])
		return len(res)


class Solution:

	def totalNQueens(self, n):
		result = []
		self.DFS(n, 0, '', [], [], [], result)
		print(result)
		return len(result)

	def DFS(self, n, row, sss, check_col, check_diag1, check_diag2, result):
		if len(sss) == n:
			result.append('.')
			return
		for col in range(0, n):
			if col in check_col:
				continue
			if row + col in check_diag1:
				continue
			if row - col in check_diag2:
				continue
			self.DFS(n, row + 1, sss + str(col), check_col + [col], check_diag1 + [row + col], check_diag2 + [row - col], result)


class Solution:

	def totalNQueens(self, n):
		placement = []

		def can_place_queen(row, col):
			for (i, j) in enumerate(placement):
				if col == j or abs(col - j) == row - i:
					return False
			return True

		def place_in_row(row):
			if row == n:
				return 1
			count = 0
			for col in range(n):
				if can_place_queen(row, col):
					placement.append(col)
					count += place_in_row(row + 1)
					placement.pop()
			return count
		return place_in_row(0)


class Solution:

	def totalNQueens(self, n):
		rl = [0]
		col = [False for x in range(n)]
		dia1 = [False for x in range(2 * n - 1)]
		dia2 = [False for x in range(2 * n - 1)]
		self.putQueen(n, col, dia1, dia2, rl, 0)
		return rl[0]

	def putQueen(self, n, col, dia1, dia2, rl, index):
		if index == n:
			rl[0] += 1
			return True
		for i in range(n):
			if not col[i] and (not dia1[index + i]) and (not dia2[index - i + n - 1]):
				col[i] = True
				dia1[index + i] = True
				dia2[index - i + n - 1] = True
				self.putQueen(n, col, dia1, dia2, rl, index + 1)
				col[i] = False
				dia1[index + i] = False
				dia2[index - i + n - 1] = False


class Solution:

	def totalNQueens(self, n):
		if n <= 0:
			return 0
		diag_lr = [True] * (2 * n - 1)
		diag_rl = [True] * (2 * n - 1)
		vert = [True] * n
		res = []

		def _check_board(x, y):
			return vert[y] and diag_lr[y - x + n - 1] and diag_rl[x + y]

		def _helper(x):
			if x == n:
				res.append(1)
				return
			for y in range(n):
				if _check_board(x, y):
					vert[y] = False
					diag_lr[y - x + n - 1] = False
					diag_rl[x + y] = False
					_helper(x + 1)
					vert[y] = True
					diag_lr[y - x + n - 1] = True
					diag_rl[x + y] = True
		_helper(0)
		return len(res)


class Solution:

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

	def placeQueen(self, row, n):
		if row == n:
			tmp = [''.join(el) for el in self.board]
			self.result += 1
			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 totalNQueens(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 totalNQueens(self, n):
		ans = []

		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 len(result)


class Solution:

	def totalNQueens(self, n):

		def dfs(cols, diag_45, diag_135, depth=0):
			nonlocal result
			row = len(cols)
			if row == n:
				result += 1
				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)
		result = 0
		dfs([], [], [])
		return result


class Solution:

	def find_arrangements(self, arrangement, diag1_used, diag2_used, col_used, x, n):
		if x == n:
			return 1
		res = 0
		for y in range(n):
			diag1 = x + y
			diag2 = x - y + n
			if not diag1_used[diag1] and (not diag2_used[diag2]) and (not col_used[y]):
				arrangement.append(y)
				diag1_used[diag1] = True
				diag2_used[diag2] = True
				col_used[y] = True
				cur_res = self.find_arrangements(arrangement, diag1_used, diag2_used, col_used, x + 1, n)
				arrangement.pop()
				diag1_used[diag1] = False
				diag2_used[diag2] = False
				col_used[y] = False
				res += cur_res
		return res

	def totalNQueens(self, n):
		arrangement = []
		diag1_used = [False] * (2 * n)
		diag2_used = [False] * (2 * n)
		col_used = [False] * n
		return self.find_arrangements(arrangement, diag1_used, diag2_used, col_used, 0, n)


class Solution:

	def totalNQueens(self, n):
		count = 0

		def solve(rows, cols, diag0, diag1, n):
			nonlocal count
			freerows = {i for i in range(n)} - rows
			if not freerows:
				count += 1
				return
			i = freerows.pop()
			candidates = []
			for j in range(n):
				if j in cols:
					continue
				if i + j in diag0:
					continue
				if i - j in diag1:
					continue
				rows.add(i)
				cols.add(j)
				diag0.add(i + j)
				diag1.add(i - j)
				solve(rows, cols, diag0, diag1, n)
				rows.remove(i)
				cols.remove(j)
				diag0.remove(i + j)
				diag1.remove(i - j)
		solve(set(), set(), set(), set(), n)
		return count


class Solution:

	def totalNQueens(self, n):
		row = [x for x in range(n)]
		table = []
		for i in range(n):
			table.append(row.copy())
		result = self.solve(table, 0)
		return len(result)

	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