Come funziona 8 Queens

A seconda dei circoli in cui ti trovi - diciamo, il tuo migliore amico è un programmatore di computer e tua sorella è un prodigio degli scacchi - potresti già avere familiarità con il puzzle delle 8 regine. Per il resto di noi, il puzzle delle 8 regine (o problema o semplicemente "8 regine") probabilmente non è qualcosa a cui passiamo molto tempo a pensare.

Il puzzle è abbastanza semplice. Come puoi posizionare 8 regine su una scacchiera in modo che nessuna si attacchi a vicenda? In alternativa, la domanda a volte viene formulata come "Qual è il numero massimo di regine che possono essere piazzate su una scacchiera, in modo che due non possano attaccarsi a vicenda", ma questo enigma diventa molto meno difficile quando lo cerchi su Google , e il termine "Il puzzle delle 8 regine" viene fuori.

Potresti chiederti perché mai sulla Terra a qualcuno importa dove tieni le tue otto regine. E sì, superficialmente, è solo un puzzle strategico. Ma (ed è qui che è utile avere un migliore amico che codifica i computer) il puzzle delle 8 regine è un ottimo modo per testare l'esperienza e l'alfabetizzazione di un programmatore.

Ora, non aver paura. Non sarai costretto a comprendere le complessità della programmazione del computer per continuare a leggere. Ma dovresti sapere che la soluzione del puzzle può essere ottenuta utilizzando un codice di programmazione - e alcuni sono più eleganti di altri. Ad esempio, puoi sicuramente trovare la soluzione utilizzando un programma di "forza bruta" che potrebbe semplicemente passare attraverso ogni possibile posizionamento, escludendone uno alla volta. Ma un programmatore sofisticato sarà in grado di costruire un programma con scorciatoie utilizzando un algoritmo più raffinato per trovarti una soluzione più velocemente. Essere in grado di trovare modi insoliti o originali per programmare una soluzione a un problema ampio quanto 8 regine può essere un ottimo test per l'esperienza di uno scrittore di codici.

Quindi, anche se non ti infileremo 1 e 0 per spiegare come funziona 8 Queens, ti forniremo alcune soluzioni al puzzle.

Ora che abbiamo la premessa di base del puzzle, dovremmo stabilire perché il problema è così unico. Per farlo, rispolveriamo le nostre basi di scacchi. In una partita a scacchi, la regina è una forza da non sottovalutare. Può muoversi in linea retta verticalmente, orizzontalmente o diagonalmente, quanti spazi vuole. L'unico problema è che non può saltare pezzi, quindi se una pedina è sulla sua strada, deve catturarla e fermarsi.

Questo è ciò che rende interessante il puzzle delle 8 regine. Se le regine possono muoversi in alto, in basso, a sinistra, a destra e in diagonale, quante reali in guerra possono occupare il tabellone senza condividere la stessa riga, colonna o linea diagonale? Ora, potresti pensare che sarebbe un'idea formidabile mettere una regina sul board, provando diverse combinazioni prima di centrarle tutte. E certo, è possibile. Ma ci sono 4.426.165.368 potenziali soluzioni, quindi potresti considerare di trovare una scorciatoia.

Prima di mettere le nostre regine in 4 miliardi di quadrati diversi, riconosciamo che qualcuno si è effettivamente seduto un giorno e ha deciso che questo sarebbe stato un buon modo per sprecare un pomeriggio o due. Com'era prevedibile, non era qualcuno che aveva le repliche di "My Big Fat Gypsy Wedding" su cui aggiornarsi: era un maestro di scacchi e compositore tedesco del 19° secolo di nome Max Bezzel. (Un compositore di scacchi è qualcuno che inventa problemi di scacchi, noti anche come enigmi, da risolvere.) È apparso per la prima volta nella rivista tedesca di scacchi DieSchachzeitung nel 1848.

Bezzel non era così interessato a risolvere l'enigma; era soddisfatto di porre semplicemente la domanda. Tuttavia, nel 1850, il matematico Franz Nauck scrisse un altro articolo che discuteva il problema. (Le prime soluzioni al puzzle furono infine risolte da Nauck.) Ciò attirò l'attenzione di Karl Gauss, un matematico del 19° secolo noto per aver scoperto la teoria fondamentale dell'algebra. Quando Gauss si interessò a trovare la soluzione, altri lo seguirono e iniziarono ad emergere approcci diversi per risolvere il puzzle.

Non sorprende che "otto" sia la risposta alla nostra domanda specifica su quante regine possono essere piazzate su un board senza attaccarsi a vicenda. Ma esploriamo in quanti modi possono essere piazzate otto regine e come viene stabilito.

Abbiamo parlato di come i programmi per computer di forza bruta siano un modo per risolvere il puzzle - e testare manualmente 4.426.165.368 possibilità si qualificherebbe sicuramente come forza bruta - ma ci sono modi più semplici per restringere le soluzioni. Un metodo semplificato fu fornito quando JWL Glaisher, un altro matematico, pubblicò un articolo nel 1874 descrivendo il suo uso dei determinanti per trovare una soluzione. "Determinants" suona un po' difficile, ma tutto quello che devi sapere è che Glaisher ha costruito fondamentalmente una matrice e, usando un sistema che ha derivato da quella matrice, è stato in grado di restringere le possibili soluzioni a 92.

E 92 soluzioni rimane. Ma non lasciarti ingannare; non sarai in grado di allineare 92 scacchiere, ciascuna con un unico set di 8 regine sistemate pacificamente, perché in realtà ci sono solo 12 soluzioni uniche.

Confuso? La differenza tra 12 soluzioni uniche e 92 soluzioni fondamentali si basa, letteralmente, su come la guardi. Sebbene tu possa impostare 12 tavole diverse in modo distintivo con le tue otto regine, tutto ciò che serve è semplicemente girare la tavola - o addirittura rifletterla su uno specchio - per far sembrare le tavole tecnicamente diverse e quindi avere un "diverso" soluzione. (Questo è chiamato operazioni di simmetria rotazionale e riflessiva.) Quindi prendi le tue 12 schede uniche, le giri di 90, 180 e 270 gradi e poi le rifletti ad ogni rotazione. Ma un'altra cosa: una tavola unica è simmetrica, quindi sembra la stessa da due angolazioni. Mentre tutte le altre schede hanno otto varianti, la scheda simmetrica ne ha solo quattro. Quindi, invece di 12 schede per 8 variazioni (96), stiamo effettivamente sottraendo le quattro che non esistono con la scheda simmetrica. Cosa otteniamo? 92 soluzioni fondamentali.

Ora, non lasciarti ingannare dalla matematica. Puoi sempre trovarti una scacchiera e tentare di scovare alcuni posizionamenti per te stesso. (Trovare una risposta, ovviamente, è molto più facile che trovarne tutte e 12.) E ci sono anche programmi sul Web che ti permettono di scoprire alcune soluzioni diverse. (Attenzione: potrebbero farti sentire stupido.)

Prima di mescolare le tue regine, controlla la pagina successiva per ulteriori informazioni.

Essendo una persona meno interessata a un algoritmo che a un alfabeto, non avevo grandi speranze per la comprensione del puzzle delle 8 regine. Sebbene fossi sicuro che avesse una sorta di applicazione pratica, non sono stato in grado di vederlo. Ironia della sorte, è stato quando ho capito la vastità del problema che ho iniziato a capire perché poteva essere utile. Trovare un insieme di soluzioni da un'enorme quantità di possibilità è uno dei motivi per cui esiste un codice. Il problema delle 8 regine sfida programmatori e matematici a scoprire nuove tecniche per semplificare la ricerca.

Link correlati

Fonti