N-Queens problem in Java
The Queens problem, also known as the N Queens problem, is a puzzle that involves placing N queens on an 8x8 chessboard in such a way that no two queens threaten each other. The goal is to find a configuration in which no two queens share the same row, column, or diagonal. The N Queen Problem is a well-known puzzle involving the task of placing N chess queens on an NxN chessboard so that no two queens can attack each other. It is a challenging problem in the field of combinatorial optimization and has been extensively studied in computer science.
Solution: 8*8
Solution: 4*4
Approach: Backtracking Algorithm
The approach used in the given code is a backtracking algorithm to solve the N-Queens problem. Backtracking is a systematic way of exploring all possible solutions by incrementally building a solution and undoing certain choices if they are found to be invalid. In this approach, we are taking the value of n as eight.
FileName: NQueensProblem.java
import java.util.*;
public class NQueensProblem {
private int[][] board; // Chessboard represented as a 2D array
private int boardSize; // Size of the chessboard
public NQueensProblem(int boardSize) {
this.boardSize = boardSize;
board = new int[boardSize][boardSize]; // Initialize the chessboard
}
public void solve() {
if (placeQueens(0)) { // Start placing queens from column 0
printBoard(); // If a solution is found in this then, print the board
} else {
System.out.println("No solution found here.");
}
}
private boolean placeQueens(int col) {
if (col == boardSize) {
return true; // All queens have been placed successfully
}
for (int row = 0; row < boardSize; row++) {
if (isSafe(row, col)) { // Check if it's safe to place a queen at this position
board[row][col] = 1; // Place the queen at (row, col)
if (placeQueens(col + 1)) { // Move to the next column recursively
return true; // If placing queens in subsequent columns is successful, return true
}
board[row][col] = 0; // Backtrack if a solution is not found and remove the queen from this position
}
}
return false; // Could not place a queen in this column, backtrack further
}
private boolean isSafe(int row, int col) {
// Check if there's a queen in the same row or diagonal present or not
for (int i = 0; i < col; i++) {
if (board[row][i] == 1) {
return false; // There's a queen in the same row
}
if (row - i - 1 >= 0 && board[row - i - 1][col - i - 1] == 1) {
return false; // There's a queen in the same diagonal (top-left to bottom-right)
}
if (row + i + 1 < boardSize && board[row + i + 1][col - i - 1] == 1) {
return false; // There's a queen in the same diagonal (bottom-left to top-right)
}
}
return true; // It's safe to place a queen at this position
}
private void printBoard() {
for (int row = 0; row < boardSize; row++) {
for (int col = 0; col < boardSize; col++) {
System.out.print(board[row][col] + " "); // Print the value (0 or 1) at each cell of the board
}
System.out.println(); // Move to the next row
}
}
public static void main(String[] args) {
int boardSize = 8; // Change this value to adjust the board size
NQueensProblem problem = new NQueensProblem(boardSize);
problem.solve();
}
}
Output:
1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0
Complexity:
Time Complexity: In the placeQueens() method, the algorithm iterates through each row for each column to check if it is safe to place a queen. This results in a time complexity of O(n^2), where n is the size of the chessboard. Since there are n columns in total, the overall time complexity of the algorithm is O(n^3).
Space Complexity: The space complexity of the algorithm is primarily determined by the chessboard representation. The board array of size n x n is used to track the positions of the queens. Thus, the space complexity of this backtracking algorithm is O(n^2).
Approach: Iterative Backtracking Using Stack
Another approach to solving the N-Queens problem is by using the Iterative Backtracking technique. Instead of using recursion, this approach uses a stack to keep track of the backtracking process. Here's an implementation of the N-Queens problem using the Iterative Backtracking approach. In this approach, we are considering the value of n as eight.
FileName: NQueensProblem.java
import java.util.Stack;
public class NQueensProblem {
private int boardSize; //size of chess board
private int[] queens;
private Stack stack;
public NQueensProblem(int boardSize) {
this.boardSize = boardSize; // Set the board size
queens = new int[boardSize]; // Initialize an array to store the row positions of the queens
stack = new Stack<>(); // Initialize a stack to track the backtracking process
}
public void solve() {
int col = 0;
while (col < boardSize || !stack.isEmpty()) { // Continue until all columns are explored or stack is empty
if (col < boardSize) { // Explore next column
int row = getNextValidRow(col); // Get next valid row for placing the queen in the column
if (row == -1) { // If no valid row found
if (stack.isEmpty()) { // If stack is empty, no solution found
break;
}
col = stack.pop(); // Backtrack by popping the column from stack
queens[col] = 0; // Reset queen's position in the current column
col++;
} else { // Valid row found
queens[col] = row; // Place the queen in the current column
stack.push(col); // Push the column onto the stack
col = 0; // Move to the next column
}
} else { // All columns have been explored
printBoard(); // Print the solution
col = stack.pop() + 1; // Backtrack by popping the column from stack and move to the next column
queens[col - 1] = 0; // Reset queen's position in the previous column
}
}
if (stack.isEmpty()) { // If stack is empty, no solution found
System.out.println("No solution found.");
}
}
private int getNextValidRow(int col) {
int row = queens[col];
while (++row < boardSize) { // Increment row until a valid position is found
if (isSafe(row, col)) { // Check if it is safe to place the queen at (row, col)
return row;
}
}
return -1; // No valid row found
}
private boolean isSafe(int row, int col) {
for (int i = 0; i < col; i++) { // Check for conflicts with previously placed queens
if (queens[i] == row || queens[i] == row + (col - i) || queens[i] == row - (col - i)) {
return false; // Conflict with a previously placed queen
}
}
return true; // It's safe to place a queen at this position
}
private void printBoard() {
for (int row = 0; row < boardSize; row++) { // Iterate through each row
for (int col = 0; col < boardSize; col++) { // Iterate through each column
if (queens[col] == row) { // If there is a queen at the current column and row
System.out.print("Q "); // Print "Q" to represent the queen
} else {
System.out.print("0 "); // Print "0" to represent an empty space
}
}
System.out.println(); // Move to the next line after printing each row
}
System.out.println();
}
public static void main(String[] args) {
int boardSize = 8; // Change this value to adjust the board size
NQueensProblem problem = new NQueensProblem(boardSize);
problem.solve();
}
}
Output:
1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0
Complexity:
Time Complexity: The algorithm utilizes backtracking to find solutions, exploring all possible configurations of queens on the chessboard. In the worst case, the algorithm needs to explore all possible combinations of queens on the board, which is proportional to the number of permutations of N queens on N positions. The time complexity can be approximated as O(N!), where N is the board size or the number of queens.
Space Complexity: The space complexity is determined by the stack used for backtracking and the array to store the positions of the queens. The stack stores the columns that have been explored, which can have a maximum of N elements in the worst case. The array to store the positions of the queens requires N elements. Therefore, the space complexity is O(N) for the stack and O(N) for the array, resulting in a total space complexity of O(N).