SUDOKU
Salve ragazzi . Dovrei fare un compito : creare un programma che una volta inserite le dimensioni del campo del sudoku , lo generi per poi giocarci . Ho girato TUTTO internet..purtroppo gli algoritmi trovati sono molto complessi ( frequento il primo anno di informatica ) . L'idea sarebbe riempire la matrice in modo corretto e poi svuotare le caselle ..ma non so proprio come muovermi
Risposte
Se sei in C, intuitivamente inizierei da un array 3x3 di opportune struct; così lo puoi controllare facilmente con cicli for... Poi devi inventarti un modo di inserire i numeri verificando che le regole siano rispettate!
Ma intendi creare un risolutore ?
Ovvero: Ti carichi prima la matrice dei numeri conosciuti, e da li risolvi il sudoku?
Ovvero: Ti carichi prima la matrice dei numeri conosciuti, e da li risolvi il sudoku?
"slevyn":
Salve ragazzi . Dovrei fare un compito : creare un programma che una volta inserite le dimensioni del campo del sudoku , lo generi per poi giocarci . Ho girato TUTTO internet..purtroppo gli algoritmi trovati sono molto complessi ( frequento il primo anno di informatica ) . L'idea sarebbe riempire la matrice in modo corretto e poi svuotare le caselle ..ma non so proprio come muovermi
Ecco quello che ti serve, pero' provaci da solo prima!
http://www.di.unipi.it/~ferreira/algom/
"Admdebian":
Ecco quello che ti serve, pero' provaci da solo prima!
http://www.di.unipi.it/~ferreira/algom/
Piu' che postare il codice, sarebbe interessante sviluppare le idee.
"Umby":
[quote="Admdebian"]
Ecco quello che ti serve, pero' provaci da solo prima!
http://www.di.unipi.it/~ferreira/algom/
Piu' che postare il codice, sarebbe interessante sviluppare le idee.[/quote]
OK! Hai perfettamente ragione.
L'idea è quella di avere un vettore bidimensionale che rappresenta la situazione iniziale.
Poi si inseriscono nel vettore i valori già noti.
Dopo: il programma procede per tentativi con un ragionamento che noi chiamiamo Backtrack.
Prende la prima cella vuota, calcola i valori possibili che può assumere, ne sceglie uno e va alla seconda casella vuota dove ricalcola i valori possibili e ne sceglie uno...
Quando arriva a una situazione di stallo, il programa torna indietro e fa un tentativo diverso.
Il Sudoku è un problema con complessità esponenziale, come il crack dei certificati di sicurezza. Pertanto si può perfezionare l'algoritmo, ma in generale non si può ottenere qualcosa di velocissimo.
"Admdebian":
Dopo: il programma procede per tentativi con un ragionamento che noi chiamiamo Backtrack.
Prende la prima cella vuota, calcola i valori possibili che può assumere, ne sceglie uno e va alla seconda casella vuota dove ricalcola i valori possibili e ne sceglie uno...
Quando arriva a una situazione di stallo, il programa torna indietro e fa un tentativo diverso.
Direi che peggio di questo sistema, non si può.
"Umby":
[quote="Admdebian"]
Dopo: il programma procede per tentativi con un ragionamento che noi chiamiamo Backtrack.
Prende la prima cella vuota, calcola i valori possibili che può assumere, ne sceglie uno e va alla seconda casella vuota dove ricalcola i valori possibili e ne sceglie uno...
Quando arriva a una situazione di stallo, il programa torna indietro e fa un tentativo diverso.
Direi che peggio di questo sistema, non si può.
[/quote]Una ottimizzazione sarebbe iniziare dalle celle con scelta forzata, e io ne ho una versione buggata che può farlo, però, per le celle che hanno piu' di una scelta, non ci puoi fare molto...oppure sì? cosa proponi?
"Admdebian":
Una ottimizzazione sarebbe iniziare dalle celle con scelta forzata, e io ne ho una versione che lo fa, però, per le celle che hanno piu' di una scelta, non ci puoi fare molto...oppure sì? cosa proponi?
Sicuramente, la situazione che hai prospettato prima, per me sarebbe "l'ultima spiaggia". Quando ho terminato di esaminare tutte le possibili situazioni, quando non so più cosa fare, e mi trovo "in panne", chiederò soccorso alla forza bruta.
Ma prima di questa, c'e' tanto da dire, tanto da fare.
"Umby":
Sicuramente, la situazione che hai prospettato prima, per me sarebbe "l'ultima spiaggia". Quando ho terminato di esaminare tutte le possibili situazioni, quando non so più cosa fare, e mi trovo "in panne", chiederò soccorso alla forza bruta.
Ma prima di questa, c'e' tanto da dire, tanto da fare.
Ok, cosa fai allora?
"Admdebian":
Ok, cosa fai allora?
Inizierei con le prime 2 cose piu' semplici.
1) In una cella ci puo' essere uno ed uno solo numero
2) Un numero può essere in una sola cella (che non è la stessa cosa del punto precedente)
"Umby":
[quote="Admdebian"]
Ok, cosa fai allora?
Inizierei con le prime 2 cose piu' semplici.
1) In una cella ci puo' essere uno ed uno solo numero
2) Un numero può essere in una sola cella (che non è la stessa cosa del punto precedente)[/quote]
A livello di programmazione, per fare questo, avevo individuato 2 modi:
Nel primo, che non ho usato, si può associare un array di numeri ad ogni cella.
Nel secondo, (non credo dia il migliore) che ho provato a implementare) avevo creato una schecchiera per ogni numero del sudoku che conteneva l'informazione su dove il numero poteva essere inserito.
La prima proposta funziona bene per il controllo "in quale cella posso scegliere un numero solo", mentre la seconda rappresenta in modo più immediato il tuo secondo punto.
"Admdebian":
A livello di programmazione, per fare questo, avevo individuato 2 modi:
Nel primo, che non ho usato, si può associare un array di numeri ad ogni cella.
Nel secondo, (non credo dia il migliore) che ho provato a implementare) avevo creato una schecchiera per ogni numero del sudoku che conteneva l'informazione su dove il numero poteva essere inserito.
La prima proposta funziona bene per il controllo "in quale cella posso scegliere un numero solo", mentre la seconda rappresenta in modo più immediato il tuo secondo punto.
Mi piace il primo metodo. Ritengo che entrambi casi da me descritti prima possono essere risolti avendo il vettore dei numeri possibili per ogni cella vuota.
Consiglio, in particolare ai lettori più esperti, di leggere questo interessante articolo di Knuth dal quale può essere derivato un metodo per la risoluzione del gioco sudoku.
P.S. Per quanto ho letto in giro, per il Sudoku, il metodo più veloce rimane il backtracking. I metodi più intelligenti e simili a quelli di risoluzione umani, sono in realtà più lenti su di un computer. Il nostro metodo di analizzare e osservare la griglia del sudoku e molto diversa da quella di un computer, noi abbiamo una visione molto più generale e siamo in grado di riconoscere schemi con maggiore facilità. Il computer fa invece calcoli molto più veloci ed ha maggiore facilità a "tornare indietro".
P.S. Per quanto ho letto in giro, per il Sudoku, il metodo più veloce rimane il backtracking. I metodi più intelligenti e simili a quelli di risoluzione umani, sono in realtà più lenti su di un computer. Il nostro metodo di analizzare e osservare la griglia del sudoku e molto diversa da quella di un computer, noi abbiamo una visione molto più generale e siamo in grado di riconoscere schemi con maggiore facilità. Il computer fa invece calcoli molto più veloci ed ha maggiore facilità a "tornare indietro".
Il backtracking è sicuramente uno dei metodi più agili per risolvere il sudoku classico cioè con numeri del gruppo fino a 9.
Se si generalizza per tabelle $n^2xn^2$ la procedura, con tecnica backtracking, risulta superpolinomiale!
Ricordo che esiste anche una procedura basata su una riduzione del problema della k-colorazione, ma non ricordo se l'algoritmo corrispondente sia di complessità simile (anche se di ricerca locale si parla sempre).
per la visione umana e quella dei computer, per essere precisi un computer a una "visione locale", noi (umani) abbiamo una visione globale di un problema. Da qui che nascono tutte le tecniche di ricerca locale (backtracking incluso).
PS: del problema ho trovato un post simile sul forum, se può servire: https://www.matematicamente.it/forum/sudoku-t13011.html
Se si generalizza per tabelle $n^2xn^2$ la procedura, con tecnica backtracking, risulta superpolinomiale!
Ricordo che esiste anche una procedura basata su una riduzione del problema della k-colorazione, ma non ricordo se l'algoritmo corrispondente sia di complessità simile (anche se di ricerca locale si parla sempre).
per la visione umana e quella dei computer, per essere precisi un computer a una "visione locale", noi (umani) abbiamo una visione globale di un problema. Da qui che nascono tutte le tecniche di ricerca locale (backtracking incluso).
PS: del problema ho trovato un post simile sul forum, se può servire: https://www.matematicamente.it/forum/sudoku-t13011.html
"ham_burst":
PS: del problema ho trovato un post simile sul forum, se può servire: https://www.matematicamente.it/forum/sudoku-t13011.html
Ho letto questo topic, e visto il link al "Risolutore". E' stata utilizzata la tecnica precedentemente menzionata da Amdebian. Questa tecnica è sicuramente la più facile da scrivere il codice, ma continua a non piacermi perchè "poco intelligente".
Ma è comunque sempre possibile far ricorso ai metodi usati dalle persone per risolvere il sudoku, anche quando a risolverlo è un PC. E questo genere di risolutore è in effetti utile nei casi in cui si desideri valutare la complessità di un sudoku. Giocatori più avanzati faranno infatti ricorso a tecniche più avanzate e complesse e tenendo conto delle tecniche usate dal risolutore per risolvere la griglia è possibile stabilire se era più o meno semplice da risolvere per un umano. Per lo sviluppo ci si potrebbe rifare ad esempio alle tecniche presentate in siti come questo.
"apatriarca":
Per lo sviluppo ci si potrebbe rifare ad esempio alle tecniche presentate in siti come questo.
Questo si che mi piace. Parla proprio delle varie tecniche da usare, partendo dalle più semplici, ed andando via via nel complesso.
A pagina 2, parla di "Naked Single" e "Hidden Single". Si tratta dei primi due casi, precedentemente esposti.
Ragazzi grazie delle risposte..ma volevo capire , l'algortimo di Backtracking va utilizzato per generare o per trovare la soluzione del sudoku ?
Puoi usarlo per fare entrambe le cose. Ovviamente con un algoritmo un po' diverso. Si tratta di un algoritmo molto generale che si adatta a diversi problemi. Si è principalmente discusso della ricerca di una soluzione comunque. Per generare la griglia ti direi che puoi semplicemente generare a caso ogni cella tenendo conto di quelle possibili. Se ti blocchi torni indietro e generi altri numeri casuali.
per esempio ora riesco a generare una griglia , però non riesco ad effettuare il controllo ( ogni numero deve essere presente una volta nella riga , colonna e regione ) :
int numeri_da_mettere ; /* numeri =30*DIMENSIONE/81 */
numeri_da_mettere = (30*DIMENSIONE*DIMENSIONE)/81 ;
int i , j , n , numero , S[DIMENSIONE][DIMENSIONE];
for(i=0; i[j]= 0;
}/* FINE INIZIALIZZAZIONE A 0 */
for(n=0; n< numeri_da_mettere; n++)
{/* INSERIMENTO NUMERI */
i = rand() % DIMENSIONE;
j = rand() % DIMENSIONE;
numero=rand() % DIMENSIONE ;
numero++;
S[j]=numero;
}
/* FINE INSERIMENTO NUMERI */
printf( " -------------------------");
for(i=0; i
for (j=0; j
printf("%3d",S[j]);
}
printf("\n");
printf( " -------------------------\n");
printf("\n\n");
int numeri_da_mettere ; /* numeri =30*DIMENSIONE/81 */
numeri_da_mettere = (30*DIMENSIONE*DIMENSIONE)/81 ;
int i , j , n , numero , S[DIMENSIONE][DIMENSIONE];
for(i=0; i
}/* FINE INIZIALIZZAZIONE A 0 */
for(n=0; n< numeri_da_mettere; n++)
{/* INSERIMENTO NUMERI */
i = rand() % DIMENSIONE;
j = rand() % DIMENSIONE;
numero=rand() % DIMENSIONE ;
numero++;
S[j]=numero;
}
/* FINE INSERIMENTO NUMERI */
printf( " -------------------------");
for(i=0; i
for (j=0; j
printf("%3d",S[j]);
}
printf("\n");
printf( " -------------------------\n");
printf("\n\n");
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo