♛ N-Queens Problem

<?php
function solveNQueens(int $n): array {
    $result = [];
    $board = array_fill(0, $n, array_fill(0, $n, '.'));
    // Optimization: track occupied columns & diagonals
    $cols = array_fill(0, $n, false);
    $diag1 = array_fill(0, 2*$n, false); // row+col
    $diag2 = array_fill(0, 2*$n, false); // row-col+n
    placeQueens($board, 0, $n, $cols, $diag1, $diag2, $result);
    return $result;
}

function placeQueens(array &$board, int $row, int $n,
    array &$cols, array &$diag1, array &$diag2, array &$result): void {

    if ($row === $n) {
        $result[] = array_map(fn($r)=>implode('',$r), $board);
        return;
    }

    for ($col = 0; $col < $n; $col++) {
        if ($cols[$col] || $diag1[$row+$col] || $diag2[$row-$col+$n]) {
            continue; // Prune! This column/diagonal is attacked
        }

        // Place queen
        $board[$row][$col] = 'Q';
        $cols[$col] = true;
        $diag1[$row+$col] = true;
        $diag2[$row-$col+$n] = true;

        placeQueens($board, $row+1, $n, $cols, $diag1, $diag2, $result);

        // Backtrack
        $board[$row][$col] = '.';
        $cols[$col] = false;
        $diag1[$row+$col] = false;
        $diag2[$row-$col+$n] = false;
    }
}

// Print solutions for N=4
$solutions = solveNQueens(4);
foreach ($solutions as $i => $sol) {
    echo "Solution " . ($i+1) . ":\n";
    foreach ($sol as $row) echo "  $row\n";
}
// Solution 1:         Solution 2:
//   .Q..                ..Q.
//   ...Q                Q...
//   Q...                ...Q
//   ..Q.                .Q..

echo "Total solutions for n=4: " . count($solutions); // 2
echo "For n=8: " . count(solveNQueens(8)); // 92