Class ChessQueensAll

java.lang.Object
topics.backtracking.nqueens.ChessQueensAll
public class ChessQueensAll extends Object

The N-Queens (All Solutions)

This class calculates all mathematically valid arrangements of N queens on an N × N chessboard such that no two queens threaten each other. It employs a highly optimized Backtracking algorithm utilizing 1D boolean arrays to achieve O(1) feasibility checks for rows and diagonals.

Complexity

  • Time Complexity: Bounded by O(N!) - The algorithm places exactly one queen per column, drastically reducing the search space compared to testing all board cells. Extensive pruning further limits actual execution paths.
  • Space Complexity: O(N) - Required for the state-tracking boolean arrays and the maximum depth of the JVM call stack.
Author:
vicegd

  • Constructor Summary

    Constructors
    Constructor
    Description
    ChessQueensAll(int boardSize)
    Initializes the N-Queens solver and allocates the necessary memory for tracking the state of the board.

  • Method Summary

    Modifier and Type
    Method
    Description
    int
    getSolutionCount()
    Retrieves the total number of valid board configurations discovered.
    void
    solve()
    Triggers the backtracking execution to find all valid N-Queens arrangements.

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • ChessQueensAll

      public ChessQueensAll(int boardSize)
      Initializes the N-Queens solver and allocates the necessary memory for tracking the state of the board.
      Parameters:
      boardSize - The size of the side of the square board (N × N), which also equals the number of queens to place.

  • Method Details

    • solve

      public void solve()
      Triggers the backtracking execution to find all valid N-Queens arrangements.

    • getSolutionCount

      public int getSolutionCount()
      Retrieves the total number of valid board configurations discovered.
      Returns:
      The integer count of valid N-Queens solutions.