Otto Regine - PerGioco.net

Il problema delle otto regine è uno dei più celebri rompicapo matematici ispirati agli Scacchi. Consiste nel collocare otto regine su una scacchiera 8 × 8 in modo che nessuna possa attaccarne un’altra lungo una riga, una colonna o una diagonale. La regina, infatti, può muoversi liberamente lungo tutte queste linee.

Il problema viene proposto nel 1848 dal compositore di problemi scacchistici tedesco Max Bezzel. Nel 1850 Franz Nauck pubblica alcune delle prime soluzioni conosciute ed estende la domanda alle scacchiere di dimensione arbitraria: nasce così il problema delle n regine, che chiede di collocare n regine su una scacchiera n × n senza che due di esse si trovino sulla stessa riga, colonna o diagonale.

Per la scacchiera tradizionale esistono 92 soluzioni. Il numero comprende anche le configurazioni ottenute ruotando o riflettendo una stessa disposizione. Considerando equivalenti quelle legate da queste simmetrie, le soluzioni fondamentali sono invece 12. Undici di esse generano otto disposizioni differenti, mentre una, dotata di una particolare simmetria, ne genera soltanto quattro.

Il problema può essere affrontato anche in termini combinatori. In ogni soluzione deve esserci esattamente una regina per ogni riga e per ogni colonna; è quindi possibile rappresentare una disposizione attraverso una permutazione delle otto colonne. Le possibili permutazioni sono 40.320, ma soltanto 92 rispettano anche il vincolo delle diagonali.

La ricerca delle soluzioni può essere organizzata sistematicamente collocando una regina alla volta e abbandonando una disposizione non appena questa non può più essere completata. Questo procedimento, noto come backtracking o ricerca con ritorno indietro, viene utilizzato nel 1972 da Edsger Dijkstra come esempio di programmazione strutturata e contribuisce a fare delle otto regine un classico dell'informatica. Nella versione generalizzata, il problema ammette soluzioni per n = 1 e per ogni n ≥ 4, mentre non ne ammette per n = 2 e n = 3. Il numero delle soluzioni cresce rapidamente: 2 per n = 4, 10 per n = 5, 4 per n = 6, 40 per n = 7 e 92 per n = 8.

La semplicità delle regole favorisce anche la trasformazione del problema in rompicapi commerciali. Tra questi figura l'Octo Puzzle, prodotto dalla Parker Brothers di Salem, nel Massachusetts, intorno al 1900. Il giocatore deve collocare otto pedine su una scacchiera 8 × 8 in modo che nessuna possa attaccarne un'altra lungo una riga, una colonna o una diagonale. La confezione riporta lo slogan: “It is HARD to do, But CAN be done”.

Un altro esempio è l'N & F Puzzle, brevettato nel 1886 da A. W. Butterworth e commercializzato da Nichols & Frost. In questo caso si devono collocare sei pioli su una scacchiera 6 × 6 rispettando lo stesso principio. Un'ulteriore testimonianza è il Jeu des Manifestants, prodotto da Jeux et Jouets Français intorno al 1900, nel quale otto carte devono essere disposte in modo da rispettare i vincoli di righe, colonne e diagonali.

I tre rompicapo sono descritti da Jerry Slocum e Jack Botermans nel volume Puzzles Old and New: How to Make and Solve Them, pubblicato nel 1986. Dimostrano come il problema delle otto regine, nato come problema matematico e scacchistico, possa essere trasformato in oggetti ludici diversi, mantenendo invariata la sua struttura fondamentale.

Il problema delle otto regine rappresenta così un punto d'incontro fra Scacchi, matematica ricreativa, combinatoria e informatica, e continua a essere uno dei più noti problemi di disposizione.