Il rompicapo delle otto regine
Si narra che in tempi lontani e imprecisati la confederazione scacco-monarchica di Biancolandia fosse un paese florido e dotato di una potenza militare impressionante.
L’unica potenza in grado di vantare una ricchezza e un esercito di pari grandezza era quella dei loro vicini di Nerolandia.
La secolare guerra tra questi due paesi, ricca di catture, arrocchi e follia, è molto nota anche a chi non è mai stato in quelle terre.
Quelle che sono meno note sono le difficoltà interne che la struttura di una confederazione scacco-monarchica porta con sé.
Per ognuno dei piccoli sottoregni di cui la confederazione era composta esistevano una regina e un re che possedevano pieni poteri.
Ogni monarca aveva gli stessi poteri di qualsiasi altro suo collega di un altro sottoregno. Capite bene che questo generava tensioni e frizioni incredibili tra monarchi che non si stavano troppo simpatici.
Ma Biancolandia non poteva permettersi nessuna debolezza interna, la guerra contro Nerolandia doveva assorbire la totalità di tutti gli sforzi della confederazione.
Fu così che venne riunito il grande consiglio degli Equini, composto dalle creature più sagge e intelligenti della confederazione, che taluni chiamano Cavalli e altri chiamano Houyhnhnm.
Nella loro riunione decisero che la scelta migliore sarebbe stata fare in modo di redistribuire i monarchi su Biancolandia in maniera intelligente, in modo che le rispettive sfere di influenza non si intersecassero. Così i problemi sarebbero stati risolti alla radice.
L’unica cosa che restava da fare era trovare questo modo intelligente di posizionare i sottoregni.
Il rompicapo
La prima formulazione del rompicapo delle otto regine si deve allo scacchista tedesco Max Bezzel nell’11.848 EU (1848 d.C.).
La sua formulazione è molto semplice, non bisogna saper giocare a scacchi per comprendere e cimentarsi nel problema.
Tutto quello che occorre sapere è:
- Una scacchiera è un quadrato di 8×8 caselle.
Su ognuna delle 64 caselle è possibile posizionare al più una pedina regina. - Posizionare una regina su una casella determina le caselle che sono minacciate dalla sua “sfera di influenza”.
Queste sono tutte le caselle raggiungibili tramite una linea orizzontale, verticale o diagonale dalla casella di posizionamento, senza restrizioni di distanza (Come da Figura 1).
È possibile posizionare otto regine su una scacchiera in modo tale che nessuna regina sia su una casella minacciata da un’altra regina?
Quante soluzioni ci sono?
La risposta secca al rompicapo è:
Sì, è possibile posizionare otto regine in modo che i vincoli siano rispettati.
Per averne la sicurezza matematica basta esibire una soluzione, ad esempio quella di Figura 2.
Da cui venne posta la classica domanda che si pone in questo tipo di problemi: Quante sono?
Volete provare a buttarvi?
La risposta venne data nell’11.850 EU (1850 d.C.) da Franz Nauck, che dimostrò che esistono esattamente 92 soluzioni al rompicapo delle otto regine.
Ora, data una soluzione è possibile ruotare o riflettere la scacchiera con la soluzione per ottenerne un’altra.
Si tende quindi a distinguere come soluzioni fondamentali quelle soluzioni che non sono ottenibili l’una dall’altra tramite riflessioni o rotazioni.
In questo modo, delle 92 soluzioni individuate da Franz Nauck il numero delle soluzioni fondamentali è 12. (Una lista di tutte queste soluzioni fondamentali è scaricabile da [2])
Il rompicapo delle N regine
Franz Nauck, una volta risolto il rompicapo, fu preso dalla fissazione di tutti i matematici: generalizzare i problemi.
Se il problema originale chiedeva di posizionare 8 regine su una scacchiera 8×8, la sua naturale generalizzazione è quella di chiedere di posizionare N regine su una scacchiera NxN in modo che nessuna sia minacciata da altre.
Se N=1, allora la nostra scacchiera ha solo una casella.
Quindi è possibile posizionare una regina in un sol modo dove non viene minacciata da nessuno.
Se invece N=2, allora la scacchiera ha quattro caselle. Posizionando una regina questa minaccerà sempre tutte le altre caselle, non consentendo di posizionare la seconda e quindi di trovare alcuna soluzione.
Se le cose vi sembrano non così complicate, pensate che per N=10 il numero di soluzioni è 724 (di cui 92 fondamentali), mentre per N=20 il numero di soluzioni è 39.029.188.884 (di cui 4.878.666.808 fondamentali).
Il problema di sapere il numero di soluzioni al rompicapo delle N regine, con N generico, è ad oggi ancora insoluto.
Fonti
[1]: Eight queens puzzle – Wikipedia [eng]
[2]: All solutions to the problem of eight queens – The On-Line Encyclopedia of Integer Sequences [eng]
Matematico, ricercatore e sbadato professionista.
Non chiedetegli di fare i conti al ristorante, non è capace: vi ritroverete a dover pagare quantità immaginarie ed essere costretti a lavare i piatti per qualche settimana.
