Sudoku
A quanto ne so è una moda che c'è da circa un annetto (o sbaglio?)
fattostà che io c'ho provato per la prima volta oggi, e la domanda che mi è venuta spontanea è: sarà difficile creare un programmino che lo risolva? anche usando il metodo di andare a tentativi...
(è la prima volta che scrivo in questa sezione e non sono per niente un'informatico... abbiate pietà e scrivete in modo comprensibile
)
non mi interessa molto il programma esatto o il linguaggio di programmazione che intendete usare più che altro il ragionamento che fate seguire al calcolatore (se di ragionamenteo di può parlare...)
grazie
fattostà che io c'ho provato per la prima volta oggi, e la domanda che mi è venuta spontanea è: sarà difficile creare un programmino che lo risolva? anche usando il metodo di andare a tentativi...
(è la prima volta che scrivo in questa sezione e non sono per niente un'informatico... abbiate pietà e scrivete in modo comprensibile
) non mi interessa molto il programma esatto o il linguaggio di programmazione che intendete usare più che altro il ragionamento che fate seguire al calcolatore (se di ragionamenteo di può parlare...)
grazie
Risposte
semplicemente andando per tentativi, cioe':
metto nella "prima" (per esempio quella piu' in alto a sinistra) casella libera il primo numero (se le possibilita' sono da 1 a 9,per esempio metto 1);
a questo punto verifico che l'intero schema ottenuto non violi i vincoli del gioco;
se lo schema viola i vincoli del gioco torno al passo precedente e metto il numero 2, altrimenti vado nella prossima casella libera e ci metto il numero 1;
...e cosi' via...
ripetendo sempre passi in avanti e indietro sono certo di arrivare ad una soluzione (se la memoria e il tempo a disposizione non finisce prima)
scusa se ti ho descritto l'algoritmo un po' "qualitativamente" e non in modo preciso, ma ho poco tempo e cmq spero di averti dato qlke idea
ciao alessandro
metto nella "prima" (per esempio quella piu' in alto a sinistra) casella libera il primo numero (se le possibilita' sono da 1 a 9,per esempio metto 1);
a questo punto verifico che l'intero schema ottenuto non violi i vincoli del gioco;
se lo schema viola i vincoli del gioco torno al passo precedente e metto il numero 2, altrimenti vado nella prossima casella libera e ci metto il numero 1;
...e cosi' via...
ripetendo sempre passi in avanti e indietro sono certo di arrivare ad una soluzione (se la memoria e il tempo a disposizione non finisce prima)
scusa se ti ho descritto l'algoritmo un po' "qualitativamente" e non in modo preciso, ma ho poco tempo e cmq spero di averti dato qlke idea
ciao alessandro
Se ti interessa un programma semplice che lo fa
http://www.pierotofy.it/pages/download.php?filename=100p97q116r97s47t112a114i111f103g114h97n109o115l47m67b47c82d105e115u111v108z118p105q95r83s117t100a111i107f117g95h49n46o49l46m122b105c112d
http://www.pierotofy.it/pages/download.php?filename=100p97q116r97s47t112a114i111f103g114h97n109o115l47m67b47c82d105e115u111v108z118p105q95r83s117t100a111i107f117g95h49n46o49l46m122b105c112d
"codino75":
semplicemente andando per tentativi, cioe':
metto nella "prima" (per esempio quella piu' in alto a sinistra) casella libera il primo numero (se le possibilita' sono da 1 a 9,per esempio metto 1);
a questo punto verifico che l'intero schema ottenuto non violi i vincoli del gioco;
se lo schema viola i vincoli del gioco torno al passo precedente e metto il numero 2, altrimenti vado nella prossima casella libera e ci metto il numero 1;
...e cosi' via...
ripetendo sempre passi in avanti e indietro sono certo di arrivare ad una soluzione (se la memoria e il tempo a disposizione non finisce prima)
scusa se ti ho descritto l'algoritmo un po' "qualitativamente" e non in modo preciso, ma ho poco tempo e cmq spero di averti dato qlke idea
ciao alessandro
si, però un'idea del genere ce l'avevo pure io...
però se una combinazione va bene per la prima riga, la seconda, la terza, la quarta e poi alla quinti (metti caso) non ci sono più possibilità, deve ricominciare da capo. Di combinazioni ce ne sono tante... quanto ci mettà come tempo?
cioe' l'algoritmo quando trova che l'ultima scelta fatta vìola le regole del gioco ritorna indietro solo di un passo, cioe' modifica solo l'ultima scelta fatta.
cioe' se per esempio arrivo a dover riempire la decima casella e provo il numero 1, e se poi mi accorgo che sto violando le regole, tutte le assegnazioni che comprendono il numero 1 in quella casella le escludo (senza arrviare esplicitamente a generarle col mio algoritmo)
praticamente l'algoritmo costruisce il cosiddetto albero delle soluzioni, solo che (fortunatamente) per questo gioco non serve scrivere l'assegnazione completa delle caselle per escludere una certa assegnazione parziale.
quindi in questo caso si escludono interi pezzi dell'albero molto prima di arrivare alle foglie (foglia =assegnazione completa).
non so se ci sono metodi piu' rapidi, ma ad occhio non ne vedo.
cioe' se per esempio arrivo a dover riempire la decima casella e provo il numero 1, e se poi mi accorgo che sto violando le regole, tutte le assegnazioni che comprendono il numero 1 in quella casella le escludo (senza arrviare esplicitamente a generarle col mio algoritmo)
praticamente l'algoritmo costruisce il cosiddetto albero delle soluzioni, solo che (fortunatamente) per questo gioco non serve scrivere l'assegnazione completa delle caselle per escludere una certa assegnazione parziale.
quindi in questo caso si escludono interi pezzi dell'albero molto prima di arrivare alle foglie (foglia =assegnazione completa).
non so se ci sono metodi piu' rapidi, ma ad occhio non ne vedo.
Il risolutore che ho costruito io per il Sudoku funziona in backtracking, proprio come dice codino75.
Credo sia il metodo più veloce..
Guarda cos'ho trovato in Wikipedia:
Computer solutions
There are two general approaches taken in the creation of serious Sudoku-solving programs: human solving methods and rapid-style methods. Human-style solvers will typically operate by maintaining a mark-up matrix, and search for contingencies, matched cells, and other elements that a human solver can utilize in order to determine and exclude cell values.
Many rapid-style solvers employ backtracking searches, with various pruning techniques also being used in order to help reduce the size of the search tree.
Rapid solvers are preferred for trial-and-error puzzle-creation algorithms, which allow for testing large numbers of partial problems for validity in a short time; human-style solvers can be employed by hand-crafting puzzlesmiths for their ability to rate the challenge of a created puzzle and show the actual solving process their target audience can be expected to follow.
Although vanilla Sudoku puzzles (with 9×9 grid and 3×3 regions) can be solved quickly by computer, the generalization to larger grids is known to be NP-Complete. Various optimisation methods have been proposed for large grids.
Paola
Credo sia il metodo più veloce..
Guarda cos'ho trovato in Wikipedia:
Computer solutions
There are two general approaches taken in the creation of serious Sudoku-solving programs: human solving methods and rapid-style methods. Human-style solvers will typically operate by maintaining a mark-up matrix, and search for contingencies, matched cells, and other elements that a human solver can utilize in order to determine and exclude cell values.
Many rapid-style solvers employ backtracking searches, with various pruning techniques also being used in order to help reduce the size of the search tree.
Rapid solvers are preferred for trial-and-error puzzle-creation algorithms, which allow for testing large numbers of partial problems for validity in a short time; human-style solvers can be employed by hand-crafting puzzlesmiths for their ability to rate the challenge of a created puzzle and show the actual solving process their target audience can be expected to follow.
Although vanilla Sudoku puzzles (with 9×9 grid and 3×3 regions) can be solved quickly by computer, the generalization to larger grids is known to be NP-Complete. Various optimisation methods have been proposed for large grids.
Paola
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo