51. N-Queens

package Leetcode.Backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author zhengxingxing
 * @date 2024/12/01
 */
public class NQueens {
    /**
     * Main method to solve the N-Queens problem for a given board size.
     *
     * This method initializes the solving process and returns all valid queen arrangements.
     *
     * @param n The size of the chessboard (number of queens to place)
     * @return A list of all possible queen arrangements, where each arrangement
     *         is represented as a list of string representations of board rows
     *
     * Key Steps:
     * 1. Create an empty result list to store solutions
     * 2. Initialize a queens array to track queen positions
     * 3. Start the backtracking process from the first row
     * 4. Return all found solutions
     */
    public static List<List<String>> solveNQueens(int n) {
        // List to store all valid solutions
        List<List<String>> result = new ArrayList<>();

        // Array to track queen positions (index = row, value = column)
        int[] queens = new int[n];
        // Initialize all positions as unoccupied
        Arrays.fill(queens, -1);

        // Start backtracking from the first row
        backtrack(queens, 0, n, result);

        return result;
    }

    /**
     * Recursive backtracking method to explore all possible queen placements.
     *
     * This is the core algorithm that systematically tries to place queens
     * on the board while maintaining the N-Queens constraints.
     *
     * @param queens Array representing current queen positions
     * @param row Current row being processed
     * @param n Total board size
     * @param result List to store all valid solutions
     *
     * Detailed Algorithm:
     * 1. Base Case: If all rows are processed, add current solution to results
     * 2. For each column in the current row:
     *    - Check if placing a queen is valid
     *    - If valid, place the queen
     *    - Recursively process the next row
     *    - Implicitly backtrack by trying next column positions
     */
    private static void backtrack(int[] queens, int row, int n, List<List<String>> result) {
        // If we've successfully placed queens in all rows, we've found a solution
        if(row == n){
            result.add(constructSolution(queens, n));
            return;
        }

        // Try placing a queen in each column of the current row
        for (int col = 0; col < n; col++) {
            // Check if placing a queen at this position is valid
            if(isValid(queens, row, col)){
                // Place the queen
                queens[row] = col;

                // Recursively process the next row
                backtrack(queens, row + 1, n, result);
            }
        }
    }


    /**
     * Validates whether a queen can be placed at the given position.
     *
     * Checks two key constraints:
     * 1. No queen in the same column
     * 2. No queen on the same diagonal
     *
     * @param queens Current queen positions
     * @param row Row of the new queen
     * @param col Column of the new queen
     * @return true if queen placement is valid, false otherwise
     *
     * Validation Logic:
     * - Column Check: Ensure no queen in the same column
     * - Diagonal Check: Use absolute value difference to detect diagonal conflicts
     *   - Diagonal conflict occurs when |row1 - row2| == |col1 - col2|
     */
    private static boolean isValid(int[] queens, int row, int col) {
        // Check all previous rows
        for (int i = 0; i < row; i++) {
            // Check column conflict
            if(queens[i] == col){
                return false;
            }

            // Check diagonal conflicts using absolute value difference
            // If |row distance| == |column distance|, queens are on the same diagonal
            if(Math.abs(row - i) == Math.abs(col - queens[i])){
                return false;
            }
        }

        return true;
    }

    /**
     * Converts the internal queens array representation to a visual board layout.
     *
     * Transforms the queens array into a list of strings where:
     * - 'Q' represents a queen
     * - '.' represents an empty square
     *
     * @param queens Array representing queen positions
     * @param n Board size
     * @return A list of strings representing the board configuration
     */
    private static List<String> constructSolution(int[] queens, int n) {
        List<String> solution = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            // Create a row filled with '.' initially
            char[] row = new char[n];
            Arrays.fill(row, '.');

            // Place queen at the correct column
            row[queens[i]] = 'Q';

            // Convert row to string and add to solution
            solution.add(new String(row));
        }

        return solution;
    }

    public static void main(String[] args) {
        // Test cases for different board sizes
        int[] testCases = {1, 4};

        for (int n : testCases) {
            System.out.println("N = " + n + " Queens Problem Solutions:");
            List<List<String>> solutions = solveNQueens(n);

            // Print number of solutions
            System.out.println("Number of Solutions: " + solutions.size());

            // Print each solution's board layout
            for (int i = 0; i < solutions.size(); i++) {
                System.out.println("Solution " + (i + 1) + ":");
                for (String row : solutions.get(i)) {
                    System.out.println(row);
                }
                System.out.println(); // Separator between solutions
            }

            System.out.println("-------------------");
        }
    }
}