LC051 - N-Queens

Problem

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

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

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: n = 4

Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Explanation: There exist two distinct solutions to the 4-queens puzzle

Solution

This problem came up before in a programming intro class and took me a whole day to figure out. And it still takes me a while to do 👉👈.

The problem can be solved either with an A* search or a Uniform Cost Search.

Time complexity is $O(N!)$ which is less than $O(N\times N)$, but can still be considered exponential. .

def solveNQueens(self, n: int) -> List[List[str]]:
	# use sets to track filled spots, cols and diagonals (pos and neg)
	cols = set()
	pos, neg = set(), set()
	board = [["."] * n for i in range(n)]
	res = []

	def backtrack(row):
		if row == n:
			temp = []
			for row in board:
				temp.append("".join(row))
			res.append(temp)
			return
	
		for col in range(n):
			if col in cols or (row + col) in pos or (row - col) in neg:
				continue
				
			cols.add(col)
			pos.add(row + col)
			neg.add(row - col)
			board[row][col] = "Q"
			
			backtrack(row + 1)

			# remove to backtrack for other sols
			cols.remove(col)
			pos.remove(row + col)
			neg.remove(row - col)
			board[row][col] = "."
	
	backtrack(0)
	return res