The N-Queens problems asks us to place N queens on an N * N chessboard such that no two queens threaten each other. The means no two queens can be in the the same row, column, or diagonal. The challenge is to find all possible configurations of the board that satisfy these conditions.
1. Understand the Problem
Problem Statement
• Place N queens on an N \times N chessboard so that:
• No two queens share the same row.
• No two queens share the same column.
• No two queens share the same diagonal.
Key Constraints
1. One queen per row.
2. A queen threatens another if:
• They share the same column.
• They share the same diagonal:
• Left diagonal: Row – Column is constant.
• Right diagonal: Row + Column is constant.
Output
• All valid arrangements of queens, where each arrangement is represented by the board configuration.
Starting with the Naive Approach: Brute Force for N-Queens
The brute force solution involves generating all possible placements of queens on the chessboard and then filtering out those that violate the constraints. While this approach is conceptually simple, it is computationally expensive.
import java.util.*;
public class NQueensBruteForce {
public List<List<String>> solveNQueens(int n) {
List<List<String>> solutions = new ArrayList<>();
List<Integer> cols = new ArrayList<>();
for (int i = 0; i < n; i++) {
cols.add(i);
}
// Generate all permutations of columns
List<List<Integer>> permutations = generatePermutations(cols);
// Filter permutations that are valid N-Queens solutions
for (List<Integer> permutation : permutations) {
if (isValid(permutation)) {
solutions.add(constructBoard(permutation));
}
}
return solutions;
}
private List<List<Integer>> generatePermutations(List<Integer> cols) {
List<List<Integer>> permutations = new ArrayList<>();
backtrack(permutations, new ArrayList<>(), new boolean[cols.size()], cols);
return permutations;
}
private void backtrack(List<List<Integer>> permutations, List<Integer> current, boolean[] used, List<Integer> cols) {
if (current.size() == cols.size()) {
permutations.add(new ArrayList<>(current));
return;
}
for (int i = 0; i < cols.size(); i++) {
if (used[i]) continue;
used[i] = true;
current.add(cols.get(i));
backtrack(permutations, current, used, cols);
current.remove(current.size() - 1);
used[i] = false;
}
}
private boolean isValid(List<Integer> permutation) {
for (int i = 0; i < permutation.size(); i++) {
for (int j = i + 1; j < permutation.size(); j++) {
if (Math.abs(permutation.get(i) - permutation.get(j)) == Math.abs(i - j)) {
return false; // Diagonal conflict
}
}
}
return true;
}
private List<String> constructBoard(List<Integer> permutation) {
List<String> board = new ArrayList<>();
for (int i = 0; i < permutation.size(); i++) {
char[] row = new char[permutation.size()];
Arrays.fill(row, '.');
row[permutation.get(i)] = 'Q';
board.add(new String(row));
}
return board;
}
}Steps in Brute Force Approach
1. Generate All Possible Placements:
• For N queens, we generate all permutations of queen placements across N rows and N columns.
• Each permutation represents a potential solution.
2. Filter Invalid Placements:
• Check each permutation to ensure that:
• No two queens share the same column.
• No two queens share the same diagonal.
3. Return Valid Solutions:
• Collect and return only the permutations that meet the criteria.
