Newsgroup: it.hobby.enigmi
Titolo: Sudoku: più di un milione di soluzioni

Molti si saranno chiesti quante e quali siano sono le soluzioni del Sudoku.
Per rispondere si può pensare di partire da una soluzione disponibile e
chiedersi:
"quante e quali ulteriori soluzioni posso trovare a partire da una soluzione
esistente?"
La risposta è semplice.
Se scambio tra loro due righe qualunque appartenenti ad uno stesso blocco o
due qualsiasi blocchi di righe ottengo una soluzione ancora valida, in
quanto non violo le regole né di riga, né di colonna né di blocco: per
ciascun blocco, questo numero è 3!, cioé 6.
Per ciascuna di queste soluzioni, posso pensare di combinare insieme le
soluzioni ottenibili dalle permutazioni del secondo e del terzo blocco:
moltiplicheremo quindi (3!)*(3!)*(3!)=6*6*6
Una ulteriore combinazione possiamo farla mescolando i 3 blocchi tra loro,
che saranno anch'essi scambiambili in 3! = 6 modi diversi. Mescolando tra
loro le righe di una soluzione data possiamo quindi ottenere altre 6*6*6*6 =
1296 soluzioni valide.
Ma fino ad ora abbiamo giocato solo con righe: un discorso analogo lo si può
fare anche scambiando due qualsiasi colonne appartenenti ad uno stesso
blocco di colonne o due qualsiasi blocchi di colonne. Conseguentemente,
ciascuna delle 1296 soluzioni precedentemente scovate possono generare altre
1296 soluzione.
Complessivamente avremo quindi che da una soluzione qualsiasi del gioco
posso ricavarne 6*6*6*6*6*6*6*6 = 6 ^ 8 = 1679616 soluzioni valide.
Ci si può chiedere a questo punto se quelle trovate siano o no tutte le
possibili soluzioni del gioco.
Io credo di sì, e penso che la dimostrazione non sia nemmeno tanto
difficile. Penso si dovrebbe partire nell'identificare un set furbo di
caselle pre-fissate che identificano univocamente una soluzione e verificare
che attraverso i suddetti scambi di righe e colonne riesco a ricostruire una
soluzione che ricopra tali celle....
In ogni caso, da buon ingegnere quale io sono, vi invito ad una verifica sul
campo: oltre a progettare software per lavoro, per le persone della e-Soft
programmare è anche un hobby, così ci siamo divertiti a fare una piccoli
routine che ha generato il "filettone" con le 1679616.
Il file in oggetto è scaricabile dal sito della nostra azienda:
http://www.e-soft.it/sudoku/
Provate a trovarne una che non sia compresa qui dentro!
Buon sudoku a tutti!
Mauro Lenzi


Alla faccia della "piccola" routine!!! 136 mb per un giochino cosě ti
sembrano pochi?

 routine che ha generato il "filettone" con le 1679616.
Da bravo ingegnere ho fatto anch'io un programma sul Sudoku, ma il mio 
non calcola tutte le permutazioni di una soluzione, ma tutte le 
soluzioni, usando un programma a vincoli (ottimizzazione combinatoria).
Facendo girare il programma (che ho anche dato come esercizio agli 
studenti di Intelligenza Artificiale ;-) mi genera piu` di 5 milioni di 
soluzioni (dopo un po' l'ho fermato), anche dopo aver eliminato le 
soluzioni simmetriche (ma ho usato una tecnica che non toglie tutte le 
soluzioni simmetriche). Quindi una stima approssimativa e` che il numero 
di Sudoku e` senz'altro maggiore di 5E6*1679616  (visto che a ciascuna 
soluzione possono essere aggiunte 1679616 soluzioni simmetriche).
Ad esempio, questa soluzione mi pare non compaia nel vostro file:
912345678634978152857612394429156837178234569563789421745823916286591743391467285
Ciao,
Marco
--
http://www.ing.unife.it/docenti/MarcoGavanelli/

 La risposta è semplice.
La risposta e' semplice ma e' SBAGLIATA!
Il numero di possibili configurazioni valide e'
  6670903752021072936960
e il metodo utilizzato per calcolarle e' presentato
in questo articolo:
http://www.shef.ac.uk/~pm1afj/sudoku/sudoku.pdf
ciao,
g.