SUDOKU - Tecniche Avanzate
Salve, sto implementando un solutore di sudoku che sfrutta anche alcune tecniche avanzate. In particolare mi sono impantanato sui cosiddetti Grouped X-Cycles. L'ideazione dell'algoritmo è tutt'altro che semplice, ma ho alcuni dubbi sulla "teoria" che mi impediscono di andare avanti.
Prima di esporre i miei dubbi, dal momento che si tratta di argomenti particolarmente specifici, ritengo più opportuno chiedere se c'è qualcuno che in teoria potrebbe aiutarmi.
Prima di esporre i miei dubbi, dal momento che si tratta di argomenti particolarmente specifici, ritengo più opportuno chiedere se c'è qualcuno che in teoria potrebbe aiutarmi.
Risposte
Ho realizzato un solver, ma molto artigianale,
e non contiene tutte le tecniche di risoluzione,
(ad esempio: questa di cui parli, non l'ho sviluppata).
Mi sono ritrovato, spesso, a chiedermi,
"quale tecnica utilizzare in questo caso" ?,
e la domanda non è di facile risposta,
perchè ogni tecnica prevedere una specifica "disposizione",
e quindi,
è più difficile capire quale tecnica utilizzare,
che non la soluzione della stessa.
Il mio solver, infatti, spesso, alza le mani,
nel caso gli do in pasto una "disposizione diabolica".
In estrema sintesi, mette in atto tutte le tecniche
elementari, e quando si ferma, fa partire la più bella,
la "brute force".
Ne abbiamo parlato qui:
https://www.matematicamente.it/forum/viewtopic.php?f=12&t=210305
L'utente @Supersquirrel sembra che abbia realizzato qualcosa a tal proposito.
e non contiene tutte le tecniche di risoluzione,
(ad esempio: questa di cui parli, non l'ho sviluppata).
Mi sono ritrovato, spesso, a chiedermi,
"quale tecnica utilizzare in questo caso" ?,
e la domanda non è di facile risposta,
perchè ogni tecnica prevedere una specifica "disposizione",
e quindi,
è più difficile capire quale tecnica utilizzare,
che non la soluzione della stessa.
Il mio solver, infatti, spesso, alza le mani,
nel caso gli do in pasto una "disposizione diabolica".
In estrema sintesi, mette in atto tutte le tecniche
elementari, e quando si ferma, fa partire la più bella,
la "brute force".
Ne abbiamo parlato qui:
https://www.matematicamente.it/forum/viewtopic.php?f=12&t=210305
L'utente @Supersquirrel sembra che abbia realizzato qualcosa a tal proposito.
"Umby":
Mi sono ritrovato, spesso, a chiedermi,
"quale tecnica utilizzare in questo caso" ?,
e la domanda non è di facile risposta,
perchè ogni tecnica prevedere una specifica "disposizione",
e quindi,
è più difficile capire quale tecnica utilizzare,
che non la soluzione della stessa.
Il mio solver, infatti, spesso, alza le mani,
nel caso gli do in pasto una "disposizione diabolica".
In estrema sintesi, mette in atto tutte le tecniche
elementari, e quando si ferma, fa partire la più bella,
la "brute force".
Semplicemente più tecniche si implementano più diminuisce la probabilità di ricorrere alla forza bruta, la quale verrà invocata se nessuna delle strategie consentirà di fare passi in avanti nella risoluzione dello schema. Ovviamente tutto dipende dall'implementazione, ma fondamentalmente l'ordine con cui vengono testate le strategie è più legato ad una questione di ottimizzazione che di corretto funzionamento.
"Umby":
Ne abbiamo parlato qui:
https://www.matematicamente.it/forum/vi ... 2&t=210305
L'utente @Supersquirrel sembra che abbia realizzato qualcosa a tal proposito.
Topic interessante, comunque il suddetto utente risulta non esistere più.
"Umby":
Ho realizzato un solver, ma molto artigianale,
e non contiene tutte le tecniche di risoluzione,
(ad esempio: questa di cui parli, non l'ho sviluppata).
Come già detto, si parla comunque di algoritmi abbastanza complicati, ma il punto è che mi sono bloccato su alcune questioni che riguardano la "teoria" della suddetta strategia. In pratica il problema, più che non saper come implementare, è non saper cosa implementare!
Per questo chiedevo se ci fosse qualche esperto di sudoku con cui discuterne per venire a capo della questione.
"utente__medio":
Semplicemente più tecniche si implementano più diminuisce la probabilità di ricorrere alla forza bruta, la quale verrà invocata se nessuna delle strategie consentirà di fare passi in avanti nella risoluzione dello schema.
Concordo con te,
anzi la "brute force" non dovrebbe essere MAI usata !!!
Il problema (IMHO), se hai uno schema incompleto, stabilire quale tecnica utilizzare non è cosa semplice... (ammesso che la stessa l'hai già implementata nel codice !!!! ).
"Umby":
anzi la "brute force" non dovrebbe essere MAI usata !!!
Dipende dalle finalità che uno si pone!
"Umby":
Il problema (IMHO), se hai uno schema incompleto, stabilire quale tecnica utilizzare non è cosa semplice... (ammesso che la stessa l'hai già implementata nel codice !!!! ).
Scusami, ma non sono sicuro di aver capito cosa intendi, a scanso di equivoci potresti essere più chiaro?
"utente__medio":
Scusami, ma non sono sicuro di aver capito cosa intendi, a scanso di equivoci potresti essere più chiaro?
Un caso "semplice", per essere chiaro.
Prendiamo il "naked pair" (questa tecnica è presente nel mio solver),
ci sono due numeri che si ripetono in una riga / colonna / quadrato,
a questo punto puoi associare gli stessi nelle due caselle,
ed escludere gli stessi nelle altre della riga / colonna / quadrato.
Ecco,
per poter applicare questa tecnica, devi prima "accorgerti" che sia presente di questa configurazione...
"Umby":
Ecco,
per poter applicare questa tecnica, devi prima "accorgerti" che sia presente di questa configurazione...
Continuo a non capire... è il programma che deve "accorgersene", mica tu! L'accorgersene fa parte dell'implementazione della tecnica risolutiva considerata; il programma in modo automatico deve tentare tutte le tecniche prima di ricorrere alla forza bruta. D'altronde era quello che dicevi anche tu in precedenza:
"Umby":
Il mio solver, infatti, spesso, alza le mani,
nel caso gli do in pasto una "disposizione diabolica".
In estrema sintesi, mette in atto tutte le tecniche
elementari, e quando si ferma, fa partire la più bella,
la "brute force".
Perché adesso mi sembra che tu stia dicendo il contrario?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo