N-Queens
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.
Constraints:
- 1 <= n <= 9
- Each queen must be placed in a unique row and column
- No two queens can be in the same diagonal
Examples:
Input: n = 4
Output: [[".Q..","...","....","...."],["...",".Q..","....","...."],["....","....",".Q..","...."],["....","....","....",".Q.."]]
Explanation: There are two solutions for n = 4: one with the queen in the first row and one with the queen in the second row.
Solutions
Backtracking
The backtracking approach is used to solve this problem. We start by initializing an empty board and then try to place a queen in each column of the current row. If it is safe to place a queen in a column, we make a recursive call to place queens in the next row. If it is not safe, we backtrack and try the next column.
def solveNQueens(n):
board = [['.' for _ in range(n)] for _ in range(n)]
result = []
def backtrack(row):
if row == n:
result.append([''.join(row) for row in board])
return
for col in range(n):
if is_valid(board, row, col):
board[row][col] = 'Q'
backtrack(row + 1)
board[row][col] = '.'
def is_valid(board, row, col):
for i in range(row):
for j in range(n):
if board[i][j] == 'Q' and (j == col or abs(j - col) == row - i):
return False
return True
backtrack(0)
return resultFollow-up:
Solve the problem for a rectangular board instead of a square board.
