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. 

Il porisma di Steiner

In geometria, il termine porisma viene spesso utilizzato per indicare una configurazione di oggetti che in generale non esiste e che tuttavia, non appena esiste, esiste in un’infinità di casi.  Uno dei porismi più famosi è quello che prende il nome dal matematico svizzero  J. Steiner (1796-1863), e che riguarda catene di circonferenze tangenti fra loro e a due circonferenze date. L’enunciato preciso è il seguente:

Porisma di Steiner. Siano $A$ e $B$ due circonferenze disgiunte nel piano, con $A$ interna a $B$. Supponiamo  che esista una catena di circonferenze $C_1, \ldots, C_n$, aventi le seguenti proprietà:

1. Ogni circonferenza $C_i$ è tangente alla precedente e alla successiva, e inoltre $C_n$ è tangente a $C_1$ (in altre parole, la catena è chiusa); 
2. Ogni $C_i$ è tangente sia ad $A$ che a $B$. 

Allora esistono infinite catene siffatte, tutte ottenibili da una fissata per mezzo di rotazioni. Inoltre, ogni circonferenza $C$, tangente sia ad $A$ che a $B$, è membro di una tale catena.

Una catena di circonferenza che verifica i punti (1) e (2) sopra è detta catena (chiusa) di Steiner. Dunque il Porisma di Steiner può essere anche enunciato dicendo che, se $A$ e $B$ ammettono una catena di Steiner formata da $n$ elementi, allora ne ammettono infinite.

Catene di Steiner (fonte Wikipedia)

Una bella dimostrazioni di questo sorprendente risultato è contenuta nel Capitolo 6 del libro di H. S. M. Coxeter [C89]. L’idea è quella di considerare una particolare inversione del piano, che trasformi le due circonferenze $A$ e $B$ in due circonferenze concentriche $A’$, $B’$. Siccome una tale inversione manda circonferenze tangenti in circonferenze tangenti, è ora sufficiente dimostrare l’enunciato per  $A’$, $B’$, nel qual caso è ovvio.

Si noti che questo argomento permette anche di dedurre che i punti di tangenza delle circonferenze della catena giacciono a loro volta su una circonferenza. Inoltre, un semplice calcolo mostra che i centri delle circonferenze della catena giacciono su un’ellisse, avente per fuochi i centri di $A$ e $B$.

Nel caso degenere in cui le circonferenze $A$, $B$ sono tangenti internamente in un punto $p$, è possibile considerare una particolare inversione che manda $p$ all’infinito, trasformando $A$ e $B$ in due rette parallele. La stessa dimostrazione di prima mostra che in tal caso esistono infinite catene di Steiner per $A$ e $B$, ciascuna delle quali formata a sua volta da un numero infinito di circonferenze (il cui raggio tende a zero man mano che esse si avvicinano a $p$). Questa situazione è trattata in dettaglio nel Capitolo 3 di [N97].

Riferimenti.

[C89] H. S. M. Coxeter: Introduction to Geometry, 2nd edition, Wiley and Sons 1989
[N97]  T. Needham: Visual Complex Analysis, Clarendon Press 1997.