Il rompicapo delle otto regine
Il rompicapo delle otto regine chiede di posizionare otto regine su una scacchiera senza che due di esse si attacchino. Il compositore di problemi di scacchi Max Bezzel lo pubblicò nel 1848, ed è diventato il classico primo esempio di ricerca con backtracking.
Un rompicapo di scacchi del 1848
Max Bezzel, compositore tedesco di problemi di scacchi, propose il rompicapo in una rivista di scacchi di Berlino nel 1848. Franz Nauck pubblicò tutte le 92 soluzioni nel 1850 e pose la stessa domanda per scacchiere più grandi. Carl Friedrich Gauss seguì il rompicapo con interesse e ne parlò nelle sue lettere.
Una regina per riga e per colonna
Otto regine che non si attaccano devono stare su otto righe diverse e otto colonne diverse. Quindi una soluzione è un rimescolamento dei numeri da 1 a 8, una permutazione, con una regola in più: due regine non possono condividere una diagonale. Delle 40.320 permutazioni, solo 92 superano la prova.
Il backtracking
Il backtracking costruisce una soluzione un pezzo alla volta e torna indietro appena finisce in un vicolo cieco. Per le regine: metti una regina sulla prima casella sicura della riga successiva e, quando una riga non ha caselle sicure, torna alla riga sopra e sposta più avanti quella regina. Nel 1972 Edsger Dijkstra usò il rompicapo per spiegare la programmazione strutturata proprio con questa ricerca.
Simmetria
Ruota la scacchiera di un quarto di giro, o riflettila, e una soluzione resta una soluzione. Questo dà fino a otto versioni di ciascuna. Le 92 soluzioni si raggruppano in 12 famiglie di questo tipo: undici con 8 membri e una con solo 4, perché quella soluzione resta uguale dopo mezzo giro.
Il problema delle n regine
Su una scacchiera n×n la domanda è la stessa con n regine. Ci sono soluzioni per ogni n da 4 in su, e il loro numero cresce in fretta: 2 per 4×4, 92 per 8×8 e 14.200 per 12×12. Non si conosce una formula per il conteggio; i valori record vengono da grandi ricerche al computer.
Prova in PictorX
Apri Otto regine e fai clic su una casella per posizionare una regina; fai di nuovo clic per toglierla. «Mostra attacchi» segna con un punto le caselle che le tue regine attaccano, e le regine in rosso si attaccano a vicenda. Risolvi esegue la ricerca con backtracking un passo alla volta e mantiene le regine che hai posizionato. Soluzione successiva scorre tutte le soluzioni in ordine, e Dimensione cambia la scacchiera da 4×4 a 12×12.
Domande frequenti
Chi ha inventato il rompicapo delle otto regine?
Max Bezzel, compositore tedesco di problemi di scacchi, nel 1848. Franz Nauck pubblicò il primo elenco completo delle soluzioni nel 1850.
Quante soluzioni ci sono?
92 sulla scacchiera standard. Contando rotazioni e riflessioni come una sola, sono 12.
Perché la scacchiera 6×6 ha così poche soluzioni?
Ne ha solo 4, tutte di un’unica famiglia. La scacchiera 5×5, più piccola, ne ha 10. Le scacchiere più grandi ne hanno sempre di più: 40 sulla 7×7 e 92 sulla 8×8.
PictorX carica qualcosa?
No. La scacchiera è disegnata su una tela nel browser. Salva scarica un PNG, e Modifica apre quell’immagine nell’editor di PictorX.
Strumenti correlati
Otto regine
Posiziona otto regine su una scacchiera in modo che nessuna ne attacchi un’altra. Prova tu stesso, guarda la ricerca con backtracking trovare una soluzione passo dopo passo e scorri tutte le 92 soluzioni.
Giro del cavallo
Fai saltare un cavallo degli scacchi su ogni casella della scacchiera esattamente una volta. Gioca da solo con i suggerimenti di Warnsdorff, oppure guarda Risolvi completare un giro aperto o chiuso. Salva il percorso come PNG.
Il giro del cavallo
La storia e la matematica del giro del cavallo: Euler e Warnsdorff, giri aperti e chiusi, perché le scacchiere di lato dispari non hanno un giro chiuso e come un computer ne trova uno.
Torre di Hanoi
Sposta una torre di dischi su tre pioli nel browser. Un disco alla volta, mai uno più grande su uno più piccolo. La soluzione più breve è di 2ⁿ − 1 mosse.
Torre di Hanoi
La Torre di Hanoi: tre pioli, un disco alla volta e mai uno più grande su uno più piccolo. La soluzione più breve è di 2ⁿ−1 mosse. Édouard Lucas presentò il rompicapo nel 1883.
Formica di Langton
Avvia la formica di Langton nel browser. Osserva simmetria, caos e l’autostrada di 104 passi, poi prova regole multicolore, più formiche, una griglia esagonale e i turmiti.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Prova Otto regine