Conquering the n-Queens Puzzle - A Chessboard Challenge
In the realm of chessboard puzzles, the n-queens puzzle stands out as an intriguing problem that tests our strategic thinking. In this blog, we will delve into the challenge of placing n queens on an n x n chessboard in such a way that no two queens attack each other. We will explore the problem statement, discuss the approach, and provide detailed implementations in both Java and Python.
Problem Statement:
The n-queens puzzle involves placing n queens on an n x n chessboard in such a way that no two queens are attacking each other. Queens can attack in horizontal, vertical, and diagonal directions.
Example:
For a 4 x 4 chessboard, one possible solution to the n-queens puzzle is as follows:
. Q . .
. . . Q
Q . . .
. . Q .
In this arrangement, no two queens are attacking each other.
Approach:
To solve the n-queens puzzle, we can utilize backtracking. We will recursively try to place queens on the chessboard, ensuring that no two queens attack each other. Starting from the first row, we will explore all possible placements for each row, backtracking if a placement leads to conflicts.
- Create an n x n chessboard represented as a 2D array.
- Define a recursive function to solve the puzzle, taking the current row as a parameter.
- Base case: If the current row is equal to n, it means all queens have been successfully placed. Return true.
- Iterate through each column in the current row: a. Check if placing a queen at the current position leads to conflicts with previous queens. If so, skip to the next column. b. Place the queen at the current position. c. Recursively call the function for the next row. d. If the recursive call returns true, it means a valid solution has been found. Return true. e. If the recursive call returns false, backtrack by removing the queen from the current position and continue to the next column.
- If all columns have been tried without finding a valid solution, return false.
- In the main function, call the recursive function with the initial row set to 0 and print the valid solution if found.
Java Implementation:
public class NQueensPuzzle {
public static boolean solveNQueens(int[][] chessboard, int row) {
int n = chessboard.length;
if (row == n) {
// All queens have been placed successfully
return true;
}
for (int col = 0; col < n; col++) {
if (isSafe(chessboard, row, col)) {
chessboard[row][col] = 1; // Place the queen
// Recursively solve for the next row
if (solveNQueens(chessboard, row + 1)) {
return true;
}
// Backtrack: Remove the queen from the current position
chessboard[row][col] = 0;
}
}
return false;
}
public static boolean isSafe(int[][] chessboard, int row, int col) {
int n = chessboard.length;
// Check for conflicts in the same column
for (int i = 0; i < row; i++) {
if (chessboard[i][col] == 1) {
return false;
}
}
// Check for conflicts in the upper-left diagonal
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (chessboard[i][j] == 1) {
return false;
}
}
// Check for conflicts in the upper-right diagonal
for (int i = row, j = col; i >= 0 && j < n; i--, j++) {
if (chessboard[i][j] == 1) {
return false;
}
}
return true;
}
public static void printSolution(int[][] chessboard) {
int n = chessboard.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (chessboard[i][j] == 1) {
System.out.print("Q ");
} else {
System.out.print(". ");
}
}
System.out.println();
}
}
public static void main(String[] args) {
int n = 4;
int[][] chessboard = new int[n][n];
if (solveNQueens(chessboard, 0)) {
System.out.println("Valid Solution:");
printSolution(chessboard);
} else {
System.out.println("No solution found!");
}
}
}
Python Implementation:
def solve_n_queens(chessboard, row):
n = len(chessboard)
if row == n:
# All queens have been placed successfully
return True
for col in range(n):
if is_safe(chessboard, row, col):
chessboard[row][col] = 1 # Place the queen
# Recursively solve for the next row
if solve_n_queens(chessboard, row + 1):
return True
# Backtrack: Remove the queen from the current position
chessboard[row][col] = 0
return False
def is_safe(chessboard, row, col):
n = len(chessboard)
# Check for conflicts in the same column
for i in range(row):
if chessboard[i][col] == 1:
return False
# Check for conflicts in the upper-left diagonal
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if chessboard[i][j] == 1:
return False
# Check for conflicts in the upper-right diagonal
for i, j in zip(range(row, -1, -1), range(col, n)):
if chessboard[i][j] == 1:
return False
return True
def print_solution(chessboard):
n = len(chessboard)
for i in range(n):
for j in range(n):
if chessboard[i][j] == 1:
print("Q ", end="")
else:
print(". ", end="")
print()
n = 4
chessboard = [[0] * n for _ in range(n)]
if solve_n_queens(chessboard, 0):
print("Valid Solution:")
print_solution(chessboard)
else:
print("No solution found!")
Conclustion:
The n-queens puzzle challenges us to find a strategic arrangement of queens on a chessboard where no two queens can attack each other. By utilizing backtracking and careful placement, we can solve this puzzle efficiently. The implementations in Java and Python demonstrate the elegance and power of this solution. Armed with this knowledge, you can confidently tackle similar chessboard challenges and explore the fascinating world of strategic problem-solving.