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.
![N-Queens problem in Java](https://static.tutorialandexample.com/java/n-queens-problem-in-java1.png)
Solution: 8*8
![N-Queens problem in Java](https://static.tutorialandexample.com/java/n-queens-problem-in-java2.png)
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 Stackstack; 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).