| un teorema sul sudoku | [matematica_light] |
(Una versione più ampia e spero più completa di questa notiziola si trova sul mio sito. Commenti sempre benvenuti!)
È un po' che non scrivo di "matematica leggera": però lo spunto che GaS mi ha mandato in un messaggio privato mi pare interessante, e spero che anche per voi sia lo stesso.
Il punto di partenza è questa recensione - che non è mia, mi affretto a precisare - dove viene enunciato il seguente teorema: Se nello schema iniziale di un sudoku appaiono solo sette numeri diversi (ripetuti quanto si vuole: magari lo schema ha 24 numeri preinseriti, ma solo sette di questi ), allora il sudoku non ha una soluzione unica. (e quindi, aggiungo io, non apparirà mai sui giornali).
Per uno che è abituato a masticare un po' di matematica, la dimostrazione è immediata, quindi è inutile che me la scriviate: mi fido. Sono più interessato a sentire commenti di persone che si divertono a risolvere i sudoku, ma sono convinti di non capire nulla di matematica. Non ci sono premi, ma nemmeno gogne pubbliche; il vantaggio di moderare i commenti è che non debbo necessariamente renderli pubblici. Se qualcuno non si fida delle sue capacità, posso anche dargli un aiutino, basta che me lo chieda privatamente.
Perché tutto questo? beh, mi piacerebbe sfatare qualche mito. Perché diciamocela tutta: la matematica è come qualsiasi altra cosa. Ci sono cose difficili se non impossibili, e cose alla portata di tutti. L'importante è non darsi per vinti in partenza.
| Commenti (8)
Se non avessi detto che era semplice mai ci sarei arrivato.
Scusa, è tardi, io sono un po' stanco e non mi ci sono messo più di tre secondi, ma, se il sudoku è risolubile, non esiste almeno la seconda soluzione [SPOILERONE CANCELLATO]?
Nell'articolo c'è un errore: dice che in un sudoku non posso esserci numeri uguali su una stessa riga, su una stessa colonna, o su una stessa diagonale.
vb, sei "convinto di non capire nulla di matematica"?
beh ciao eh...vi lascio alle vostre cose interessanti.
[SPOILERONE!!!]
mmm, forse mi sfugge qualcosa, ma non mi semra un teorema da affrontare matematicamente: se in uno schema sono presenti solo 7 numeri su 9 allora per forza esistono almeno 2 soluzioni, identiche in tutto ma con le posizioni dei 2 numeri mancanti scambiate. Del resto il sodoku, anche se tipicamente viene fatto con i numeri, non e' un gioco di matematica ma di logica...
@mante: la paura della matematica è proprio tanta, neh?
@alex: perché la tua dimostrazione (che poi è quella pratica) non sarebbe matematica? Certo, non è numerica, ma la matematica è ben più dei numeri, basti pensare a tutte le lettere che si usano, latine, greche e financo l'aleph.
Comunque è un good point, ne tengo conto nella versione definitiva che sto preparando per il sito.
Alex,
a scanso di equivoci, il Sudoku è un problema NP-completo, infatti è equivalente al problema della colorazione di un grafo (che è NP-completo: Karp, 1972).
Esempio per un Sudoku di 9x9 caselle, con 9 colori (ma puoi generalizzare a nxn con n colori):
- i nodi sono le coppie (a, b) con a, b numeri interi da 1 a 9;
- una coppia di nodi (a, b) e (a', b') è connessa se e solo se a = a', oppure b = b', oppure se int(a/3) = int(a'/3) e int(b/3) = int(b'/3) con arrotondamento all'intero superiore.
- la colorazione è l'assegnazione di un intero tra 1 e 9 in modo che due nodi connessi non abbiano lo stesso colore.