Un matematico risponde a un problema di scacchi vecchio di 150 anni

Se hai alcuni set di scacchi a casa, prova il seguente esercizio: Disponi otto regine su una scacchiera in modo che nessuna di esse si attacchi a vicenda. Se ci riesci una volta, riesci a trovare un secondo arrangiamento? Un terzo? Quanti sono lì?

Questa sfida ha più di 150 anni. È la prima versione di una domanda matematica chiamata n-regine problema la cui soluzione Michael Simkin, borsista post-dottorato presso il Center of Mathematical Sciences and Applications dell’Università di Harvard, azzerato su in un articolo pubblicato a luglio. Invece di piazzare otto regine su una scacchiera standard 8 per 8 (dove ci sono 92 diverse configurazioni che funzionano), il problema chiede quanti modi ci sono per piazzare n regine su an n-di-n tavola. Questo potrebbe essere 23 regine su un tabellone 23 per 23, o 1.000 su un tabellone 1.000 per 1.000 o un numero qualsiasi di regine su un tabellone della dimensione corrispondente.

“È molto facile da spiegare a chiunque”, ha detto Erika Roldán, Marie Skłodowska-Curie fellow presso l’Università tecnica di Monaco e il Politecnico federale di Losanna.

Simkin ha dimostrato che per enormi scacchiere con un gran numero di regine, ci sono approssimativamente (0.143n)n configurazioni. Quindi, su un tabellone milione per milione, il numero di modi per disporre 1 milione di regine non minacciose è di circa 1 seguito da circa 5 milioni di zeri.

Il problema originale sulla scacchiera 8 per 8 è apparso per la prima volta in una rivista di scacchi tedesca nel 1848. Nel 1869, il n-il problema delle regine era seguito. Da allora, i matematici hanno prodotto un filo di risultati su n-regine. Sebbene i ricercatori precedenti abbiano utilizzato simulazioni al computer per indovinare il risultato trovato da Simkin, è il primo a dimostrarlo effettivamente.

“Fondamentalmente lo ha fatto molto più acutamente di quanto chiunque altro lo avesse fatto in precedenza”, ha detto Sean Eberhard, borsista post-dottorato presso l’Università di Cambridge.

Una barriera per risolvere il n-queens problema è che non ci sono modi ovvi per semplificarlo. Anche su una tavola relativamente piccola, il numero di potenziali arrangiamenti di regine può essere enorme. Su una scheda più grande, la quantità di calcolo coinvolta è sbalorditiva. In questa situazione, i matematici spesso sperano di trovare qualche schema sottostante, o struttura, che permetta loro di suddividere i calcoli in pezzi più piccoli che siano più facili da gestire. Ma il n-il problema delle regine non sembrava averne.

“Una delle cose che è notevole del problema è che, almeno senza pensarci molto, non sembra esserci alcuna struttura”, ha detto Eberhard.

Ciò deriva dal fatto che non tutti gli spazi sulla scacchiera sono uguali.

Per capire perché, immagina di nuovo di costruire la tua configurazione di otto regine. Se metti la tua prima regina vicino al centro, sarà in grado di attaccare qualsiasi spazio nella sua riga, nella sua colonna o lungo due delle diagonali più lunghe del tabellone. Ciò lascia 27 spazi off-limits per la tua prossima regina. Ma se posizioni invece la tua prima regina lungo il lato del tabellone, minaccia solo 21 spazi, poiché le relative diagonali sono più corte. In altre parole, i quadrati centrali e laterali sono distinti e, di conseguenza, la scacchiera manca di una struttura simmetrica che potrebbe rendere il problema più semplice.

Questa mancanza di struttura è il motivo per cui, quattro anni fa, quando Simkin ha visitato il matematico Zur Luria al Politecnico federale di Zurigo per collaborare al problema, ha inizialmente affrontato il “toroidale” più simmetrico. n– problema delle regine. In questa versione modificata, la scacchiera si “avvolge” su se stessa ai bordi come un toro: se cadi a destra, riappari a sinistra.

Il problema toroidale sembra più semplice a causa della sua simmetria. A differenza della scacchiera classica, tutte le diagonali hanno la stessa lunghezza e ogni regina può attaccare lo stesso numero di spazi: 27.

Simkin e Luria hanno tentato di creare configurazioni sulla scheda toroidale utilizzando una ricetta in due parti. Ad ogni passo, piazzavano una regina a caso, scegliendo qualsiasi spazio con uguale probabilità finché era disponibile. Hanno quindi bloccato tutti gli spazi che poteva attaccare. Tenendo traccia di quante opzioni avevano a ogni passaggio, speravano di calcolare un limite inferiore, un minimo assoluto per il numero di configurazioni. La loro strategia è chiamata algoritmo greedy casuale ed è stata utilizzata per risolvere molti altri problemi nell’area di combinatoria.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *