Il Problema delle N-Regine: Un Viaggio Attraverso Logica e Programmazione

Il problema delle N-Regine è un classico problema di logica e programmazione che ha affascinato amanti degli scacchi, matematici e programmatori per decenni. La sfida sembra semplice all’inizio: data una scacchiera NxN, puoi posizionare N regine in modo che nessuna di esse attacchi l’altra? Come sanno molti giocatori di scacchi, la regina è il pezzo più potente del gioco: può muoversi orizzontalmente, verticalmente e diagonalmente. Quindi, ogni regina deve avere la sua traversa, colonna e diagonale libere da altre regine.

Per scacchiere piccole, il problema può sembrare facile. Per N=1, puoi semplicemente posizionare la regina su qualsiasi casa. Ma per N=2 e N=3, non c’è modo di posizionare le regine senza che si attacchino a vicenda. Solo per N≥4 il problema ha almeno una soluzione.

4x4: Il Primo Passo

Iniziamo con un caso semplice: la scacchiera 4x4. Se provassimo a posizionare tutti i possibili arrangiamenti di 4 regine sulle 16 case, senza preoccuparci dei loro movimenti, otterremmo:

$$\binom{16}{4} = 1820$$

Questo è il numero totale di modi per scegliere 4 case su 16. Ma molti di questi arrangiamenti non soddisfano le regole del problema. Possiamo pensare al problema in modo più efficiente applicando livelli di semplificazione:

Primo livello
Poiché una regina controlla l’intera traversa in cui si trova, possiamo semplificare il problema posizionando solo una regina per traversa. Questo dà:

$$4^4 = 256$$

Perché $4^4$? Perché per ognuna delle 4 traverse, possiamo scegliere una qualsiasi delle 4 colonne. A questo punto, però, alcune configurazioni potrebbero avere più regine nella stessa colonna.

Secondo livello
Aggiungiamo la regola di una regina per colonna: nessuna colonna può avere più di una regina. Ora contiamo tutte le possibili permutazioni di colonne:

$$4! = 24$$

Terzo livello
Eliminiamo poi qualsiasi arrangiamento in cui le regine si attaccano a vicenda diagonalmente. A questo livello, dobbiamo controllare ogni permutazione per vedere se le diagonali sono sicure. Per 4x4, solo 2 soluzioni soddisfano questa regola. Per N più grandi, è necessario un algoritmo specifico per trovare le soluzioni valide.

5x5: Più Complessità

Con una scacchiera 5x5, il numero iniziale di arrangiamenti cresce rapidamente:

$$\binom{25}{5} = 53,130$$

Applichiamo gli stessi livelli di semplificazione:

Primo livello
Una regina per traversa:

$$5^5 = 3,125$$

Ancora una volta, a questo livello, le regine potrebbero condividere la stessa colonna.

Secondo livello
Filtriamo gli arrangiamenti considerando solo le permutazioni di colonne:

$$5! = 120$$

Terzo livello
Rimuoviamo gli arrangiamenti dove le regine possono attaccare diagonalmente. Per 5x5, ci sono 10 soluzioni valide.

8x8: La Scacchiera Classica

Con la classica scacchiera 8x8, la complessità esplode:

$$\binom{64}{8} \approx 4.4 \text{ miliardi}$$

Applichiamo gli stessi tre livelli:

Primo livello
Una regina per traversa:

$$8^8 = 16,777,216$$

Ancora una volta, le regine potrebbero condividere la stessa colonna.

Secondo livello
Filtriamo usando le permutazioni di colonne:

$$8! = 40,320$$

Terzo livello
Rimuoviamo gli arrangiamenti dove le regine possono attaccare diagonalmente. Il numero finale di soluzioni valide è 92.

È interessante notare che molte di queste soluzioni sono simmetriche, il che significa che possono essere ottenute ruotando o riflettendo la scacchiera. Solitamente, tutti gli arrangiamenti distinti vengono contati, anche se sono simmetrici. Se volessimo contare solo gli arrangiamenti fondamentali (quelli che non possono essere ruotati o riflessi per ottenere un’altra soluzione), per N=8, ce ne sarebbero 12.

Dalla Forza Bruta al Backtracking

Come abbiamo visto, il numero di configurazioni possibili cresce rapidamente all’aumentare di N. Ma come possiamo effettivamente affrontare il problema da una prospettiva algoritmica?

Forza bruta: l’approccio della ricerca esaustiva

Un primo metodo è generare tutti i possibili arrangiamenti di N regine sulla scacchiera e poi filtrare quelli validi, dove nessuna regina attacca un’altra. Questo approccio è facile da capire, ma diventa rapidamente troppo lento anche per valori moderati di N.

per ogni possibile arrangiamento di N regine su una scacchiera NxN:
    se nessuna regina ne attacca un'altra:
        salva la soluzione

Backtracking: l’approccio intelligente

Il backtracking costruisce la soluzione una regina alla volta, traversa per traversa, scartando immediatamente le configurazioni che porterebbero a un conflitto. In questo modo, “potiamo” molte configurazioni inutili e risparmiamo tempo computazionale.

funzione risolvi(riga, colonne_occupate, diagonali1, diagonali2):
    se riga == N:
        salva la soluzione
    altrimenti:
        per ogni colonna da 0 a N-1:
            se colonna non in colonne_occupate
               e (riga + colonna) non in diagonali1
               e (riga - colonna) non in diagonali2:
                aggiungi colonna a colonne_occupate
                aggiungi (riga + colonna) a diagonali1
                aggiungi (riga - colonna) a diagonali2
                risolvi(riga + 1, colonne_occupate, diagonali1, diagonali2)
                rimuovi colonna, (riga + colonna), (riga - colonna)

In questo pseudocodice, colonne_occupate tiene traccia delle colonne già occupate da una regina, mentre diagonali1 e diagonali2 rappresentano le diagonali principali e secondarie già occupate. In questo modo, ogni volta che proviamo a posizionare una nuova regina, controlliamo immediatamente se la posizione è sicura.

La differenza fondamentale tra i due approcci sta nel quando viene controllata la validità di una configurazione.

• La forza bruta genera tutti i possibili arrangiamenti completi di N regine e controlla solo se la soluzione è valida alla fine. Questo significa che spende molto tempo costruendo ed esaminando configurazioni che avrebbero potuto essere scartate molto prima.
• Il backtracking, invece, controlla la validità dell’arrangiamento parziale ad ogni passo, non appena viene posizionata una nuova regina. Se viene trovato un conflitto, l’algoritmo abbandona immediatamente quel percorso e torna indietro, evitando lavoro inutile.

Questa validazione anticipata e la potatura dei percorsi non validi è ciò che rende il backtracking drammaticamente più efficiente della forza bruta, specialmente all’aumentare delle dimensioni della scacchiera.

Conclusione

Il problema delle N-Regine non è solo un divertente gioco di logica o un esercizio di programmazione: è un affascinante viaggio che connette scacchi, algoritmi e strategia.

Pensare in livelli di semplificazione ci aiuta ad affrontare problemi complessi passo dopo passo, mentre implementare il backtracking ci mostra come l’efficienza può emergere anche dalle sfide più semplici.

Divertiti! 🚀♟️

Alberto