The N-Queens problem is a classic algorithmic problem in which the task is to place N chess queens on an N×N chessboard such that no two queens threaten each other. This means that no two queens can be in the same row, column, or diagonal.

Program Structure

The program uses backtracking to explore all possible arrangements of queens on the board. It checks for safe placements and recursively places queens until a solution is found or all possibilities are exhausted.

Java Code

public class NQueens {
    
    private int[] board; // To hold the positions of queens
    private int solutionsCount = 0; // To count the number of solutions

    public NQueens(int n) {
        board = new int[n]; // Initialize board for n queens
        solveNQueens(0); // Start solving from the first row
    }

    /**
     * Method to solve the N-Queens problem using backtracking.
     * @param row The current row to place a queen.
     */
    private void solveNQueens(int row) {
        int n = board.length;
        if (row == n) {
            printSolution(); // Print the solution when all queens are placed
            solutionsCount++;
            return;
        }

        for (int col = 0; col < n; col++) {
            if (isSafe(row, col)) { // Check if it's safe to place a queen
                board[row] = col; // Place queen
                solveNQueens(row + 1); // Recur to place next queen
                // No need to remove the queen; just overwrite for the next iteration
            }
        }
    }

    /**
     * Check if a queen can be placed on the board at board[row][col].
     * @param row The row of the queen.
     * @param col The column of the queen.
     * @return true if safe, false otherwise.
     */
    private boolean isSafe(int row, int col) {
        for (int i = 0; i < row; i++) {
            if (board[i] == col || Math.abs(board[i] - col) == Math.abs(i - row)) {
                return false; // Column or diagonal conflict
            }
        }
        return true; // No conflict
    }

    /**
     * Prints the current solution in a readable format.
     */
    private void printSolution() {
        System.out.println("Solution " + (solutionsCount + 1) + ":");
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                if (board[i] == j) {
                    System.out.print("Q "); // Place queen
                } else {
                    System.out.print(". "); // Empty space
                }
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int n = 8; // You can change the value of N here
        new NQueens(n); // Create an instance of NQueens with n queens
    }
}

Explanation of the Code

• Class Definition: The class NQueens contains all necessary methods and variables for solving the N-Queens problem.
• Board Representation: The board array represents the chessboard, where the index is the row and the value is the column of the queen.
• Recursive Backtracking: The method solveNQueens(int row) places queens row by row and backtracks if a conflict is found.
• Safety Check: The isSafe(int row, int col) method checks if placing a queen at the given row and column is safe from attacks by previously placed queens.
• Solution Printing: The printSolution() method displays each valid arrangement of queens on the board.

Usage

To run the program, simply compile and execute it in a Java environment. You can change the value of n in the main method to solve the N-Queens problem for different board sizes.

Conclusion

The N-Queens problem is a great way to practice backtracking algorithms. The provided Java program efficiently explores all possible configurations and outputs all valid solutions for the given board size.