Cosa succede quando ci sono più regine a voler controllare una scacchiera? I problemi di dominazione ce lo dicono in termini matematici
La storia e la politica ci insegnano che, quando ci sono più persone a contendersi una posizione di potere, sorgono inevitabilmente problemi. Un esempio è stato quello di due regine, la protestante Elisabetta I, regina d’Inghilterra, e la cattolica Maria Stuarda, regina di Scozia. A Maria spettava per diritto di nascita il trono inglese, essendo Elisabetta considerata figlia illegittima di Enrico VIII. La contesa fu motivo di vari scontri tra cattolici e protestanti nel panorama britannico del XVI secolo e si risolse, purtroppo, a sfavore di Maria che fu decapitata nel 1587.
Ci sono però altri casi in cui la presenza di più sovrane non deve per forza dar vita a eventi sanguinari. Questo accade quando le regine sono quella bianca e quella nera che, insieme agli altri pezzi, si danno battaglia per il controllo della scacchiera. Se nella recente serie Netflix c’è una sola “Regina degli scacchi”, Beth Harmon, giovane geniale che tiene testa ai più grandi maestri di scacchi del pianeta, cosa succederebbe se, invece, ce ne fossero addirittura più di due? A questo proposito, esiste una classe di problemi, detti “problemi di dominazione”, che fanno parte di un’ampia collezione di quesiti matematici legati al movimento di pezzi sulla scacchiera.
I primi esempi di tali problemi risalgono al Cinquecento, qualche decennio prima delle vicende di Maria ed Elisabetta. Una formulazione classica è questa: qual è il numero minimo di regine da posizionare su una scacchiera di dimensioni n x n affinché ogni altra casella sia sotto attacco da almeno una di esse?
Problemi del genere interessano in modo particolare i matematici perché rappresentano un modo di applicare la teoria dei grafi. Un grafo è un oggetto matematico costituito da vertici che possono essere collegati tra loro in vari modi. Nel caso dei problemi di dominazione delle regine, la scacchiera è vista come un grafo, detto Qn, e le caselle sono i vertici. Due vertici si dicono adiacenti se uno dei due è occupato da una regina e l’altro è sotto scacco da questa, cioè è una casella che si trova sulla stessa riga, colonna o diagonale della regina.
Allora, tra tutti i vertici di Qn, si considera l’insieme di quelli occupati da regine (D). L’insieme D è detto “dominante” se ogni altro vertice di Qn è adiacente ad almeno un elemento di D. Quindi il problema di dominazione consiste nel trovare la minima cardinalità (numero di elementi) dell’insieme D, indicata con g(Qn ). Questo numero è detto, appunto, “numero di dominazione”.
Due possibili insiemi dominanti su una scacchiera di dimensione 8×8, in questo caso g(Q8 )=5
La versione pacifica del problema è quella per cui le regine non possono attaccarsi tra di loro. In questo caso si parla di “dominazione indipendente” se gli elementi di D non sono adiacenti tra loro e la sua cardinalità si indica con i(Qn).
Determinare questi numeri rappresenta una sfida che cresce con l’aumentare delle dimensioni della scacchiera. Si conoscono, infatti, i valori di g(Qn ) per n<14 e di i(Qn) per n<13. I successivi risultati hanno permesso di trovare solo dei limiti inferiori o superiori ed è stato ipotizzato che, per n sufficientemente grande, g(Qn )= i(Qn ).
Come si può facilmente immaginare, il problema può essere formulato usando altri pezzi, in particolare per gli alfieri, le torri e i re.
Considerando per primi gli alfieri, una curiosità su questi è che il loro nome deriva dall’antica versione arabo-persiana del gioco, “al fil” significa “l’elefante” e, infatti, il pezzo che muoveva in diagonale aveva le sembianze di questo animale. In inglese, invece, il pezzo è chiamato “bishop”, vescovo. In questo caso il grafo si indica Bn e l’insieme dominante si costruisce ponendo tutti i pezzi sulla colonna più vicina al centro della scacchiera, quindi g(Bn)=n.
Per quanto riguarda i re, il grafo si indica con Kn e la configurazione dominante si ottiene ponendo i pezzi a una distanza di due caselle uno dall’altro. Il numero di dominazione g(Kn) è la parte intera del quadrato di (n+2)/3. Infine, per le torri, il grafo è Rn e la minima dominazione si ha sistemando tutte le torri lungo la prima fila di caselle, per cui g(Rn)=n.
Gli insiemi dominanti per B6, K6 e R6 .
Anche se questi risultati sono abbastanza intuitivi, la parte che si solito diverte i matematici è trovare il modo per dimostrarli. Far vedere, cioè, che il numero di dominazione giusto è esattamente quello e non può essere nessun altro. Chissà se l’imbattibile Beth Harmon sarebbe riuscita a risolvere anche un problema del genere…
Per saperne di più:
K.S.P. Sowndarya, Y. Lakshmi Naidu, Perfect Domination for Bishops, Kings and Rooks Graphs On Square Chessboard, Annals of Pure and Applied Mathematics, 18, 59-64 (2018)
E.J. Cockaine, Chessboard domination problems, Discrete Mathematics, 86, 13-20, (1990)
Immagine di copertina: Battle of chess queens via Shutterstock