Insomma, far convivere otto regine in una scacchiera tipica degli scacchi.
E' un rompicapo affascinante, che ha fatto infatuare diversi matematici, tra cui Gauss.
La regina è il pezzo più potente degli scacchi, perché include le possibilità di movimento di tutti gli altri: può muoversi come una torre (quindi lungo la sua riga e la sua colonna) e come un alfiere (in diagonale).
Provare già a posizionare 4 regine in una 4x4 non è semplice, pensate 8 in una 8x8, o addirittura 16 in una 16x16! In effetti, il rompicapo si estende a un qualsiasi numero N (N regine, in una NxN).
Se provate a risolvere meccanicamente il problema, sicuramente utilizzereste un metodo simile a quello che ho provato a utilizzare io: inizio a posizionare la prima regina nella prima casella, dopodiché la seconda in modo tale che non possa mangiare la prima. Vado avanti, posizionando la terza, e via via fino all'ottava. Quando vedo che non posso più posizionare una regina, torno indietro a quella precedente e vedo dove posso metterla in maniera diversa da come avevo fatto. Vado avanti così, finché non risolvo il problema.
Certo, in una 4x4 questo procedimento non porta via tanto tempo, ma già in una 8x8 dovreste stare minuti a segnarvi le caselle che avete già provato, per non parlare del fatto che noi non siamo macchine, e ci stufiamo in fretta.
Guardate un po' questa animazione che cerca di risolvere il problema così come abbiamo descritto:
Prima o poi, questo procedimento porta sempre a una soluzione.
Invece di provare noi stessi, perché non fare provare a una macchina? In un momento di entusiasmo, ho scritto un programma in Java che cerca la soluzione.
La soluzione adottata è comunque una soluzione molto lenta. Il programma sta in questo momento ancora provando a risolvere il rompicapo 16x16, e non ne ho idea di quando finirà.
Questo programma impiega molto tempo a risolvere il problema proprio perché, anche se non sembra, è un programma piuttosto stupido: infatti prova tutte le soluzioni, tornando indietro quando non sa più che pesci pigliare. Questo lo rende estremamente lento. Si può fare di meglio? Bè, tutte le soluzioni al rompicapo sono note, quindi basterebbe caricarle in un programma e darle in output quando richiesto! Ma questo grazie a qualcheduno che lungo la storia si è messo carta e matita a studiare il problema.
Di questo rompicapo esistono (finora?) 92 soluzioni, ricavabili da 12 di partenza pasticciando un po' con la scacchiera.
Sebbene questo problema possa risultare per certi versi inutile da un punto di vista pratico, uno dei più grandi informatici della storia, Edsger Dijkstra, ha illustrato attraverso questo problema la potenza di una tecnica di programmazione. Ma questa è un'altra storia.
Mentre finivo di scrivere questo post, il programma ha inaspettatamente terminato di risolvere una 16x16:
Nessun commento:
Posta un commento