Ultimo aggiornamento: 15-05-2014
Durante l’ultima sessione di corsi, ho seguito Agoritmi 2, in cui il prof per spiegarci il BackTrack c’ha fatto implementare in python un sudoku solver, basandosi sugli appunti di Norving, che usa backtrack con constraint propagation.
Base
Io ho scritto il programma con una euristica diversa dalla sua: non uso la propagazione dei vincoli (e che lo facevo uguale :P) e non risolvo solo per sottogriglie, ma vado a vedere la colonna o la riga o la sottogriglia che ha il maggior numero di numeri già inseriti e lì vado a tentare l’inserimento di un nuovo numero, ovviamente il tutto ottimizzato usando le hash table (usando la funzione set in python) in modo da non contare ogni volta il numero di elementi presenti.
Con questi meccanismi rapportato all’algoritmo di Norving “mi difendo”, non ho performance così elevate, però riesco a risolvere i suoi hardest sudoku anche in 0.03 secondi, ma a volte anche di più (parlo di secondi e molti a volte):
Solution computed . . . 9 2 . . . . 3 8 7 9 2 6 4 1 5 . . 6 8 . 3 . . . 5 4 6 8 1 3 9 7 2 1 9 . . 7 . . . 6 1 9 2 4 7 5 8 3 6 2 3 . . 4 . 1 . . 2 3 5 7 4 9 1 6 8 . . 1 . . . 7 . . 9 6 1 2 5 8 7 4 3 . . 8 . 3 . . 2 9 4 7 8 6 3 1 5 2 9 7 . . . 8 . . 9 1 7 5 4 3 8 2 6 9 1 . . . 5 . 7 2 . . 6 1 3 5 9 7 2 8 4 . . . . 6 4 . . . 8 2 9 1 6 4 3 5 7 Number of recursive calls: 735 In 0.0366179943085 seconds .. Solution computed 7 . . . . . 4 . . 7 9 8 6 3 5 4 2 1 . 2 . . 7 . . 8 . 1 2 6 9 7 4 5 8 3 . . 3 . . 8 . 7 9 4 5 3 2 1 8 6 7 9 9 . . 5 . . 3 . . 9 7 2 5 8 6 3 1 4 . 6 . . 2 . . 9 . 5 6 4 1 2 3 8 9 7 . . 1 . 9 7 . . 6 3 8 1 4 9 7 2 5 6 . . . 3 . . 9 . . 6 1 7 3 5 2 9 4 8 . 3 . . 4 . . 6 . 8 3 5 7 4 9 1 6 2 . . 9 . . 1 . 3 5 2 4 9 8 6 1 7 3 5 Number of recursive calls: 3595 In 0.172569036484 seconds
Però i suoi hard (i top95), a volte, il mio algoritmo li risolve anche in 200 secondi o più, ma a volte in meno (si veda dopo), un esempio:
Solution computed 6 . . . . . 8 . 3 6 1 7 4 5 9 8 2 3 . 4 . 7 . . . . . 2 4 8 7 3 6 9 1 5 . . . . . . . . . 5 3 9 1 2 8 4 6 7 . . . 5 . 4 . 7 . 9 8 2 5 6 4 3 7 1 3 . . 2 . . . . . 3 7 4 2 9 1 5 8 6 1 . 6 . . . . . . 1 5 6 8 7 3 2 9 4 . 2 . . . . . 5 . 8 2 3 6 4 7 1 5 9 . . . . 8 . 6 . . 7 9 1 3 8 5 6 4 2 . . . . 1 . . . . 4 6 5 9 1 2 7 3 8 Number of recursive calls: 4647810 In 222.295469999 seconds
Fin qui tutto oki, un programmino normale, però ho deciso di piazzarci un pò di randommizzazione, giusto per divertirmi un pò e per vedere quello che ci potevo tirar fuori.
Randomizzazione
La randomizzazione l’ho piazzata in due punti:
- Quando vado a scegliere il numero da provare nella cella vuota trovata: non provo sempre la sequenza di numeri da 1 a 9, ma ogni volta computo una permutazione diversa.
- Nel caso che ci sia una riga o una colonna o una sottogriglia che abbiano lo stesso numero di elementi già inseriti, vado a scegliere chi usare a caso (si potrebbe provare anche nella selezione della cella vuota, nel caso due abbiano lo stesso numero, massimo, di valori da non provare per trovare la soluzione).
In base a questo meccanismi ho lanciato il programma su una lista breve di sudoku, per più volte ed ho trovato soluzioni inaspettate, almeno per me, tipo: il sudoku hard, riportato sopra lo risolve anche in 1 secondo:
Solution computed 6 . . . . . 8 . 3 6 1 7 4 5 9 8 2 3 . 4 . 7 . . . . . 2 4 8 7 3 6 9 1 5 . . . . . . . . . 5 3 9 1 2 8 4 6 7 . . . 5 . 4 . 7 . 9 8 2 5 6 4 3 7 1 3 . . 2 . . . . . 3 7 4 2 9 1 5 8 6 1 . 6 . . . . . . 1 5 6 8 7 3 2 9 4 . 2 . . . . . 5 . 8 2 3 6 4 7 1 5 9 . . . . 8 . 6 . . 7 9 1 3 8 5 6 4 2 . . . . 1 . . . . 4 6 5 9 1 2 7 3 8 Number of recursive calls: 23558 In 1.09461808205 seconds
Quindi a seconda se sceglie di operare su una colonna|riga|sottogriglia, una volta trovata la cella su cui inserire un valore scelto a random, s’hanno risultati sempre diversi.
Non volendo arrivare a parlare di statistica: l’algoritmo con delle scelte (sbagliate) risolve in più tempo l’algoritmo: nel peggiore dei casi quando gli manca una sola cella, vede che lì non ci può mettere nessun numero e quindi torna indietro (back-track per l’appunto) e finchè non trova la strada giusta, e nel peggiore dei casi, non c’è una soluzione, può eseguire tutte le permutazioni possibili, che nel caso del sudoku 9×9: sono ((9×9)-(numeri già fissati))! circa, perchè l’algoritmo dato non prova in una cella vuota un numero già presente sulla stessa riga|colonna|sottogrigia, quindi di permutazioni ne farà molte di meno.
Parallelizzazione
A questo punto m’è venuta un’ idea: perchè non eseguo più sudoku solver in parallelo in modo che almeno uno non eseguirà una strada molto lunga per trovare una soluzione, o vista da un’altra prospettiva: ci sarà uno che troverà una strada più corta degli altri.
Dato che ho tutto in python e che per fortuna ho quad core intel, però senza tecnologia hyper-threading (con la quale un core può eseguire più thread parallelamente), ho deciso di optare per l’interprete jython 2.7, poichè questo non ha il GIL di python (il GIL permette di eseguire solo un thread per volta, su qualsiasi architettura) e così posso utilizzare anche le classi di java per la concorrenza: ExecutorService in primis, che implementa il metodo: invokeAny(collection Callable) il quale prende come argomenti una collezione di thread, li esegue e ritorna il valore del primo thread che termina.
In linguaggio java il risultato di un thread è un oggetto Future<?> e un thread che ritorna un valore viene rappresentato con l’interfaccia Callable<?> . Ora ci servirà solo Callable.
Quanti thread da eseguire per risolvere il sudoku?
Dato che ho un quad core (ma non l’hyperthreading), di cui uno in teoria lo tiene occupato solo l’OS ed il main del programma, diciamo ne ho 3 liberi; per fruttare al meglio il multi-tasking, facciamo che ne lancio 6, due thread per core. Su Windows con questa configurazione mi da il 90% di cpu usata (segnalo la legge di Amdahl anche se non l’ho usata qui).
Codice
Arrivo al sodo, ecco quindi il codice per jython usato: prima di tutto ho cambiato il metodo BackTrack di SearchProblem.py in modo da inserire un variabile, che se attivata interrompe il thread su cui runna: non è stiloso, però funziona ed è veloce.
import java.lang.Thread
....
def BackTrack(self,Empty=None):
if self.goOn == False:
Thread.currentThread().interrupt() #brute stops!
...
Poi ho fatto un file python (jSudoku.py) dove importo la classe implementata per risolvere il sudoku: BetterSudoku, dove ho creato un classe che implementa Callable che lo incapsula:
from bet_sudoku import BetterSudoku
from java.util.concurrent import Callable
class BSThread(Callable):
def __init__(self, line):
self.problem=BetterSudoku(line)
def call(self):
if self.problem.BackTrack():
print self.problem #stampo il sudoku risolto
else:
print "no solution\n" #non è un sudoku con soluzione
return True
def stop(self): #per fermare l'esecuzione del thread
self.problem.goOn=False
Infine il main:
import sys
from java.util.concurrent import Executors, TimeUnit, TimeoutException
import time
if __name__ == "__main__":
with open(sys.argv[1]) as myfile:
for line in myfile:
print "\nTrying to solve sudoku"
try:
start_time=time.time()
pool = Executors.newFixedThreadPool(6)
threads = [BSThread(line) for t in xrange(6)] #creo la collection di callable
futures = pool.invokeAny(threads) #eseguo i thread in parallelo
#se sto qui un thread ha finito
tot_time = time.time() - start_time
for p in threads: #killo i thread ancora attivi
p.stop()
pool.shutdownNow()
print "Total time: %f seconds"%tot_time
except RuntimeError as e:
print e
In questo modo, saremo al sicuro dall’eseguire la strada proprio sbagliata, anzi se abbiamo fortuna potremmo risolvere i sudoku in breve tempo, ovviamente più thread eseguiamo e più possibilità abbiamo,
Ecco a voi tutto il progetto: sudokuRandomParallel, ovvimanete c’è da scaricare l’interprete jython e dopo si può eseguire il programma jSudoku.py passandogli come argomento un file txt con i sudoku da risolvere.
Infine potremmo fare una piccola modifica al codice del main:
si può invocare invokeAny dicendogli quanti secondi aspettare: pool.invokeAny(threads, 30, TimeUnit.SECONDS), in questo caso 30 (si ricordi di gestire l’eccezione TimeoutException) e si può inserire un loop in cui si può vedere dopo quanti tentativi, si trova un thread che risolve un sudoku in meno di 30 secondi.
Io ho provato ad usare il loop di invokeAny sul sudoku più difficile trovato da Norving, e non sono riuscito a risolverlo provando con 100 cicli, (c’ho provato solo due volte): si vede che è proprio difficile da risolvere quello =)