Quadrati sudoku e polinomi cromatici

Quadrati Sudoku e polinomi cromatici *

†

Agnes M. Herzberg e M. Ram Murty

Giugno 2007

Il Sudoku è diventato un puzzle molto popolare che molti giornali propongono come appuntamento giornaliero.

Il gioco consiste in una griglia di 9 x 9 celle, in ognuna delle quali si deve collocare un numero da 1 a 9, in modo

×

3 3

tale che in ognuna delle 9 righe, colonne o sottogriglie, compaiano tutte e sole le cifre da 1 a 9.

Figura 1. La griglia del Sudoku. ×

n n n

Ricordiamo che un quadrato Latino di rango è un ordinamento di numeri, tale che ogni riga e colonna

n

contenga tutti i numeri da a. In particolare, si può affermare che ogni Sudoku è un quadrato Latino di rango

1 ×

3 3

9, ma non viceversa, a causa della condizione relativa alle sottogriglie.

1

4 2 5 4 7

8 3

1 9

3 4 2

5 1

8 6

Figura 2. Un Sudoku con 17 dati specifici.

Coloro che tentano di risolvere un Sudoku si pongono naturalmente diversi interrogativi, quali ad esempio:

• Per un dato Sudoku esiste una soluzione?
• Se la soluzione esiste è unica?
• Se la soluzione non è unica quante soluzioni esistono?

Articolo pubblicato dal Notiziario della Società Americana di Matematica (http://www.ams.org/notices/200706/tx070600708p.pdf)

*

nel numero di giugno 2007 e tradotto da arch. Federico Alvino (05/2010), alvino.federico@yahoo.it, la cui pubblicazione solo su

questo sito è stata autorizzata dal dr. Erin M. Buck, per conto della AMS, unica titolare dei diritti di copyright, in data 07/06/2010.

Agnes M. Herzberg (herzberg@post.queensu.ca) e M. Ram Murty (murty@mast.queensu.ca) sono professori emeriti di matematica

†

presso la Queen's University, Canada. La loro ricerca è stata parzialmente finanziata dal NSERC, Natural Science and Engineering

Research Council. 1

• Esiste una procedura sistematica per determinarne le soluzioni?
• Quanti sono i Sudoku con soluzione unica?
• Qual è il numero minimo di dati specifici che garantisce l'unicità della soluzione?

Per esempio, in figura 2 si mostra che il numero minimo di dati specifici è al massimo 17. (Lasciamo al lettore la

verifica dell'unicità della soluzione del Sudoku di fig. 2).

Al momento non si sa se un Sudoku con 16 dati specifici ha una soluzione unica. Gordon Royle ha collezionato

1

36628 distinti Sudoku con 17 dati specifici.

Noi riformuleremo molti di questi interrogativi in un contesto matematico per tentare di trovare le risposte. Più

precisamente, noi interpretiamo il Sudoku come un problema di colorazione dei vertici all'interno della teoria dei

grafi. Ciò rende possibile generalizzare le questioni e inquadrarle in una struttura più ampia. Noi discuteremo,

inoltre, la relazione tra quadrati Latini e Sudoku per dimostrare che l'insieme dei quadrati Sudoku è sostanzialmente

più piccolo di quello dei quadrati Latini.

Polinomi cromatici

−

grafo colorato completo λ colorato G

Per convenienza del lettore, ricordiamo la nozione di. Un di un grafo è una

{1,

f G 2, ....λ} colorata completa

mappa dall'insieme dei vertici di a. Pertanto una mappa si definisce se si verifica

6 = x y G completamente

che con e giacenti in. Il numero minimo di colori richiesti per colorare i nodi di

f(x) f(y)

G numero cromatico G χ(G).

un grafo è chiamato di e viene denotato con. Pertanto non è difficile vedere che, in

realtà, il Sudoku diventa un problema di colorazione dei grafi. Infatti, noi associamo un grafo alla griglia del

9 x 9

Sudoku nel modo seguente. Il grafo avrà 81 vertici, ognuno corrispondente a una cella della griglia. Due distinti

vertici saranno considerati adiacenti se e solo se le celle corrispondenti della griglia si trovano o sulla stessa riga,

colorato completo

Quindi, un Sudoku esatto corrisponde a un di

o sulla stessa colonna o nella stessa sottogriglia. 2 2

n x n

questo grafo. Poniamo ciò in un contesto un po' più generale. Consideriamo una griglia. Associamo a ogni

0 0

2

≤ ≤

(i, j) 1 i, j n (i, j) (i', j')

cella della griglia un vertice etichettato da con. Noi diremo che e sono adiacenti se

2

0 0 0 0

i = i j = j i/n i'/n j/n j'/n X

o oppure se = e =. Indicheremo questo grafo con e lo chiameremo grafo

n 2

n

Un quadrato Sudoku di rango sarà un di questo grafo usando colori.

del Sudoku di rango n. n colorato completo

Un puzzle Sudoku corrisponde a un e il problema è di vedere se questo può essere

colorato parziale colorato parziale

completato in un del grafo. Sottolineiamo che, in genere, è più conveniente etichettare i vertici

colorato completo 0

2

≤ ≤ −

0 i, j n 1 i = i

di un usando con. Quindi e sono adiacenti se o

grafo Sudoku di rango n (i,j) (i,j) (i',j')

3

0 0 0

j = j i/n = i'/n j/n = j'/n χ

oppure se e. Il che significa che è l'intero più grande minore o uguale a

χ X

. Ricordiamo che un grafo è definito se ogni vertice ha lo stesso grado. Semplici calcoli mostrano che

regolare n

2 − − −

3n 2n 1 = (3n + 1)(n 1) n = 3 X

è un grafo regolare quando ogni vertice ha grado pari a. Nel caso di, 3

− −

20 regolare n = 2 X 7 regolare

è un grafo e nel caso, è un grafo. Il numero di modi per colorare un grafo

2

λ λ

con colori è ben noto ed espresso da un polinomio in di grado eguale al numero dei vertici di. Il nostro

G G.

primo teorema dimostra che dato un di G, il numero di modi per completare la colorazione per

parziale colorato C G

λ λ λ

ottenere un usando colori è ancora un polinomio in, a condizione che sia maggiore o uguale

colorato completo °

al numero dei colori usati in. Più precisamente tanto è indicato nel Teorema n. 1.

C.

°

Teorema n. 1

Sia un grafo finito di vertici. Sia un parziale colorato di di vertici formato con colori.

G v C G t d

0

Sia il numero di modi per completare la colorazione usando colori per ottenere un colorato

p(λ) λ

G,C

completo di G. Allora è un polinomio a una variabile (λ) con coefficienti interi di grado v-t

p(λ) λ

G,C

per.

≥

λ d Daremo due dimostrazioni di questo teorema.

La prova più diretta utilizza la teoria degli insiemi parzialmente ordinati e le funzioni di Möbius che ricapitoliamo

brevemente. Un insieme parzialmente ordinato (acronimo), è un insieme di elementi uniti con un ordinamento parziale

poset P

≤ ≤ ∈ ≤

x x x P x y

indicato dalla relazione che soddisfa le seguenti condizioni: (a) per ogni; (b) e

≤ ≤ ≤ ≤

y x x = y x y y z x z

implica che; (c) e implica. Noi considereremo solo finiti. Esempi comuni di

posets

comprendono la collezione dei sottogruppi di un gruppo finito parzialmente ordinato dall'insieme inclusione

posets

e la collezione dei divisori positivi di un numero naturale parzialmente ordinato dal criterio di divisibilità. Un

n

piccolo esempio è dato dalla seguente costruzione.

1 vedi http://www.csse.uwa.edu.au/~gordon/sudokumin.php

2 l m

Qui la notazione significa che arrotondiamo all'intero maggiore più vicino.

•

3 h i

Con che indica la funzione intera più grande.

• 2

Sia un grafo finito ed un bordo di. Il grafo ottenuto da identificando i due vertici uniti da (con la

G e G G e

G/e

rimozione dei conseguenti lati multipli) è denotato da ed è chiamato. In generale, noi

contrazione di G da e.

diciamo che il grafo è una contrazione di se è ottenuto da con una serie di contrazioni. L'insieme di tutte

G' G G' G

A B

le contrazioni di un grafo finito G può ora essere parzialmente ordinato definendo che se è una contrazione

A

≤ × →

μ : P P

di. Dato un finito parzialmente ordinato da, noi definiamo la funzione di Möbius

B poset Z

P 6

μ(x, x) = 1 μ(x, y) = 0 =

ricorsivamente, impostando:; se.

x z

x≤y≤z

Il teorema principale della teoria delle funzioni di Möbius è il seguente.

→

f : P

Se è una funzione a valori complessi e definiamo

C P

g(y) = f(x)

≤

x y

allora P

f(y) = μ(x, y)g(x)

≤

x y

e viceversa. 4

Rimandiamo il lettore a (vedi nota) per ampliare queste idee.

Dimostrazione del Teorema n. 1

° (G, C)

Useremo la richiamata teoria delle funzioni di Möbius per provare il Teorema n. 1. Sia dato, con grafo e

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 finale 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 specificati per. Sia il numero di modi per colorare

G' C 0

G', C

λ

(non necessariamente in modo completo) i vertici di G' usando colori tra quelli specificati per C. 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(λ)

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 coefficienti 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

induzione sui numeri dei bordi del grafo (G, C). Consideriamo tre casi: