Description:
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.
Examples:
Example 1:
Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above
Example 2:
Input: n = 1
Output: [["Q"]]
Solution in Python:
To solve the N-Queens problem in Python, we can use backtracking. The goal is to place n queens on an n×n chessboard such that no two queens attack each other.
Python
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
# This will store the final results
results = []
# Helper function to create the board configuration from queen positions
def create_board(state):
board = []
for i in range(n):
row = ['.'] * n
row[state[i]] = 'Q'
board.append(''.join(row))
return board
# The backtracking function
def backtrack(row, diagonals, anti_diagonals, cols, state):
# If we've reached the end of the rows, it means we've found a solution
if row == n:
results.append(create_board(state))
return
for col in range(n):
# Calculate the diagonal and anti-diagonal
diag = row - col
anti_diag = row + col
# Check if the position is under attack
if col in cols or diag in diagonals or anti_diag in anti_diagonals:
continue
# Add the position to our state
cols.add(col)
diagonals.add(diag)
anti_diagonals.add(anti_diag)
state.append(col)
# Move to the next row
backtrack(row + 1, diagonals, anti_diagonals, cols, state)
# Remove the position from our state (backtrack)
cols.remove(col)
diagonals.remove(diag)
anti_diagonals.remove(anti_diag)
state.pop()
# Initial call to the backtracking function
backtrack(0, set(), set(), set(), [])
return resultsDetailed Explanation:
- Initialization:
results: A list to store all the valid board configurations.
- Helper Function:
create_board(state): This function generates the board configuration from the list of queen positions (state). Each position instaterepresents the column index of the queen in that row.
- Backtracking Function:
backtrack(row, diagonals, anti_diagonals, cols, state): This function attempts to place a queen on each row of the board while ensuring no two queens can attack each other.- Parameters:
row: The current row we are trying to place a queen in.diagonals: A set to keep track of the columns and rows that are already under attack by a diagonal.anti_diagonals: A set to keep track of the columns and rows that are already under attack by an anti-diagonal.cols: A set to keep track of the columns that are already occupied by a queen.state: A list to keep track of the column positions of the queens in each row.
- Base Case: If
rowequalsn, it means we have successfully placed queens in all rows, and we add the current configuration toresults. - Iterate Through Columns: For each column in the current row, we calculate the diagonal and anti-diagonal indices. If placing a queen at the current position does not conflict with any other queen (i.e., it is not under attack), we add this position to our sets and state and recursively call
backtrackfor the next row. - Backtrack: After exploring placing a queen in the current column, we remove the position from our sets and state to explore other possibilities.
- Initial Call:
- The
backtrackfunction is initially called withrowset to 0 and empty sets fordiagonals,anti_diagonals, andcols, as well as an empty list forstate.
- The
This approach ensures that we explore all possible placements of queens in a systematic way, only adding valid configurations to the results.
Solution in Javascript:
JavaScript
/**
* @param {number} n
* @return {string[][]}
*/
var solveNQueens = function(n) {
// This will store the final results
let results = [];
// Helper function to create the board configuration from queen positions
const createBoard = (state) => {
let board = [];
for (let i = 0; i < n; i++) {
let row = '.'.repeat(n).split('');
row[state[i]] = 'Q';
board.push(row.join(''));
}
return board;
};
// The backtracking function
const backtrack = (row, diagonals, antiDiagonals, cols, state) => {
// If we've reached the end of the rows, it means we've found a solution
if (row === n) {
results.push(createBoard(state));
return;
}
for (let col = 0; col < n; col++) {
// Calculate the diagonal and anti-diagonal
let diag = row - col;
let antiDiag = row + col;
// Check if the position is under attack
if (cols.has(col) || diagonals.has(diag) || antiDiagonals.has(antiDiag)) {
continue;
}
// Add the position to our state
cols.add(col);
diagonals.add(diag);
antiDiagonals.add(antiDiag);
state.push(col);
// Move to the next row
backtrack(row + 1, diagonals, antiDiagonals, cols, state);
// Remove the position from our state (backtrack)
cols.delete(col);
diagonals.delete(diag);
antiDiagonals.delete(antiDiag);
state.pop();
}
};
// Initial call to the backtracking function
backtrack(0, new Set(), new Set(), new Set(), []);
return results;
};Solution in Java:
Java
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> solutions = new ArrayList<>();
char[][] board = new char[n][n];
// Initialize the board with empty spaces ('.')
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = '.';
}
}
// Start the backtracking process from the first row
backtrack(solutions, board, 0, n);
return solutions;
}
private void backtrack(List<List<String>> solutions, char[][] board, int row, int n) {
// If we've placed queens in all rows, add the board to the solutions list
if (row == n) {
solutions.add(constructBoard(board));
return;
}
// Try placing a queen in each column of the current row
for (int col = 0; col < n; col++) {
if (isValid(board, row, col, n)) {
// Place the queen
board[row][col] = 'Q';
// Move to the next row
backtrack(solutions, board, row + 1, n);
// Remove the queen (backtrack)
board[row][col] = '.';
}
}
}
private boolean isValid(char[][] board, int row, int col, int n) {
// Check if any queen is placed in the same column
for (int i = 0; i < row; i++) {
if (board[i][col] == 'Q') {
return false;
}
}
// Check the upper left diagonal
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') {
return false;
}
}
// Check the upper right diagonal
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j] == 'Q') {
return false;
}
}
return true;
}
private List<String> constructBoard(char[][] board) {
List<String> result = new ArrayList<>();
for (int i = 0; i < board.length; i++) {
result.add(new String(board[i]));
}
return result;
}
}Solution in C#:
C#
using System;
using System.Collections.Generic;
public class Solution {
public IList<IList<string>> SolveNQueens(int n) {
IList<IList<string>> results = new List<IList<string>>();
// Helper function to create the board configuration from queen positions
List<string> CreateBoard(List<int> state) {
List<string> board = new List<string>();
for (int i = 0; i < n; i++) {
char[] row = new char[n];
Array.Fill(row, '.');
row[state[i]] = 'Q';
board.Add(new string(row));
}
return board;
}
// The backtracking function
void Backtrack(int row, bool[] cols, bool[] diagonals, bool[] antiDiagonals, List<int> state) {
// If we've reached the end of the rows, it means we've found a solution
if (row == n) {
results.Add(CreateBoard(state));
return;
}
for (int col = 0; col < n; col++) {
// Calculate the diagonal and anti-diagonal
int diag = row - col + n - 1;
int antiDiag = row + col;
// Check if the position is under attack
if (cols[col] || diagonals[diag] || antiDiagonals[antiDiag]) {
continue;
}
// Add the position to our state
cols[col] = true;
diagonals[diag] = true;
antiDiagonals[antiDiag] = true;
state.Add(col);
// Move to the next row
Backtrack(row + 1, cols, diagonals, antiDiagonals, state);
// Remove the position from our state (backtrack)
cols[col] = false;
diagonals[diag] = false;
antiDiagonals[antiDiag] = false;
state.RemoveAt(state.Count - 1);
}
}
// Initial call to the backtracking function
Backtrack(0, new bool[n], new bool[2 * n - 1], new bool[2 * n - 1], new List<int>());
return results;
}
}