Newsgroup: it.comp.lang.pascal
Titolo: Sudoku?

Mio padre ormai se e' perso dietro a questo gioco... quello facile e 
quello medio non gli richiedono piu' di dieci minuti, ma l'ho visto 
vaneggiare ore dietro al Diabolico sul Corriere della Sera.
A me sa' di gioco noioso, o forse ho nausea di numeri in questo momento.
Il problema e' quando leggo cose di questo genere:
http://www.corriere.it/Primo_Piano/Cronache/2005/07
_Luglio/14/sudoku.shtml
e leggo di questa prof di filosofia che lotta con il livello semplice e 
dice che "non c'e' nulla di matematico"...  vabbeh
Cmq, dopo questo lungo ed inutile preambolo -Razz che non ha mai nulla 
da fare, RdC che magari tempo libero lo trova, Omega che a questo punto 
l'orale l'avra' dato- scrivere un programma che risolva il suddetto 
gioco?
Io ho un'idea, ma non ho tempo. Questo implica che vi do' un vantaggio 
di una, anzi, quasi due settimane :p
ovviamente - dato che altrimenti sarebbe OT :p - va fatto in pascal :)
-- 
Dreadnaut - 
http://dreadnaut.servebeer.com/
(Life would be easier if I had the source code)

 
Capito RDC? NOn barare niete Java :PPPP
-- 
Il Razziatore,
The Only Good Windows is an uninstalled Windows
-----------------------------------------------
MSN   : 
IlRazz...@netscape.net
ICQ   : 67552596
Yhaoo : Razziatore82
-----------------------------------------------
Founder of MediaPlayer Project
http://mpp.iwebland.com

Non corrette oggi ci penso un pochino
ReDiCuori
-- 
-- 
L'uomo non sa perchč si innamora, l'uomo viene travolto e basta
---------------------------------------------------------
www.giordanoemilio.altervista.org
---------------------------------------------------------
www.securitygroup.it
Societą di servizio che opera nel campo
della sicurezza aziendale
---------------------------------------------------------
www.pascallike.too.it
http://utenti.lycos.it/pascallike
il sito sulla programmazione pascal
sorgenti, tutorial ed utility
------------------------------------------------------------
www.treves-srl.com
Libreria Internazionale Treves
Via Toledo 249/250 Napoli
------------------------------------------------------------
www.alphalibri.com
Vendita ingrosso di libri
Via S.Anna dei Lombardi 10 , Napoli
------------------------------------------------------- 

 Non corrette oggi ci penso un pochino
io sto lavorando tipo 23 ore al giorno alla tesi, non temere :)


Allora appena ho visto il problema mi è venuto in mente un approccio stile
Programmazione Dinamica, ma poi pensandoci bene mi sa che ormai è una mia 
ossessione.
Formalizziamo il problema e vediamo che ne esce fuori :
Problema :
Data una matrice NxN (9x9), suddivisa in N (9) riquadri ciascuno formato da 
N (9) caselle (ogni riguadro è una matrice 3x3), nella quale sono disposti 
in  alcuni numeri (da 1 a 9), con un minimo di 30.
Trovare un algoritmo che riempia la matrice rispettando i seguenti vincoli.
Data la casella M(i,j) un numero a  con a=1..9 può essere inserito se e 
soltanto se :
1. a Non è presente nella colonna j
2. a Non è presente nella colonna i
3. a Non è presente nel riquadro di appartenenza.
Nota i riquadri non sono in overlap quindi il primo riquadro ha coordinate
M(1,1), M(3,3) il secondo M(1,4),M(3,6) e così via...
Svolgimento :
Prima di tutto cerchiamo di capire cosa bisogna fare.
Viene data una matrice 9x9 suddivisa in 9 sottomatrici, la matrice contiene 
dei numeri compresi tra 1 e 9.
Bisogna riempire l'intera matrice in modo tale che il valore da inserire 
nella casella (i,j) (chiamiamolo s):
NON DEVE appartenere alla colonna j della matrice
NON DEVE appartenere alla riga i della matrice
NON DEVE appartenere alla sottomatrice contenente la casella (i,j)
Bisogna quindi scrivere una funzione che riceve una matrice M parzialmente 
riempita e ritorni la stessa matrice totalmente riempita
Input :
    Matrice NxN parzialmente riempita
Ouput
   Matrice NxN totalmente riempita rispettando i vincoli elencati prima.
Vediamo come riscrivere i vincoli i modo da rendere la lettura più facile
(almeno si spera che una notazione similFormale riesca a dare il senso di
tutto):
    dato un numero a e le coordinate (i,j) è possibile inserire a nella 
matrice M sse
             a not in M(i) and a not in M(j) and a not in Sub(i,j)  con 
a=1..9 e i,j=1..N(9)
dove sse abrv. se e soltanto se
         M(i) indica l'intera riga i della matrice
         M(j) indica l'intera colonna j della matrice
         Sub(i,j) indica la sottotabella contente (i,j)
La prima cosa che mi è venuta in mente è quella di provare tutte le 
combinazioni fino ad ottenere la soluzione, tornado sui propri passi quando 
necessario. In realtà è possibile un approccio meno costoso.
Ho definito una funzione di costo per ogni casella della matrice. Possiamo 
dire che il costo di scelta  per una singola casella è pari al numero di 
numeri (scusate il gioco di parole) che possiamo immettere nella casella 
senza violare il vincolo.
Usando una notazione algebrica possiamo scrivere che il Costo(i,j)=|(((N 
\M(i)) \ M(j))\ Sub(i,j)))|    dove | | indica la cardinalità dell'insieme e 
\ l'operazione di complementazione (se non ricordo male tutti gli elementi 
di N che non appartengono a M(i)).
Non dimentichiamoci che esistono delle caselle con valori già assegnati, la 
funzione costo diviene :
                      0                                                se 
M(i,j) <>0
Costo(i,j) =
                      |(((N \ M(i)) \ M(j))\ Sub(i,j)))|   altrimenti
supponendo che le caselle di M da riempiere siano inizializzate 0.
Data questa funzione possiamo assegnare un costo ad ogni casella, si ottiene 
che se il costo della casella (i,j) è pari 1 allora la scelta è immediata ed 
è pari a N\M(i)\M(j)\Sub(i,j), dove N è l'insieme di numeri {1,..9}.
Una volta scelto un valore per la casella (i,j) possiamo decrementare i 
costi delle caselle che si trovano sulla stessa riga, sulla stessa colonna e 
nello stesso quadrante, sfruttando la funzione per il calcolo dei costi.
Un algoritmo che risolve il problema potrebbe essere come questo :
  1. Si crea una matrice C dei costi
  2. Finchè la matrice dei costi non è Zero (tutte le caselle hanno un 
valore 0)
  3.    Si estrae il valore minimo pari a 1 (ottenendo i,j)
  4.    Si assegna ad M(i,j) = N\M(i)\M(j)\Sub(i,j)
  5.    Si assegna a C(i,j)=0
  6.    Ricalcola(i,j) <--- ricalcola tutti i valori sensibili alla modifica 
effettuata
Il problema ora è dimostrare che l'algoritmo proposto sia corretto. Per fare 
ciò bisogna dimostrare che esiste sempre la possibilità di trovare una 
casella il cui costo è 1.
Beh mi sono arrovellato un bel pò, provando su vari schemi... l'invariante 
esiste ed è sempre rispettata, penso che sia dovuta alla distribuzione 
iniziale di numeri ed alla posizione di questi nella matrice. (Lo so che non 
è una dimostrazione formale chiedio perdono, ma funziona per almeno 10 
schemi che ho visto).
Vediamo di scrivere qualcosa che sia più vicina al pascal (così Raz è 
contento)
procedure RisolviSudoku()
    begin
        C:=CalcolaCosti(M);
        while not Zero(C)
            begin
                (i,j):=getMinimo(C);
                M(i,j):=N\M(i)\M(j)\Sub(i,j);
                C(i,j):=0;
                Ricalcola(C,i,j);
            end;
     end;
Vediamo quanto costa questo algoritmo è come si può migliorare... (sperando 
che mi ricordo come si fa !)
Iniziamo a proporre una versione di CalcolaCosti:
CalcolaCosti (M)
begin
    for i=1 To n do
      for j=1 to n do
         if (M(i,j)<>0) then
           conta=0;
           for k=1 to n do
              if (M(i,k)<>0) conta=conta+1;
           for k=1 to n
              if (M(k,i)<>0) conta=conta+1;
           conta=conta+ContaSub(i,j);
          C(i,j)=9-conta;
 end
i due cicli innestatti hanno una complessità pari  n^2,  i due cicli interni 
hanno complessità n, ContaSub deve contare 9 caselle pari al valore di input 
n  quindi possiamo dire che il tutto è n^2 * 3n = O(n^3).
getMinimo(C)  su una matrice non ordinata ha complessità al più n^2 => 
O(n^2)
Ricalcola(C,i,j) è lineare sull'input dato che è simile ai due cicli for e 
contaSub di CalcolaCosti, quindi  O(n)
L'operazione di assegnazione alla casella M(i,j) potrebbe essere molto 
dispendiosa.
Vediamo un pò cosa possiamo fare...
Siccome tutte le righe, tutte le colonne e tutti i riquadri devono contenere 
alla fine tutti i numeri da 1 a 9 si può pensare di conservare stringe di 9 
bit per ogni riga e per ogni riguadro, in modo da effettuare aggiornate ogni 
volta che si aggiunge un nuovo numero, e tramite le quali recuperare il 
valore da inserire quindi riduciamo il tutto ad un costo costante.
Il ciclo while dovrebbe essere ripetuto n^2 volte e la condizione Zero(C) 
potrebbe essere calcolata con una complessità al più pari a O(n), magari 
sfruttando i bit (questo in teoria...)
Per un costo totale pari a O(n^4) se nn ho scritto ca... e se ho fatto bene 
i conticini
-----------------------------------------------------------------------------------
Sfruttando un heap binario minimo (con un piccolo indice correlato => 
aumento della complessità di spazio) è possibile, sempre se ho fatto bene i 
conti, ridurre la complessità a n^3 log n
CalcolaCosti (M)
begin
    for i=1 To n
      for j=1 to n
         if (M(i,j)<>0) then
           conta=0;
           for k=1 to n
              if (M(i,k)<>0) conta=conta+1;
           for k=1 to n
              if (M(k,i)<>0) conta=conta+1;
           conta=conta+ContaSub(i,j);
          C(i,j)=9-conta;
   costruisciHeap(C)
 end
In questo caso C lo trattiamo come un array di 81 elementi, lascio la 
notezione a matrice nn è  difficile calcolare l'indice per l'array.
La prima parte è n^3, costruisciHeap ha una complessità n^2 log n => n^3
RisolviSudoku()
    begin
        C=CalcolaCosti(M);
        while notEmpty(C)
            begin
                (i,j)=getMinimo(C);
                M(i,j)=N\M(i)\M(j)\Sub(i,j);
                C(i,j)=0;
                Ricalcola(C,i,j);
            end
     end
getMinimo su un heap è eseguito a tempo costante + log (n) per il ripristino 
della proprietà dello heap
Ricalcola può essere riscritto sfruttando un algoritmo di decreese key che 
su un heap binario ha complessità log n  => nlog n
il ciclio viene sempre eseguito per tutte le caselle della matrice quindi 
n^2
otteniamo cosi n^3 log n.  che è un bel rispario di tempo.
ReDiCuori
-- 
-- 
L'uomo non sa perchè si innamora, l'uomo viene travolto e basta
---------------------------------------------------------
www.giordanoemilio.altervista.org
---------------------------------------------------------
www.securitygroup.it
Società di servizio che opera nel campo


 riempita e ritorni la stessa matrice totalmente riempita
Scusate io non conosco il gioco { meaculpa si scrivera cosi boh } ma il 
3o vincolo non lo capisco. Vuoi dire che s non deve stare nella 
submatrice 3x3 che continee la cella (i,j)? ho capito bene?
{ non sono andato avanti a leggere perchè lo voglio fare da solo :D }


 { non sono andato avanti a leggere perchè lo voglio fare da solo :D }
Allora
    1   2   3   4   5   6   7   8   9
1  2       8
2       x   7    4  5   2
3       3
4
5
...
Metti che devi inserire x alle coordinate (2,2) allora x deve essere 
diverso da tutti i valori presenti sulla
riga 2 da tutti i valori presenti sulla colonna 2 e diverso da tutti i 
valori presenti nella matrice 3x3 di coordinate (1,1) (3,3). Quindi x dovrà 
essere divverente da 2,3,4,5,7,8
Alla fine del gioco ti trovi che ogni riga contiene tutti i numeri da 1..9, 
ogni colonna tutti i numeri da 1..9, ogni riguadro tutti i numeri da 1..9
ReDiCuori


 submatrice 3x3 che continee la cella (i,j)? ho capito bene?
- regole:
http://www.corriere.it/Primo_Piano/Cronache/2005/06
_Giugno/24/pop_regole.shtml
io ho ancora sbattimento estremo fino a Martedi, poi mi lancio nella mia 
idea :)


ho notato parecchio interesse per questo gioco da parte di molti....
ho letto le regole, ed e' simile a quello delle "regine di una
scacchiera"
di fatto trovare la o le soluziooni al gioco non ha maolto senso se le
prove le deve fare una persona...
a causa della complessita' (in ordine del numero d tentativi da fare,
 che sono quasi tutti non validi, eccetto le soluzioni come da
regolamento)
questo e' uno di quei problemi da dare in pasto ad un algoritmo che usa
aspprocci di intelligenza artificiale (tipo minimi conflitti), + qualche
altra nozione di
euristica ...e tenendo i computers accesi per un paio d ore ...o giorni
potrete trovare qualche soluzione...
immaginate di non usare solo 9 numeri , ma una quantità variabile...
fareste ancora con carta e penna la ricerca delle soluzioni?
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG

( Salvatore Licciardi - news:359879992f4c7d1fe3d47487d72cb157.93615
@
mygate.mailgate.org
 )
non ne sono certo (non ho provato molto) ma la complessita' per un umano 
non e' cosi' elevata. I vincoli sono facilmente gestibili e -persino- mia 
madre, a-matematica e letterata al 100%, non ha problemi a livello facile 
e medio.
La cosa complessa e' simularlo con un algoritmo secondo me. L'esaustivo 
ok, ma costruire un'euristica non è poco.
L'idea AI non e' male... ma in fondo AI vuol dire alberi di ricerca in 
questo tipo di problemi, ovvero semi-esaustivo.
La mia idea e piu' sul calcolo evoluzionistico, che secondo me puo' 
viaggiare veloce, ma ne ho una di riserva di programmazione genetica, che 
-inventa- l'euristica.
domani mi laureo, poi ci penso :p


 suddetto gioco?
Eehhehe effettivamente ormai... 88/100 li ho presi! :P
Cmq devo essere sincero, non sono un appassionato di sudoku, mi informerò
ma la butto li... calcolo combinatorio?
Devo essere sincero, dalla fine dell'esame ovvero dopo il 7 luglio fino ad
oggi sto lavorando quindi ho poco tempo da dedicare alla programmazione,
mi rifarò vivo! Anche perchè a settembre inizierà per me (spero) la
"carriera" universitaria a lancusi (UNISA)...
Un saluto a tutti
E Dread complimenti per la Laurea :))))
--
________________________
· Omega
· 
http://gnammo.altervista.org
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

domani mi laureo, poi ci penso :p
E bravo signor dottore, complimenti.
-- 
Omega e' omega e basta

 E bravo signor dottore, complimenti.
grassie... solo che adesso mi sto perdendo nelle vacanze e non riesco a 
sedermi, scrivere e finire sta' roba... e adesso parto. Torno il 26 e 
provvedero' a sfornare :)
che vergogna che vergogna... Razz ridera' di me in eterno :p


 che vergogna che vergogna... Razz ridera' di me in eterno :p
Chi io? E perchè ? :P
{ nah non sono morto :P e solo che x-privat è andato down per + di un 
mese :'( }
