Il Problema delle Otto Regine

È tempo di Natale, le famiglie si riuniscono e dai cassetti vengono tirate fuori le scatole con i giochi. Giochi elettronici, di ruolo, di carte e, ovviamente, giochi da scacchiera. Fra questi ultimi, gli scacchi sono sicuramente fra quelli che hanno dato vita al maggior numero di rompicapo matematici. Uno dei più celebri è il

Problema delle Regine. Data una scacchiera $n \times n$, qual è il massimo numero di regine che possono essere poste su di essa, in modo tale che nessuna attacchi le rimanenti?

Siccome ogni regina può muoversi in orizzontale, verticale e diagonale, il problema è equivalente a quello di disporre il massimo numero di pedine sulla scacchiera, in maniera tale che non ve ne siano due sulla stessa riga, colonna o diagonale. Da ciò segue che il massimo numero di regine non può superare $n$, e non è difficile dimostrare che su ogni scacchiera di ordine almeno $4$ esiste almeno una soluzione con esattamente $n$ regine.

Molto più difficile è il problema di descrivere tutte le soluzioni o, almeno, un insieme completo di soluzioni a meno di rotazioni e riflessioni (le cosiddette "soluzioni fondamentali"). Per la scacchiera $4 \times 4$ vi è una sola soluzione fondamentale, per quella $5 \times 5$ ve ne sono due, e di nuovo solo una per quella $6 \times 6$. Il numero di soluzioni fondamentali per la scacchiera $7 \times 7$ è sei, quella classica $8 \times 8$ ne possiede dodici, quella $9 \times 9$ quarantasei e quella $10 \times 10$ novantadue.

Il numero totale di soluzioni al variare di $n$ è tabulato nella sequenza OEIS A000170, mentre quello di soluzioni fondamentali è tabulato nella sequenza OEIS A002562. Al momento, non esiste una formula chiusa per il numero di soluzioni in funzione di $n$, tuttavia sono stati pubblicati algoritmi di tipo "bit vector encoding" per produrre tutte le soluzioni [3].

Il problema originale, per la scacchiera 8x8, fu formulato da M. Bezzel nella rivista berlinese Schachzeitung nel 1848, e le $12$ soluzioni fondamentali vennero pubblicate per la prima volta da F. Nauck nella rivista di Lipsia Illustrierte Zeitung (1850). La prima dimostrazione che esse esauriscono tutte le possibilità, basata sulla teoria dei determinanti, fu data da J. W. Glaisher nel 1874. Vi è esattamente una soluzione fondamentale in cui non esistono tre regine allineate, quella indicata col numero (10) in [1].

Le 12 soluzioni fondamentali sulla scacchiera $8 \times 8$ (fonte: Wolfram MathWorld)

Per maggiori notizie sul Problema delle Otto Regine, e sui problemi correlati in cui le regine sono sostituite con altri pezzi degli scacchi, il lettore può consultare [2].

Nota computazionale. Nella pagina Wikipedia [1] si può trovare il seguente script in Pascal per determinare una soluzione al Problema delle Otto Regine:

program eightqueen1(output);
 
var i : integer; q : boolean;
    a : array[ 1 .. 8] of boolean;
    b : array[ 2 .. 16] of boolean;
    c : array[ -7 .. 7] of boolean;
    x : array[ 1 .. 8] of integer;
 
procedure try( i : integer; var q : boolean);
    var j : integer;
    begin 
    j := 0;
    repeat 
        j := j + 1; 
        q := false;
        if a[ j] and b[ i + j] and c[ i - j] then
            begin 
            x[ i    ] := j;
            a[ j    ] := false; 
            b[ i + j] := false; 
            c[ i - j] := false;
            if i < 8 then
                begin
                try( i + 1, q);
                if not q then
                    begin 
                    a[ j] := true; 
                    b[ i + j] := true; 
                    c[ i - j] := true;
                    end
                end 
            else 
                q := true
            end
    until q or (j = 8);
    end;
 
begin
for i :=  1 to  8 do a[ i] := true;
for i :=  2 to 16 do b[ i] := true;
for i := -7 to  7 do c[ i] := true;
try( 1, q);
if q then
    for i := 1 to 8 do write( x[ i]:4);
writeln
end.

Riferimenti.

[1] https://en.wikipedia.org/wiki/Eight_queens_puzzlehttps://en.wikipedia.org/wiki/Eight_queens_puzzle
[2] M. Gardner: Enigmi e giochi matematici, Vol. 4.
[3] Z. Qiu: Bit-vector encoding of $n$-queen problem. ACM SIGPLAN Notices. 37 (2) (2002), 68-70.