Per chi non lo sapesse, nel gioco degli scacchi la regina è il pezzo con la maggiore libertà: può spostarsi liberamente in tutti i sensi, in orizzontale, in verticale e in diagonale, per un numero di caselle a piacimento.
Il problema delle 8 regine consiste nel piazzare opportunamente 8 regine all'interno della scacchiera (8x8 caselle) senza che queste si minaccino l'una con l'altra.
In prima analisi potrebbe sembrare sufficiente creare una matrice 8x8 per rappresentare tutte le caselle: questa matrice potremmo popolarla con tutte le possibili combinazioni delle 8 regine sulla scacchiera da 64 caselle per poi analizzare ogni singolo schema.
Questa soluzione però è improponibile in quanto richiederebbe l'analisi di oltre 4 miliardi di combinazioni... gli appassionati di matematica possono dilettarsi a calcolare il numero di combinazioni semplici di n elementi di classe k con n=64 e k=8.
A questo punto si potrebbe pensare di lavorare caricando 8 colonne o 8 righe, in questo caso avremmo 8^8 schemi da analizzare, "solo" 16 milioni.
Risulta chiaro che è necessario ridurre il numero di schemi generati.
Nel codice qui sotto trovate una implementazione in linguaggio C# di un algoritmo che cerca di arrivare ai 92 schemi possibili lavorando sulle permutazioni.
Si parte dal presupposto che le regine devono risiedere tutte su colonne e righe differenti: si tratta quindi di associare ad ogni colonna una riga diversa, ad esempio 78643521 potrebbe indicare che sulla colonna 1 la regina sta sulla riga 7, sulla colonna 2 la regina sta nella riga 8, nella colonna 3 la regina sta sulla riga 6 ecc...
In questo modo si può lavorare su un array anzichè matrice e si dovranno analizzare un totale di 40320 possibili schemi (8!).
Per eseguire il controllo dello schema sarà poi necessario controllare solo le diagonali.
Il programma qui sotto esegue la ricerca utilizzando proprio questo metodo. Le funzioni principali sono:
- Trova_8_regine() e Carica_riga() che si occupano della generazione delle permutazioni;
- Check_8_regine() esegue il test sulle diagonali per verificare lo schema creato;
- Log_soluzione() stampa su file lo schema trovato.
//-----------------------------------------------------------------------------
// Autore: Sebastien Costa
// Data: 02/06/2007
//
// Descrizione: un metodo semplice per la risoluzione del problema delle
// 8 regine
//-----------------------------------------------------------------------------
using System;
using System.IO;
using System.Text;
public class regine {
byte [] colonna = new byte[8];
int n_analizzati;
int n_trovati;
//-------------------------------------------------------------------------
// entry point del programma
//-------------------------------------------------------------------------
public static void Main()
{
Console.WriteLine( "Risoluzione problema delle 8 regine" );
regine r = new regine();
r.Trova_8_regine();
Console.WriteLine( "finito, analizzati " + r.n_analizzati +
" trovati " + r.n_trovati );
}
//-------------------------------------------------------------------------
// funzione principale che ricerca tutti gli schemi
//-------------------------------------------------------------------------
public void Trova_8_regine()
{
byte i;
for ( i = 0; i < 8; i++ )
colonna[ i ] = 0;
Carica_riga( 1 );
}
//-------------------------------------------------------------------------
// funzione che controlla se uno schema è accettabile
//-------------------------------------------------------------------------
public void Check_8_regine()
{
byte i, j;
n_analizzati++;
// l'unico controllo che viene effettuato è che non ci siano 2 regine
// sulla stessa diagonale: lo schema che abbiamo in input, infatti, ci
// garantisce che le regine stanno tutte su colonne e righe diverse
//
// Per il test delle diagonali è necessario testare che per tutte le
// combinazioni di due regine la differenza fra il numero di colonna
// e la differenza del numero di riga non sia uguale in valore
// assoluto
for ( i = 0; i < 8; i++ )
{
for ( j = (byte)(i+1); j < 8; j++ )
{
// se si trovano sulla stessa diagonale
if ( Math.Abs( i - j ) == Math.Abs( colonna[ i ] - colonna[ j ] ) )
return;
}
}
n_trovati++;
Log_Soluzione( n_trovati ); // stampiamo lo schema trovato
}
//-------------------------------------------------------------------------
// funzione ricorsiva
//-------------------------------------------------------------------------
public void Carica_riga(byte riga)
{
byte i;
for ( i = 0; i < 8; i++ ) // ciclo da 0 a 7 per provare tutte le
{ // possibili colonne in cui mettere la regina
if ( colonna[ i ] == 0 ) // se la colonna non è occupata
{
colonna[ i ] = riga; // combiniamo la colonna i-esima con la riga
if ( riga == 7 ) // se stavamo lavorando sull'ultima riga
Check_8_regine(); // testiamo le diagonale
else // altrimenti passiamo alla riga successiva
Carica_riga( (byte)(riga + 1) );
colonna[ i ] = 0; // riazzeriamo la colonna corrente
}
}
}
//-------------------------------------------------------------------------
// stampa
//-------------------------------------------------------------------------
public void Log_Soluzione(int n_sol)
{
int i, j;
try
{
StreamWriter fs;
if (n_sol == 1)
fs = File.CreateText(".\\regine.txt"); // alla prima soluzione ricrea il file
else
fs = File.AppendText(".\\regine.txt"); // dopo appende le soluzioni
// stampa a video la posizione delle 8 regine
fs.WriteLine(" ");
fs.WriteLine("SOLUZIONE #" + n_sol);
fs.WriteLine(" ");
fs.WriteLine(" 1 2 3 4 5 6 7 8 ");
fs.WriteLine(" ---------------------------------");
for (i = 0; i < 8; i++) // cicla sulle 8 righe
{
fs.Write((i + 1) + " |");
for (j = 0; j < 8; j++) // cicla sulle 8 colonne della riga
{
if (colonna[j] == (i + 1))
fs.Write(" # |");
else
fs.Write(" |");
}
fs.WriteLine(" ");
fs.WriteLine(" ---------------------------------");
}
fs.Close();
}
catch (Exception e)
{
Console.WriteLine("Error opening file");
}
}
}
