Problema delle N regine

Lista di variabili booleane

2 variabili: x1,x2

Come si esprime che esattamente una delle 2 variabili è vera:
(x1⇒¬x2)∧(¬x1⇒x2)

Come si esprime che al massimo una delle 2 variabili è vera:
(x1⇒¬x2)

3 variabili: x1,x2,x3

Come si esprime che esattamente una delle 3 variabili è vera:
(x1->(¬x2∧¬x3))∧(¬x1⇒(x2⇒¬x3)∧(¬x2⇒x3))

Come si esprime che al massimo una delle 3 variabili è vera:
(x1->(¬x2∧¬x3))∧(¬x1⇒(x2⇒¬x3))

4 variabili: x1,x2,x3,x4

Come si esprime che esattamente una delle 4 variabili è vera:
(x1->(¬x2∧¬x3∧¬x4))∧(¬x1⇒(x2->(¬x3∧¬x4))∧(¬x2⇒(x3⇒¬x4)∧(¬x3⇒x4)))

Come si esprime che al massimo una delle 4 variabili è vera:
(x1->(¬x2∧¬x3∧¬x4))∧(¬x1⇒(x2->(¬x3∧¬x4))∧(¬x2⇒(x3⇒¬x4)))

N variabili: x1,x2,...,xn

Come si esprime che esattamente una delle n variabili è vera:
(x1->(¬x2∧..∧¬xn))∧(¬x1⇒...))

Come si esprime che al massimo una delle n variabili è vera:
(x1->(¬x2∧..∧¬xn))∧(¬x1⇒...))

Esercizi

B1 Scrivere una funzione exactly_one che prende una variabile iniziale i, un incremento j ed un numero n e restituisce la formula booleana che esprime che esattamente una delle variabili x(i), x(i+j),...,x(i+(n-1)*j) è vera.
B2 Scrivere una funzione at_most_one che prende una variabile iniziale i, un incremento j e un numero n e restituisce la formula booleana che esprime che al massimo una delle variabili x(i), x(i+j),...,x(i+(n-1)*j) è vera.

Problema delle N regine

Si possono mettere N regine su una scacchiera NxN in modo tale che nessuna regina sia in contatto con un'altra:

scacchiera

Formalizzazione

Ogni variabile corrisponde ad una casella. Se la variabile ha valore vero, ciò denota che c'è una regina dentro la casella.

Ex: N=3

sacchetiera
Esattamente una regina per riga:

((x0⇒(¬x1∧¬x2))∧(¬x0⇒((x1⇒¬x2)∧(¬x1⇒x2)))) ∧
((x3⇒(¬x4∧¬x5))∧(¬x3⇒((x4⇒¬x5)∧(¬x4⇒x5)))) ∧
((x6⇒(¬x7∧¬x8))∧(¬x6⇒((x7⇒¬x8)∧(¬x7⇒x8)))) ∧

Esattamente una regina per colonna:

((x0⇒(¬x3∧¬x6))∧(¬x0⇒((x3⇒¬x6)∧(¬x3⇒x6)))) ∧
((x1⇒(¬x4∧¬x7))∧(¬x1⇒((x4⇒¬x7)∧(¬x4⇒x7)))) ∧
((x2⇒(¬x5∧¬x8))∧(¬x2⇒((x5⇒¬x8)∧(¬x5⇒x8)))) ∧

Al massimo una regina per diagonale:

((x0⇒(¬x4∧¬x8))∧(¬x0⇒(x4⇒¬x8))) ∧
(x1⇒¬x5) ∧
(x3⇒¬x7) ∧
((x2⇒(¬x4∧¬x6))∧(¬x2⇒(x4⇒¬x6))) ∧
(x1⇒¬x3) ∧
(x5⇒¬x7)

La formula risultante non è soddisfacibile: il problema non ha soluzione (non si può mettere 3 regine in una scacchiera 3x3).

Esercizi

B3 Scrivere una funzione chessboard che prende la dimensione n e restituisce la formula corrispondente al problema delle n regine.

Soddisfacibilità

Per la dimensione N, ci sono 2^(N*N) valutazioni possibili delle variabili. Dunque usare la tabella di verità per decidere se il problema è soddisfacibile è troppo costoso. Si può fare solo fino a N=5. Bisogna trovare qualcosa di meglio...


Laurent Théry

Last modified: Tue Apr 30 01:38:21 MEST 2002