Backtracking (vuelta atrás)

def backtracking(parcial):
    if es_solucion(parcial):          # caso base: la solución está completa
        guardar(list(parcial))        # (una copia: parcial va a seguir cambiando)
        return
    for op in opciones(parcial):
        if es_valida(parcial, op):    # poda: no seguir por caminos imposibles
            aplicar(parcial, op)
            backtracking(parcial)
            deshacer(parcial, op)     # volver atrás para probar la siguiente opción

function backtracking(parcial) {
    if (esSolucion(parcial)) {         // caso base: la solución está completa
        guardar([...parcial]);         // (una copia: parcial va a seguir cambiando)
        return;
    }
    for (const op of opciones(parcial)) {
        if (esValida(parcial, op)) {   // poda: no seguir por caminos imposibles
            aplicar(parcial, op);
            backtracking(parcial);
            deshacer(parcial, op);     // volver atrás para probar la siguiente opción
        }
    }
}

void Backtracking(List<Opcion> parcial) {
    if (EsSolucion(parcial)) {                 // caso base: la solución está completa
        Guardar(new List<Opcion>(parcial));    // (una copia: parcial va a seguir cambiando)
        return;
    }
    foreach (Opcion op in Opciones(parcial)) {
        if (EsValida(parcial, op)) {           // poda: no seguir por caminos imposibles
            Aplicar(parcial, op);
            Backtracking(parcial);
            Deshacer(parcial, op);             // volver atrás para probar la siguiente opción
        }
    }
}

function backtracking(array &$parcial): void {
    if (esSolucion($parcial)) {        // caso base: la solución está completa
        guardar($parcial);             // (PHP copia el array al pasarlo por valor)
        return;
    }
    foreach (opciones($parcial) as $op) {
        if (esValida($parcial, $op)) { // poda: no seguir por caminos imposibles
            aplicar($parcial, $op);
            backtracking($parcial);
            deshacer($parcial, $op);   // volver atrás para probar la siguiente opción
        }
    }
}

n = 6
soluciones = llamadas = 0
columna_de_fila = [0] * n             # columna_de_fila[f] = columna de la reina de la fila f
col = [False] * n                     # columnas y diagonales ya ocupadas
diag1 = [False] * (2 * n - 1)         # fila + columna es igual en cada diagonal «/»
diag2 = [False] * (2 * n - 1)         # fila - columna es igual en cada diagonal «\»
primera = None


def tablero():
    filas = (" ".join("Q" if columna_de_fila[f] == c else "." for c in range(n)) for f in range(n))
    return "\n".join(filas) + "\n"


def colocar(fila):
    global soluciones, llamadas, primera
    llamadas += 1
    if fila == n:                     # todas colocadas: una solución más
        soluciones += 1
        if primera is None:
            primera = tablero()
        return
    for c in range(n):
        # poda: la casilla está atacada por una reina de una fila anterior
        if col[c] or diag1[fila + c] or diag2[fila - c + n - 1]:
            continue
        columna_de_fila[fila] = c
        col[c] = diag1[fila + c] = diag2[fila - c + n - 1] = True     # aplicar
        colocar(fila + 1)
        col[c] = diag1[fila + c] = diag2[fila - c + n - 1] = False    # deshacer


colocar(0)
print(f"{n} reinas: {soluciones} soluciones ({llamadas} llamadas)")
print(primera, end="")

const n = 6;
let soluciones = 0, llamadas = 0, primera = null;
const columnaDeFila = new Array(n).fill(0);       // columnaDeFila[f] = columna de la reina de la fila f
const col = new Array(n).fill(false);             // columnas y diagonales ya ocupadas
const diag1 = new Array(2 * n - 1).fill(false);   // fila + columna es igual en cada diagonal «/»
const diag2 = new Array(2 * n - 1).fill(false);   // fila - columna es igual en cada diagonal «\»

function colocar(fila) {
    llamadas++;
    if (fila === n) {                             // todas colocadas: una solución más
        soluciones++;
        if (primera === null) primera = tablero();
        return;
    }
    for (let c = 0; c < n; c++) {
        // poda: la casilla está atacada por una reina de una fila anterior
        if (col[c] || diag1[fila + c] || diag2[fila - c + n - 1]) continue;
        columnaDeFila[fila] = c;
        col[c] = diag1[fila + c] = diag2[fila - c + n - 1] = true;     // aplicar
        colocar(fila + 1);
        col[c] = diag1[fila + c] = diag2[fila - c + n - 1] = false;    // deshacer
    }
}

function tablero() {
    let s = "";
    for (let f = 0; f < n; f++) {
        const fila = [];
        for (let c = 0; c < n; c++) fila.push(columnaDeFila[f] === c ? "Q" : ".");
        s += fila.join(" ") + "\n";
    }
    return s;
}

colocar(0);
console.log(`${n} reinas: ${soluciones} soluciones (${llamadas} llamadas)`);
process.stdout.write(primera);

using System;
using System.Text;

class Program {
    static int n, soluciones, llamadas;
    static int[] columnaDeFila = Array.Empty<int>();   // columnaDeFila[f] = columna de la reina de la fila f
    static bool[] col = Array.Empty<bool>();           // columnas y diagonales ya ocupadas
    static bool[] diag1 = Array.Empty<bool>(), diag2 = Array.Empty<bool>();
    static string? primera;

    static void Colocar(int fila) {
        llamadas++;
        if (fila == n) {                     // todas colocadas: una solución más
            soluciones++;
            primera ??= Tablero();
            return;
        }
        for (int c = 0; c < n; c++) {
            // poda: la casilla está atacada por una reina de una fila anterior
            if (col[c] || diag1[fila + c] || diag2[fila - c + n - 1]) continue;
            columnaDeFila[fila] = c;
            col[c] = diag1[fila + c] = diag2[fila - c + n - 1] = true;     // aplicar
            Colocar(fila + 1);
            col[c] = diag1[fila + c] = diag2[fila - c + n - 1] = false;    // deshacer
        }
    }

    static string Tablero() {
        var sb = new StringBuilder();
        for (int f = 0; f < n; f++) {
            for (int c = 0; c < n; c++) sb.Append(c > 0 ? " " : "").Append(columnaDeFila[f] == c ? "Q" : ".");
            sb.Append('\n');
        }
        return sb.ToString();
    }

    static void Main() {
        n = 6;
        columnaDeFila = new int[n];
        col = new bool[n];
        diag1 = new bool[2 * n - 1];      // fila + columna es igual en cada diagonal «/»
        diag2 = new bool[2 * n - 1];      // fila - columna es igual en cada diagonal «\»
        Colocar(0);
        Console.WriteLine(
quot;{n} reinas: {soluciones} soluciones ({llamadas} llamadas)");
        Console.Write(primera);
    }
}

<?php
class NReinas {
    public int $soluciones = 0;
    public int $llamadas = 0;
    public ?string $primera = null;
    private array $columnaDeFila;       // columnaDeFila[f] = columna de la reina de la fila f
    private array $col;                 // columnas y diagonales ya ocupadas
    private array $diag1;               // fila + columna es igual en cada diagonal «/»
    private array $diag2;               // fila - columna es igual en cada diagonal «\»

    public function __construct(public int $n) {
        $this->columnaDeFila = array_fill(0, $n, 0);
        $this->col = array_fill(0, $n, false);
        $this->diag1 = array_fill(0, 2 * $n - 1, false);
        $this->diag2 = array_fill(0, 2 * $n - 1, false);
    }

    public function colocar(int $fila): void {
        $this->llamadas++;
        if ($fila === $this->n) {                     // todas colocadas: una solución más
            $this->soluciones++;
            $this->primera ??= $this->tablero();
            return;
        }
        for ($c = 0; $c < $this->n; $c++) {
            $d1 = $fila + $c;
            $d2 = $fila - $c + $this->n - 1;
            // poda: la casilla está atacada por una reina de una fila anterior
            if ($this->col[$c] || $this->diag1[$d1] || $this->diag2[$d2]) continue;
            $this->columnaDeFila[$fila] = $c;
            $this->col[$c] = $this->diag1[$d1] = $this->diag2[$d2] = true;    // aplicar
            $this->colocar($fila + 1);
            $this->col[$c] = $this->diag1[$d1] = $this->diag2[$d2] = false;   // deshacer
        }
    }

    private function tablero(): string {
        $s = "";
        for ($f = 0; $f < $this->n; $f++) {
            $fila = [];
            for ($c = 0; $c < $this->n; $c++) $fila[] = $this->columnaDeFila[$f] === $c ? "Q" : ".";
            $s .= implode(" ", $fila) . "\n";
        }
        return $s;
    }
}

$r = new NReinas(6);
$r->colocar(0);
echo "{$r->n} reinas: {$r->soluciones} soluciones ({$r->llamadas} llamadas)\n";
echo $r->primera;