Solving the 8 queens

Solving the N-Queens Problem with Breadth-First Search in Java

Explore the classic N-Queens problem and learn how to implement a Breadth-First Search (BFS) algorithm in Java to find all valid solutions.

The N-Queens problem is a classic puzzle in computer science and artificial intelligence. The challenge is to place N non-attacking queens on an N×N chessboard. A queen can attack any piece in the same row, column, or diagonal. This article will guide you through understanding the problem and implementing a solution using Breadth-First Search (BFS) in Java.

Understanding the N-Queens Problem

The core of the N-Queens problem lies in finding a configuration where no two queens threaten each other. This means:

1. No two queens share the same row.
2. No two queens share the same column.
3. No two queens share the same diagonal.

Since each queen must be in a different row, we can simplify the problem by placing one queen per row. The challenge then becomes selecting the correct column for each queen to satisfy the column and diagonal constraints. For an 8x8 board, there are 92 unique solutions.

flowchart TD
    A[Start with empty board] --> B{Place Queen in Row 0?}
    B --> C{Try Column 0 to N-1}
    C --> D{Is position (Row, Col) safe?}
    D -- Yes --> E[Add Queen to board]
    E --> F{All N Queens placed?}
    F -- Yes --> G[Solution Found!]
    F -- No --> B
    D -- No --> C
    G --> H[Backtrack/Explore next option]
    H --> C

Conceptual flow for placing queens on the board

Breadth-First Search (BFS) Approach

BFS is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key') and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. For the N-Queens problem, BFS can be adapted by considering each state as a partial board configuration. We start with an empty board and, at each level, explore all valid placements for the next queen.

Each 'state' in our BFS will represent a board configuration up to a certain row. We'll use a queue to manage the states to explore. When we process a state, we try to place the next queen in the current row. For each valid placement, we create a new state (a new board configuration) and add it to the queue. This continues until we find a state where all N queens are successfully placed.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class NQueensBFS {

    static class BoardState {
        int[] queens;
        int row;

        public BoardState(int[] queens, int row) {
            this.queens = queens.clone(); // Deep copy
            this.row = row;
        }
    }

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> solutions = new ArrayList<>();
        Queue<BoardState> queue = new LinkedList<>();

        // Initial state: empty board, starting at row 0
        queue.offer(new BoardState(new int[n], 0));

        while (!queue.isEmpty()) {
            BoardState current = queue.poll();

            // If all queens are placed, add to solutions
            if (current.row == n) {
                solutions.add(formatBoard(current.queens, n));
                continue;
            }

            // Try placing a queen in the current row (current.row)
            // in each possible column (col)
            for (int col = 0; col < n; col++) {
                if (isSafe(current.queens, current.row, col)) {
                    int[] newQueens = current.queens.clone();
                    newQueens[current.row] = col;
                    queue.offer(new BoardState(newQueens, current.row + 1));
                }
            }
        }
        return solutions;
    }

    private boolean isSafe(int[] queens, int currentRow, int currentCol) {
        for (int prevRow = 0; prevRow < currentRow; prevRow++) {
            int prevCol = queens[prevRow];

            // Check column conflict
            if (prevCol == currentCol) {
                return false;
            }

            // Check diagonal conflict
            // abs(currentCol - prevCol) == abs(currentRow - prevRow)
            if (Math.abs(currentCol - prevCol) == Math.abs(currentRow - prevRow)) {
                return false;
            }
        }
        return true;
    }

    private List<String> formatBoard(int[] queens, int n) {
        List<String> board = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringBuilder row = new StringBuilder();
            for (int j = 0; j < n; j++) {
                if (queens[i] == j) {
                    row.append('Q');
                } else {
                    row.append('.');
                }
            }
            board.add(row.toString());
        }
        return board;
    }

    public static void main(String[] args) {
        NQueensBFS solver = new NQueensBFS();
        int n = 4; // Example for 4 queens
        List<List<String>> solutions = solver.solveNQueens(n);

        System.out.println("Solutions for " + n + " Queens:");
        for (List<String> solution : solutions) {
            for (String row : solution) {
                System.out.println(row);
            }
            System.out.println();
        }
    }
}

Java implementation of N-Queens using Breadth-First Search.

Analyzing the Solution

The BoardState class encapsulates the current placement of queens (queens array where queens[i] is the column of the queen in row i) and the row we are currently trying to place a queen in. The isSafe method is crucial; it checks for conflicts with previously placed queens (in rows 0 to currentRow - 1). It verifies both column and diagonal conflicts.

The solveNQueens method initializes the queue with an empty board state. It then iteratively dequeues a state, attempts to place a queen in the next available row, and enqueues new valid states. Once current.row == n, a complete solution has been found, and it's formatted for output.

This BFS approach systematically explores all possible valid placements, ensuring that all solutions are found without redundant checks for invalid partial configurations.

1. Initialize the Queue

Create a Queue<BoardState> and add an initial BoardState representing an empty board, starting at row 0.

2. Process States

While the queue is not empty, dequeue a BoardState. This state represents a partial solution up to current.row - 1.

3. Check for Solution

If current.row equals n (the board size), it means all n queens have been successfully placed. Format this board configuration and add it to your list of solutions.

4. Explore Next Placements

If not all queens are placed, iterate through each column (col) from 0 to n-1 in the current.row. For each column, check if placing a queen there is safe using the isSafe method.

5. Enqueue New States

If a position (current.row, col) is safe, create a new BoardState with the queen placed at (current.row, col) and increment current.row. Enqueue this new state for further exploration.