Le otto regine: convivere senza attaccarsi

In una soluzione deve esserci esattamente una regina per ogni colonna e una per ogni riga.

Puoi quindi descrivere una disposizione con otto numeri: per ogni colonna, annota la riga occupata dalla sua regina. Gli otto numeri dovranno essere tutti diversi.

Righe e colonne non bastano: due regine nelle colonne i e j sono sulla stessa diagonale quando la differenza tra le loro righe vale |i−j|.

Procedi colonna per colonna. Se una scelta crea un conflitto, cancellala e prova la riga successiva: non è un fallimento, è la parte essenziale della ricerca.

Indichiamo le colonne con A, B, C, D, E, F, G, H e numeriamo le righe da 1 a 8. Una disposizione valida è:

A1, B5, C8, D6, E3, F7, G2, H4

Le righe formano la sequenza (1, 5, 8, 6, 3, 7, 2, 4). Sono tutte diverse, quindi non esistono attacchi orizzontali; una regina per colonna esclude quelli verticali.

Per le diagonali si controlla ogni coppia di colonne: se le regine sono nelle colonne i e j e nelle righe rᵢ e rⱼ, non deve mai accadere |rᵢ−rⱼ|=|i−j|. La sequenza proposta supera tutti i controlli e quindi è una soluzione.

Un modo sistematico per trovarla è il backtracking: si colloca una regina nella prima riga disponibile di una colonna; si passa alla colonna seguente; se nessuna casella è lecita, si torna alla colonna precedente e si cambia scelta. Il processo termina quando tutte le otto colonne sono occupate.

Otto colonne, otto righe e nessuna diagonale condivisa.

Una disposizione con una regina per colonna è una sequenza di otto righe. Imporre che ogni riga compaia una sola volta significa cercare fra le permutazioni dei numeri da 1 a 8, non fra tutte le possibili scelte di otto caselle.

Resta il vincolo diagonale. Il backtracking costruisce la permutazione un elemento alla volta e scarta subito ogni prefisso incompatibile. È un esempio classico di problema di soddisfacimento di vincoli: le variabili sono le colonne, i valori possibili sono le righe e i vincoli vietano uguaglianze e diagonali.

Sulla scacchiera 8×8 esistono 92 soluzioni contando separatamente rotazioni e riflessioni. Se disposizioni ottenute per simmetria vengono considerate equivalenti, restano 12 soluzioni fondamentali.

Prova la versione con quattro regine su una scacchiera 4×4. Esistono due disposizioni, che sono immagini speculari. Una è descritta dalla sequenza (2, 4, 1, 3): regine in A2, B4, C1 e D3.

Verifica i tre vincoli e poi cerca la seconda soluzione senza limitarti a riflettere mentalmente la prima. Che cosa accade invece sulle scacchiere 2×2 e 3×3?

Il problema delle otto regine risale alla metà dell’Ottocento e attirò presto l’attenzione di matematici e appassionati. Oggi è usato per presentare ricorsione, backtracking, programmazione a vincoli e tecniche di ricerca.

Il numero 92 non significa che si debbano provare alla cieca tutte le configurazioni. Sfruttare subito righe, colonne, diagonali e simmetrie riduce drasticamente lo spazio di ricerca: una buona rappresentazione è già metà della soluzione.