[C++] Risolvere Sudoku

[ka0s]

Oggi ho visto sul giornale sto gioco e mi sono prefisso, come esercizio di programmazione, di riuscire a fare un programma che, dati i numeri iniziali, completi il resto della tabella...
Il problema è che non so da che parte analizzare il problema... [tra l'altro non ci ho mai giocato :P] però il meccanismo è piuttosto semplice...

quindi chiedo a voi se avete qualche suggerimento o qualche idea su come implementare un algoritmo o simile...

grazie in anticipo!

[Darecon]

Azz, servirebbe anche a me

[subvertigo]

ogni casella del sudoku la vedi come un array di 9 interi da 1 a 9.
Fai un ciclo che passa tutte le caselle e che ad ogni passata "barra" i numeri delle varie caselle (sia sulla riga, sia sulla colonna, sia nel riquadro) che NON possono essere. Ogni volta che rimane un solo numero nell'array della casella allora quello sarà il definitivo.
Il ciclo termina quando dopo una passata non ci sono differenze.

Tuttavia credo proprio che questo algoritmo compia una risoluzione parziale (cioè non riesce a risolverlo tutto)... dopo bisogna applicare altri algoritmi. Se non si riesce a trovarne di migliori, la forza bruta (provi numeri a caso, quando hai contraddizione rifai, altrimenti è giusto)....

[Furla]

il problema è proprio che a volte certi ragionamenti nella risoluzione saltano all'occhio dopo un po' ad un essere pensante, mentre ad un computer non gli passa neanche dalla ram di seguire un procedimento logico ma non previsto dall'algoritmo che sta processando... parlo da accanito risolvitore dei sudoku "diabolici" del corriere (tanto me lo regalano...), per prevedere proprio TUTTO ci vogliono parecchie prove e "campi di allenamento" per il programma, in modo da vedere dove si ferma e trovare il modo di risolverlo prima dal punto di vista umano e poi dal punto di vista della macchina.

altrimenti si va di bruteforce mettendo numeri random cercando che tutto torni da sè, ma specialmente all'inizio ci sono migliaia di possibilità...

[Ziosilvio]

Purtroppo per ka0s, il Sudoku è NP-completo.
Per cui: o non esiste alcun modo generale per risolvere velocemente uno schema di Sudoku arbitrario, oppure RSA è crackabile in tempo polinomiale.

[redcloud]

Ecco questo http://www.salcappalonga.it/sudoku/

e questo http://www.dcs.warwick.ac.uk/~pwg/cs301/sudoku.html

[ka0s]

Grazie per i link e per le risposte!
Però non ho ben capito cosa voglia dire che il sudoku è NP-completo... tra l'altro mi sfugge anche il significato di "tempo polinomiale"... vuol dire che non si può risolvere in un tempo accettabile per l'uomo?
In effetti usando il metodo del brute force le combinazioni sono una marea... ma in ogni caso credo che un metodo per risolverlo esista (magari per gli schemi semplici o intermedi soltanto). In giro ci sono dei programmi che lo fanno... però volevo capire come si potesse implementare in un prog in c++!

[marco.r]

Originariamente inviato da ka0s

Grazie per i link e per le risposte!
Però non ho ben capito cosa voglia dire che il sudoku è NP-completo... tra l'altro mi sfugge anche il significato di "tempo polinomiale"... vuol dire che non si può risolvere in un tempo accettabile per l'uomo?
In effetti usando il metodo del brute force le combinazioni sono una marea... ma in ogni caso credo che un metodo per risolverlo esista (magari per gli schemi semplici o intermedi soltanto). In giro ci sono dei programmi che lo fanno... però volevo capire come si potesse implementare in un prog in c++!

Il problema e' complesso quando hai la griglia vuota (ovvero per chi ti deve preparare il gioco), se devi risolverlo hai gia' diversi indizi e si puo' fare con un numero limitato di calcoli (e d''altra parte deve essere in grado di risolverlo una persona).
L'idea di provare tutte le combinazioni non e' sbagliata del tutto, basta partire con le piu' probabili (e quindi le posizioni certe in primis), ed e' quello che in effetti fa una persona quando lo risolve a mano.
Una implementazione naive dell'algoritmo potrebbe essere la seguente (in python, con alcune funzioni accessorie omesse):

def risolviSudoku( celleLibere ):
    """
    Prendi una cella libera, e togli dalle altre rimanenti tutte le incompatibili.
    torna una lista con la cella scelta e la soluzione ricorsiva delle celle rimanenti
    """
    for cella  in ordina(celleLibere):
        (riga,colonna,numero) = cella
        compatibili = [ (r,c,n) for (r,c,n) in celleLibere if (r,n) != (riga,numero) and (c,n) != (colonna,numero) and (riga,colonna) != (r,c) and ( box(r,c) , n ) != (box(riga,colonna) , numero )]
        resto = risolviSudoku( compatibili )
        if resto != None:
            return [ (riga,colonna,numero) ] + resto
    return None

def sudoku( celleIniziali, dimensione ):
    tutte = tutteLeCelle(dimensione)
    libere = sottrai( tutte , celleIniziali )
    return risolviSudoku( libere )

Il codice e' la trasposizione abbastanza pedissequa dell'idea:
- ordina le possibili celle (intesa come una terna (riga,colonna,numero) ) dalle piu' probabili alle meno probabili
- prendine una, togli dalle altre tutte quelle incompatibili con questa e ripeti la procedura

Il trucco e' tutto nella funzione ordina, che fa si' che il programma provi prima le caselle dove ci sono meno alternative in modo da limitare il danno in caso di errore.
Con i problemi delle rivista questo vuol dire di solito che per la maggior parte delle caselle si tratta di scegliere tra uno o due valori, per cui la soluzione si trova con una certa velocita'.
Disclaimer: non ho ancora provato il codice, non mi assumo la responsabilita' per eventuali errori

[vlacus]

Il fatto che il sudoku sia difficile da risolvere perchè NP-completo è una cavolata, in quanto lo schema non dipende da nessun parametro essendo sempre un 9x9 e quindi nessuno ci vieta di risolverlo in tempo costante.

[Minelab]

Io l'ho scritto (ad Agosto all'apice della sua popolarità) con il VB di Excel con il seguente algoritmo.
Per ogni casella vuota ricerca solo i numeri che possono essere inseriti in base a riga, colonna e riquadro. Nel caso il risultato fosse un solo numero la casella vene riempito. Il ciclo continua finchè ci sono caselle da riempire.
Con solo questa parte di codice si riescono a risolvere gli schemi Facile Medio e Difficile (almeno quelli che ho provato io).
Per il Diabolico invece non è sufficiente e occorre passare alla forza bruta. Per limitare al minimo il numero di combinazioni possibili ho seguito la seguente strada: per ogni casella rimasta vuota ho memorizzato i possibili numeri inseribili ed ho cominciato ad estrarli casualmente. Mi sono però accorto che anche così i tempi sono biblici.
Probabilmente, visto che l'ho implementata ma solo testata inserendo il numero a mano, la via corretta è quella di individuare se c'è una casella che possa accettare solo 2 numeri. A questo punto se ne inserisce uno e si applica la prima parte del codice (per intedenrci quello risolve i primi 3 gradi di difficoltà) e se è quello corretto il gioco è risolto. In caso contrario si inserisce l'altro.
Quest'ultima parte non ho avuto modo di testarla a fondo quindi non so se funzioni sempre anche perchè poi ho abbandonato per dedicarmi allo sviluppo di database con Access.

[marco.r]

Originariamente inviato da marco.r

Disclaimer: non ho ancora provato il codice, non mi assumo la responsabilita' per eventuali errori

e in effetti ho dimenticato un paio di cosette, come accorgersi quando la soluzione viene trovata
stasera se ho tempo la sistemo :P

[FedeX_65246X]

Avevo fatto un programmino Java (o C#, non ricordo) con algoritmo forza bruta; le tabelle 9x9 sono così piccole che possono essere risolte rapidamente anche con algoritmi "stupidi".

[ka0s]

grazie per le risp
vedrò quel che riesco a fare

[Furla]

ora lo faccio anche io in vb.net

cmq spesso quando l'"eliminazione per caselle certe" non è sufficiente si passa all'eliminazione per caselle certe a coppie o a tre", o basandosi sul fatto che nessuna altra casella della stessa riga/colonna/quadrato accetta un certo numero. quindi algoritmi "advanced" per la risoluzione di schemi più difficili si possono sviluppare su queste logiche. certo che se non si sanno risolvere manualmente gli schemi più difficili, è difficile fare un algoritmo "non bruteforce" (ovvero che non rischi di metterci più di un essere umano a risolverlo) che li risolva.

[FedeX_65246X]

Originariamente inviato da Furla

certo che se non si sanno risolvere manualmente gli schemi più difficili, è difficile fare un algoritmo "non bruteforce" (ovvero che non rischi di metterci più di un essere umano a risolverlo) che li risolva.

Per la cronaca, il sudoku pubblicato qui
(Figura 2, a sinistra), viene "brillantemente" risolto dal mio programmino in soli 3981602 tentativi, quando si dice forza bruta...

[vlacus]

a me lo stesso lo fa con 63 tentativi

[FedeX_65246X]

Mmh, azzecca tutti i numeri al primo colpo?
Non male...

[vlacus]

si ma sotto c'è una "precomputazione" bella tosta ...

[marco.r]

Originariamente inviato da vlacus

si ma sotto c'è una "precomputazione" bella tosta ...

Anche il programma di FedeX_65246X ha una precomputazione bella tosta (circa 40000000 di mosse) per poi dare la soluzione al primo colpo

[wisher]

dal punto di vista matematico si tratta di risolvere un sistema in 89 incognite, una x ogni casella.
il sistema deve eguagliare ogni linea e ogni riquadro alla somma dei numeri da 1 a 9