Quadrati sudoku e polinomi cromatici

G

0

(G , C) (G, C)

colorato completo di alcuni vertici. Diremo che è un sottografo di se è ottenuto contraendo

C G'

qualche bordo di G con al più un punto nale in . In questo modo otteniamo un insieme parzialmente ordinato.

C

La contrazione minima sarebbero i vertici di esclusi gli adiacenti. Useremo la lettera per indicare il grafo

C C

0

(G , C) p (λ)

minimo nel nostro . Per ogni sottografo di questo , sia il numero minimo di modi per

poset poset 0

G ,C

λ q (λ)

colorare completamente con colori tra quelli specicati per . Sia il numero di modi per colorare

G' C 0

G ,C

λ

(non necessariamente in modo completo) i vertici di ' usando colori tra quelli specicati per . Chiaramente

G C

0 −t 0

v ≥

q (λ) = λ v t λ d

, dove è il numero di vertici di e è il numero dei vertici di . Se , allora, dato

G' C

0

G ,C 0

0

−

λ colorato (G, C) (G , C)

un di , possiamo derivare un colorato completo di un unico sottografo semplicemente

(G, C)

contraendo i bordi, ogni volta che due vertici adiacenti di hanno lo stesso colore assegnato. In questo modo

otteniamo la relazione P

v−t

q (λ) = λ = p (λ)

0

G,C G C

0

≤

C G

Dalla relazione inversa del Teorema di Möbius, deduciamo che

P 0

0 −t

v

p (λ) = µ(C, G )λ

G,C 0

≤

C G

dove il secondo membro è proprio un polinomio a una variabile a coecienti interi di grado , come enunciato dal

v-t

teorema. °

Possiamo anche dimostrare il Teorema n 1 senza l'uso delle funzioni di Möbius. Applichiamo il principio di

(G, C)

induzione sui numeri dei bordi del grafo . Consideriamo tre casi:

(1) Supponiamo che sia un bordo che unisce due vertici di , con al più uno contenuto in C. Useremo la

e G

−

G e

seguente notazione che denoterà il grafo ottenuto da eliminando il bordo , ma non i suoi punti nali. Il

G e

grafo ottenuto da , identicante i due vertici uniti da (e rimuovendo ogni bordo multiplo) sarà denotato con

G e

G/e

. Con questa notazione, abbiamo: −

p (λ) = p (λ) p (λ)

G,C G−e,C G/e,C − −

G e G e

perché ogni colorato completo di è anche un colorato completo di e un colorato completo di genera

G

un colorato completo di se e solo se assegna colori distinti ai punti nali , di . Perciò il numero di colorati

G x y e

p (λ) p (λ)

completi può essere ottenuto da sottraendo quelle colorazioni che assegnano lo stesso colore sia

G,C G−e,C

p (λ)

a che a , e questo numero corrisponde a . Ogni e hanno meno bordi di G. Perciò possiamo

x y G-e G/e

G/e,C

applicare il principio di induzione e completare, in questo caso, la dimostrazione.

v

(2) Ora supponiamo che ha un solo vertice non contenuto in . Se questo vertice non è adiacente ad ogni

G C

0

∪

G = C v v v

vertice di , allora , che è l'unione disgiunta di C e del vertice , per cui possiamo colorare usando

C 0 0 0

λ p (λ) = λ

ognuno dei colori. Quindi, in questo caso, . Se il vertice è adiacente a vertici di C, e questi vertici

d

G,C

−

d p (λ) = max(λ d , 0)

utilizzano colori, allora .

0 G,C 0

4 J.H. Van Lint e R.M.Wilson, A Course in Combinatorics, Cambridge University Press, 1992.

3 p (λ) = 1

(3) Ogni vertice di è contenuto in . In questo caso, abbiamo già un colorato di e . Perciò,

G C G G,C

con il principio di induzione sul numero dei bordi del grafo, il teorema è dimostrato.

In una sezione successiva esamineremo le implicazioni di questo teorema per il puzzle Sudoku. Adesso basta

p (9) = 1

evidenziare che, dato un puzzle Sudoku, il numero di modi per completare il grafo è dato da . Sarebbe

x ,c

3

estremamente interessante determinare sotto quali condizioni un colorato parziale può essere esteso a un colorato

completo. In questa direzione abbiamo il seguente enunciato generale.

°

1.3 Teorema n 2.

Sia un grafo con numero cromatico e un parziale colorato di che utilizza solo

G C G −

χ(G) χ(G) 2

colori. Se il parziale colorato può essere completato in colorato completo di , allora ci sono al più

G

due modi per estendere la colorazione. °

1.4 Dimostrazione del Teorema n 2.

Dal momento che due colori non sono stati usati nel parziale colorato iniziale, questi due colori possono essere

scambiati nel colorato completo nale per ottenere un'altra estensione completa.

°

Il Teorema n 2 implica che se è un parziale colorato di che può essere completato in un

C G univocamente

−

χ(G) 1

colorato completo di , allora deve utilizzare almeno colori. In particolare, in ogni Sudoku puzzle,

G C 2 2 2 −

n n n 1

almeno 8 colori devono essere usati nelle celle date. In generale, per puzzles Sudoku , almeno colori

x

devono essere utilizzati, nel parziale colorato dato, anché il puzzle abbia una soluzione unica.

2 Programmazione e parziali colorati

Dato un grafo , con uno specico , possiamo chiederci se questo può essere esteso a un

G parziale colorato colorato

del grafo. E' ben noto che i problemi di colorazione dei gra codicano problemi di programmazione nella

completo

vita reale. L'estensione da un a un corrisponde a un problema di programmazio-

parziale colorato colorato completo

ne con vincoli addizionali, come, per esempio, quando vogliamo programmare incontri di varie commissioni in certi

intervalli di tempo, con alcune di queste già impegnate in altri determinati intervalli. Naturalmente, la corrispon-

dente relazione di adiacenza è che due commissioni sono unite da un bordo se hanno un membro in comune. Questo

è un problema di rilevante interesse e sembra dicile determinare i criteri per dire quando un può

parziale colorato

essere esteso a un dell'intero grafo. Una situazione simile nasce per l'assegnazione delle frequenze.

colorato completo

Supponiamo che, in una data regione, vi siano trasmittenti televisive che hanno bisogno di una frequenza per poter

trasmettere. Due trasmittenti, entro 100 miglia l'una dall'altra, avranno assegnate frequenze diverse per evitare

problemi di interferenze. Spesso alcune trasmittenti hanno già frequenze assegnate, e alle nuove trasmittenti devono

essere assegnate le frequenze tenendo presenti questi vincoli. E', di nuovo, un problema di completamento da un

a un di un grafo. Infatti, noi associamo un vertice a ogni trasmittente e uniamo

parziale colorato colorato completo

due di loro se si trovano entro 100 miglia l'una dall'altra. L'assegnazione di una frequenza corrisponde a un

colore

assegnato a quel vertice. Possiamo evidenziare molteplici esempi relativi a dierenti contesti della vita reale. In

ogni caso il problema del passaggio da un a un emerge come archetipo. Quadrati

parziale colorato colorato completo

Latini e Sudoku sono solo casi specici di questo tema. Tuttavia, essi possono anche essere studiati indipendente

da questo contesto. L'esplicita costruzione di quadrati Latini è ben nota per le applicazioni nella progettazione di

ν ν ν

esperimenti statistici. Negli studi agricoli, per esempio, per poter piantare varietà di piante in le e colonne,

in modo tale che le peculiarità del suolo in cui sono state piantate non abbiano inuenza sull'esperimento. Gli

ν ν

agricoltori hanno già usato quadrati Latini per progettare un tale esperimento. Questo serve per bilanciare i

x

trattamenti dell'esperimento prima della randomizzazione. In questo contesto, se interessa anche testare il ruolo dei

vari fertilizzanti sulla crescita di queste piante, si potrebbe utilizzare un quadrato Sudoku, dove ad ogni sottogriglia

(o banda) viene applicato un diverso fertilizzante in modo da averne uno per ogni trattamento.

X

3 Colorazione esplicita per n X

In questa sezione, mostreremo come si può colorare completamente il grafo Sudoku . Ricordiamo che il numero

n

di un grafo è il numero minimo di colori necessari per colorare completamente i suoi vertici. Così, il grafo

cromatico K

completo , composto da vertici, in cui ogni vertice è adiacente a ogni altro vertice, ha numero cromatico .

n n

n 4

°

3.1 Teorema n 3.

Per ogni numero naturale , c'è un colorato completo del grafo Sudoku usando colori. Il

2

n X n

n

numero cromatico di è .

2

X n

n °

3.2 Dimostrazione del Teorema n 3.

Notiamo subito che tutte le celle nell'angolo superiore sinistro della griglia sono adiacenti a tutte le altre,

n x n

2 2

K K n X n

e questo forma un grafo isomorfo a . Il numero cromatico di è e così, necessita di almeno

2 2 n

n n (i, j)

colori per essere un colorato completo. Come rimarcato in precedenza, è conveniente etichettare i vertici con

2 2 2

≤ ≤ − ≤ ≤ −

0 i, j n 1 n 0 i, j n 1 i = t n + d

. Consideriamo le classi di modulo residuo . Per , scriviamo con

i i

2

≤ ≤ − ≤ ≤ − ≤ ≤ −

0 d n 1 0 t n 1 0 j n 1 c(i, j) = d n + t + nt + d

e e similarmente per . Assegniamo il ,

colore

i i i i j j

2 2 2

n (i, j) n n

modulo ridotto , alla esima posizione nella griglia . Aermiamo che in questo caso si ha un colorato

x 0 0

(i, j) (i , j )

completo. Per vedere ciò, mostreremo che ogni due coordinate adiacenti e hanno colori distinti. Infatti, se

0 0 0 0

6

i = i c(i, j) = c(i, j ) j = j c(i, j) = c(i, j ) nt +d = nt +d

, allora dobbiamo mostrare che a meno che . Se , allora 0 0

j j j j

0 0 0 0 0

6

j = j . j = j c(i, j) = c(i , j) i = i . [i/n] = [i /n]

che signica Allo stesso modo, se , allora a meno che Se ora, e

0 0 0

[j/n] = [j /n] d = d d = d . c(i, j) = c(i , j )

, allora e Se allora

0 0

i i j j t + nt = t + nt .

0 0

i j j j 0 0

t = t t = t (i, j) = (i , j )

Riducendo questo modulo abbiamo . Quindi , per cui anche in questo caso. Pertanto,

n 0 0

i i j j

questo è un colorato completo.

4 Conteggio delle soluzioni.

Vogliamo arontare brevemente la questione dell'unicità della soluzione per un dato puzzle Sudoku. Non è sempre

chiaro, in via preliminare, se un dato puzzle ha una soluzione. In questa sezione, determineremo qualche condizione

necessaria perché vi sia una soluzione unica.

ˆ La gura 3 mostra un esempio di puzzle Sudoku che ore precisamente due soluz