Class ChessQueensOne

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

The N-Queens (First Solution)

This class calculates a single mathematically valid arrangement of N queens on an N × N chessboard such that no two queens threaten each other. It employs a highly optimized Backtracking algorithm that halts execution immediately upon discovering the first valid topological configuration.

Complexity

  • Time Complexity: Bounded by O(N!) - The algorithm attempts to place exactly one queen per column. The early termination mechanism drastically reduces the practical execution time if a valid arrangement exists early in the search tree.
  • 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
    ChessQueensOne(int boardSize)
    Initializes the N-Queens solver and allocates the necessary memory for tracking the state of the board in constant time.

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    hasFoundSolution()
    Retrieves the execution status to determine if a valid arrangement was discovered.
    void
    solve()
    Triggers the backtracking execution to find the first valid N-Queens arrangement.

    Methods inherited from class Object

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

  • Constructor Details

    • ChessQueensOne

      public ChessQueensOne(int boardSize)
      Initializes the N-Queens solver and allocates the necessary memory for tracking the state of the board in constant time.
      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 the first valid N-Queens arrangement.

    • hasFoundSolution

      public boolean hasFoundSolution()
      Retrieves the execution status to determine if a valid arrangement was discovered.
      Returns:
      true if a solution exists; false otherwise.