Newsgroup: it.hobby.enigmi
Titolo: sudoku

SUDOKU ( o SU DOKU) sembra che sia il nuovo tormentone di quest'anno,
qualcuno sostiene che emulerà il successo del cubo di Rubik.
Strano che qui non se ne sia ancora parlato, o forse mi è sfuggito
qualcosa.
Per i pochi che non lo comoscessero: si tratta di una griglia 9*9,
suddivisa in nove sottogriglie 3*3, che deve essere riempita con cifre
da 1 a 9, in modo che in ciascuna riga, colonna e sottogriglia
compaiano tutte e 9 le cifre.
Per esempio:
123  456  789
456  789  123
789  123  456
231  564  897
564  897  231
897  231  564
312  645  978
645  978  312
978  312  645
Molte riviste stanno pubblicando SUDOKU con inserite un certo numero
di cifre, e i lettori devono completare la griglia.
Mi chiedo, a prescindere da eventualli cifre pre inserite, quante
siano le possibili configurazioni valide. In un thread su rec.puzzles
è riportato un valore di circa 6.7*10^21, ma non dice, o ma non ho
capito, come ci si a arrivato.
ciao
paolo

Paolo Licheri ha scritto:

se ne era discusso sulla mailing list "matenigmici".
o meglio, ne avevano discusso.
sinceramente, non riesco a trovarci un grande fascino.
era stato segnalato da Nicola Salmoria il seguente articolo di D. Knuth:
http://arxiv.org/PS_cache/cs/pdf/0011/0011047.pdf
che presenta un algoritmo di copertura applicabile a vari problemi, tra 
cui il sudoku
per quanto riguarda il numero di soluzioni, la difficoltà maggiore sta 
nel NON contare due volte la stessa soluzione, magari con una 
permutazione delle cifre.
inoltre, ogni permutazione delle 3 maxirighe o maxicolonne permette di 
ottenere una soluzione al problema.
quindi si dovrebbero trovare le soluzioni "base"
ma, ripeto, non lo trovo così affascinante :-)
pazqo

A proposito di tutto ciň... sapete dirmi se la soluzione ad ogni schema č 
unica o meno? Avevo capito che cosě fosse, ma ho risolto il primo di quelli 
pubblicati da Repubblica e, nonostante sia corretto, la soluzione non 
corrisponde a quella fornita dal giornale... 


Puoi postare lo schema?

 



eccolo:


 


8    4    
5    1    2    3    
6    9    7


 


7    6    
3    8    4    9    
5    1    2


 


9    1    
2    6    7    5    
8    3    4


 


4    9    
8    2    1    7    
3    5    6


 


3    5    
7    9    6    8    
4    2    1


 


1    2    
6    5    3    4    
9    7    8


 


5    7    
1    3    8    6    
2    4    9


 


6    3    
4    7    9    2    
1    8    5


 


2    8    
9    4    5    1    
7    6    3


 


 


era quello "avanzato" pubblicato da Repubblica il 
25 giugno; qui si può vedere lo schema iniziale e la soluzione pubblicata: 
http://www.repubblica.it/speciale/2005/sudoku/index.html


 


 




Non č unica,anzi
Per lo schema
 8 4   |         |   9 7
         | 8   9 |
         | 6   5 |
         |   1    |
 3 5   | 9   8 |   2 1
   2 6 |         | 9 7
         |         |
      4 |         | 1
      9 |         | 7
ho trovato queste 2 soluzioni
 8 4 5 | 1 2 3 | 6 9 7
 6 7 1 | 8 4 9 | 3 5 2
 9 3 2 | 6 7 5 | 8 1 4
 4 9 8 | 2 1 7 | 5 6 3
 3 5 7 | 9 6 8 | 4 2 1
 1 2 6 | 5 3 4 | 9 7 8
 5 1 3 | 7 8 6 | 2 4 9
 7 6 4 | 3 9 2 | 1 8 5
 2 8 9 | 4 5 1 | 7 3 6
-------------------------------
 8 4 5 | 3 2 1 | 6 9 7
 6 7 2 | 8 4 9 | 3 1 5
 9 1 3 | 6 7 5 | 2 8 4
 4 9 8 | 2 1 7 | 5 3 6
 3 5 7 | 9 6 8 | 4 2 1
 1 2 6 | 5 3 4 | 9 7 8
 7 3 1 | 4 5 2 | 8 6 9
 2 8 4 | 7 9 6 | 1 5 3
 5 6 9 | 1 8 3 | 7 4 2
ma ce ne  sono mooooolte di piů
Per lo schema
 6       | 2      |     9
          |         | 6   4
       4 | 1 8   |
 3 5 2 | 8 6   | 4   1
       1 |   2    | 8
 4    8 |   7 1 | 9 5 2
          |   5 3 | 2
 5    3 | 4      |
 1       |      8 |     5
ci sono solo 2 soluzioni
 6 3 5 | 2 4 7 | 1 8 9
 8 1 7 | 9 3 5 | 6 2 4
 2 9 4 | 1 8 6 | 5 3 7
 3 5 2 | 8 6 9 | 4 7 1
 9 7 1 | 5 2 4 | 8 6 3
 4 6 8 | 3 7 1 | 9 5 2
 7 4 9 | 6 5 3 | 2 1 8
 5 8 3 | 4 1 2 | 7 9 6
 1 2 6 | 7 9 8 | 3 4 5
e
 6 3 7 | 2 4 5 | 1 8 9
 8 1 5 | 9 3 7 | 6 2 4
 2 9 4 | 1 8 6 | 5 3 7
 3 5 2 | 8 6 9 | 4 7 1
 9 7 1 | 5 2 4 | 8 6 3
 4 6 8 | 3 7 1 | 9 5 2
 7 4 9 | 6 5 3 | 2 1 8
 5 8 3 | 4 1 2 | 7 9 6
 1 2 6 | 7 9 8 | 3 4 5

 la soluzione non corrisponde a quella fornita dal giornale...
per questo schema esistono almeno 5 soluzioni
      1   8 9 4   5   7
         2    3
      4   5   8 1  3
            7  6
      7 2   4  5    6
      6 9 1 3 2 8 4 7
        4  1     7
      5
          7

       xx7xxxxxx
MM

 corrisponde a quella fornita dal giornale...
Ne ho verificati anch'io qualcuno e mi danno varie soluzioni.
Ho usato un programmino in javascript che trovi in
http://www.infocare.it/sudoku.htm
Fa parte di una serie di programmi didattici che risolvono rompicapo su
matrici che abbiamo publicato con un amico insegnante.
Andrea