Sudoku solver

[ago]

Questo weekend ho scritto un sudoku solver (serve python 2.4). Se qualcuno fosse interessato.... Il programmino e' un simpatico esercizio 1) perche' e' breve, 2) per la logica di rosoluzione del sudoku, 3) Perche' sembra funzionare .

#!/bin/python 
# 
# sudoku-solver 
# Copyright 2005 Ago, all rights reserved 
# 
m=[ 
[5, 2, 6,       8, 0, 0,      3, 7, 0], 
[3, 0, 0,       0, 9, 0,      5, 0, 0], 
[0, 8, 0,       0, 5, 0,      0, 0, 0], 

[0, 0, 0,       2, 0, 0,      0, 0, 0], 
[0, 0, 7,       0, 0, 3,      2, 0, 0], 
[8, 6, 0,       9, 0, 0,      0, 5, 0], 

[0, 0, 0,       0, 0, 0,      0, 6, 1], 
[0, 0, 0,       0, 7, 0,      0, 4, 0], 
[1, 7, 8,       6, 0, 0,      0, 0, 0], 
] 
print "\n=============================" 
for x in m: print x
set9 = set(range(1,10)) 
range9 = range(9) 
range3 = range(3) 
points = [(i,j) for i in range9 for j in range9 if m[i][j]==0] #Remaining points to be solved 
solutions = [[set() for i in range9] for j in range9] #Set of possible solutions for each point 
def f(x): return (x/3)*3 #get block first cell row/col index 
def setSolution(r, c, sol=None): 
    global doloop 
    doloop = True 
    if sol is not None: 
        print "row=", r+1, "col=", c+1, ":", sol 
        m[r][c] = sol 
        points.remove((r,c)) 
        solutions[r][c] = set() 
    for i,j in points: #Recalculate all possible solutions 
        row = set(m[i]) 
        col = set(cl[j] for cl in m) 
        block = set(m[f(i)+i2][f(j)+j2] for i2 in range3 for j2 in range3)      
        solutions[i][j] = set9.difference(row.union(col).union(block)) 
    for i,j in points: #Eliminate (im)possible solutions 
        blockrow = set([n for i2 in range3 for j2 in range3 for n in solutions[f(i)+i2][f(j)+j2] if f(i)+i2==i]).difference(set([n for i2 in range3 for j2 in range3 for n in solutions[f(i)+i2][f(j)+j2] if f(i)+i2!=i]))      
        blockcol = set([n for i2 in range3 for j2 in range3 for n in solutions[f(i)+i2][f(j)+j2] if f(j)+j2==j]).difference(set([n for i2 in range3 for j2 in range3 for n in solutions[f(i)+i2][f(j)+j2] if f(j)+j2!=j]))      
        if len(blockrow): 
            for j2 in range9: 
                if j2 not in [f(j),f(j)+1,f(j)+2]: 
                    solutions[i][j2]=solutions[i][j2].difference(blockrow) 
        if len(blockcol): 
            for i2 in range9: 
                if i2 not in [f(i),f(i)+1,f(i)+2]: 
                    solutions[i2][j]=solutions[i2][j].difference(blockcol) 
setSolution(0, 0) #Initialize 
while(doloop): #Main loop 
    doloop = False #Check if a solution is unique in row/col/block 
    for i,j in points: 
        row = set([n for k in range9 for n in solutions[i][k] if j != k]) 
        col = set([n for k in range9 for n in solutions[k][j] if i != k]) 
        block = set([n for i2 in range3 for j2 in range3 for n in solutions[f(i)+i2][f(j)+j2] if f(i)+i2 !=i or f(j)+j2 != j]) 
        for n in solutions[i][j]: 
            if len(solutions[i][j])==1 or n not in row or n not in col or n not in block: 
                setSolution(i,j,n) 
#Finished! Format output and print results 
m = [[m[i][j]and m[i][j]or [x for x in solutions[i][j]] for j in range9]for i in range9] 
for x in m: print x 

Stilisticamente il codice si potrebbe migliorare un po' usando nomi di variabili piu' significativi, ripulendo l'ultimo pezzo di setSolution, etc, etc... ma non ne avevo voglia.

[ago]

Istruzioni:

1) Installare python se non lo avete (per windows http://www.python.org/ftp/python/2.4.2/python-2.4.2.msi)
2) Copiare il codice sopra in un file di testo chiamato sudoku.py
3) Modificare la matrice ad inizio file e salvare
4) Eseguire su terminale: python sudoku.py

[Elendil]

non si potrebbe avere un commento passo passo per niubbi magari in ita

[ago]

#Logica di base:
#1) Cercare l'insieme di soluzioni ammissibili per ogni punto della matrice (vedi setSolution)
#2) Vedere (Main loop) se queste soluzioni sono "uniche" cioe' se:
#2a) una cella ammette una sola soluzione
#2b) una soluzione e' unica nella riga, colonna o blocco
#Se 2a o 2b sono vere abbiamo risolto un nuovo punto e si torna ad 1
#Si ripete il tutto finche' non c'e' piu' nulla di nuovo da fare, 
#nel qual caso abbiamo risolto oppure la matrice e irrisolvibile dati i punti iniziali
#in ogni caso abbiamo finito

#m e' la matrice iniziale
m=[
[5, 2, 6,       8, 0, 0,      3, 7, 0],
[3, 0, 0,       0, 9, 0,      5, 0, 0],
[0, 8, 0,       0, 5, 0,      0, 0, 0],

[0, 0, 0,       2, 0, 0,      0, 0, 0],
[0, 0, 7,       0, 0, 3,      2, 0, 0],
[8, 6, 0,       9, 0, 0,      0, 5, 0],

[0, 0, 0,       0, 0, 0,      0, 6, 1],
[0, 0, 0,       0, 7, 0,      0, 4, 0],
[1, 7, 8,       6, 0, 0,      0, 0, 0],
]
print "\n============================="

#Stampiamo le righe di m, si puo' anche usare "print m" 
#ma il risultato sotto e' piu' carino 
for x in m: print x

#Alcune variabili che contengono vettori di numeri usati di frequente
#rispettivamente: 1-9, 0-8, e 0-3 
#set9 non e' in realta' un vettore ma un insieme.  
#L'insieme e' un contenitore speciale che supporta 
#operazioni di insiemistica (a noi servono unione e differenza di insiemi)
set9 = set(range(1,10))
range9 = range(9)
range3 = range(3)

#points e' una lista che contine i punti della matrice m da risolvere
#in pratica m contiene i punti risolti, points i punti da risolvere
#in points ogni punto e' una coppia di variabili (i,j) 
#dove i e' la riga e j la colonna di ogni punto
#la lista viene inizializzata con i punti di m che sono = 0
#l'utilizzo di [f(x,y) for x in range1 for y in range2 if ... ] 
#e' un modo piu' sintetico per creare una lista
#invece di usare loops tradizionali. 
#Tale sintassi e' usata anche in seguito
points = [(i,j) for i in range9 for j in range9 if m[i][j]==0]

#solutions e' una matrice (stesse dimensioni di m) 
#in cui ogni punto e' un insieme di soluzioni ammissibili.
#notare che per creare la matrice si e' usato 
#[[f(x,y) for x in range] for y in range] 
#simile a quanto fatto per points ma qui si ottiene una lista di liste
#la matrice viene iniziliazzata con insiemi vuoti
solutions = [[set() for i in range9] for j in range9]

#Questa funzione (f) trasforma una riga/colonna in m 
#nella prima riga/colonna del sottoblocco corrispondente
#es 0->0, 1->0, 2->0, 3->1, 4->1...
#siccome x e' un intero x/3 e' un intero
def f(x): return (x/3)*3

#Questa funzione viene invocata per inizializzare solutions 
#ed ogni qual volta si risolve un nuovo punto.  Il suo compito e'
#1) aggiornare m (inserendo il nuovo punto) e points (eliminando il punto). 
#2) ricalcolare l'insieme delle soluzioni ammissibili (solutions) di ogni punto
def setSolution(r, c, sol=None):
    #doloop e' usato per controllare il loop principale 
    global doloop
    doloop = True

    #Se setSolution non e' chiamato in fase di inizializzazione (sol=None)
    #vengono aggiornati m, points e solutions
    if sol is not None:
        print "row=", r+1, "col=", c+1, ":", sol
        m[r][c] = sol
        points.remove((r,c))
        solutions[r][c] = set()
    
    #Per ogni punto da risolvere vengono calcolate le soluzioni ammissibili
    #Queste sono date dall'inisieme dei numeri 1-9 (set9) 
    #a cui va sottrato l'insieme dei punti gia' risolti
    #sulla stessa riga, stessa colonna, e stesso blocco
    for i,j in points: 
        row = set(m[i])
        col = set(cl[j] for cl in m)
        block = set(m[f(i)+i2][f(j)+j2] for i2 in range3 for j2 in range3)      
        solutions[i][j] = set9.difference(row.union(col).union(block))
    
    
    #Non tutte le soluzioni sopra pero' sono possibili... 
    #Alcune sono mutuamente incompatibili. Possiamo scremare.
    #Se ad es si prende l'insieme delle soluzioni ammissibili 
    #della prima riga di un blocco ed in 
    #queste appare il numero 2 come possibile soluzione,
    #ed il numero 2 non appare nell soluzioni delle altre due righe del blocco, 
    #significa che 2 deve essere nella prima riga del blocco
    #il che' significa che 2 non puo' essere nel resto della riga
    for i,j in points:
        blockrow = set([n for i2 in range3 for j2 in range3 for n in solutions[f(i)+i2][f(j)+j2] if f(i)+i2==i]).difference(set([n for i2 in range3 for j2 in range3 for n in solutions[f(i)+i2][f(j)+j2] if f(i)+i2!=i]))      
        blockcol = set([n for i2 in range3 for j2 in range3 for n in solutions[f(i)+i2][f(j)+j2] if f(j)+j2==j]).difference(set([n for i2 in range3 for j2 in range3 for n in solutions[f(i)+i2][f(j)+j2] if f(j)+j2!=j]))      
        if len(blockrow):
            for j2 in range9:
                if j2 not in [f(j),f(j)+1,f(j)+2]:
                    solutions[i][j2]=solutions[i][j2].difference(blockrow)
        if len(blockcol):
            for i2 in range9:
                if i2 not in [f(i),f(i)+1,f(i)+2]:
                    solutions[i2][j]=solutions[i2][j].difference(blockcol)

#Chiamando setSolutions senza terzo argomento 
#in pratica inizializziamo la matrice solutions        
setSolution(0, 0)

#Loop principale. Controlla per ogni punto da risolvere (i,j in points)
#e per ogni soluzione ammissibile (n) di tale punto, 
#se tale soluzione e' "unica" cioe' se:
#   2a) una cella ammette una sola soluzione: len(solutions[i][j])==1
#   2b) una soluzione e' unica nella riga, colonna o blocco. 
while(doloop):
    #Il loop si interrompe al prossimo giro 
    #una volta controllati tutti i punti a meno che non risolviamo
    #qualche nuovo punto. In tal caso doloop viene riattivato da 
    #setSolutions e facciamo un giro in piu'
    doloop = False
    #per ogni punto
    for i,j in points: 
        row = set([n for k in range9 for n in solutions[i][k] if j != k])
        col = set([n for k in range9 for n in solutions[k][j] if i != k])
        block = set([n for i2 in range3 for j2 in range3 for n in solutions[f(i)+i2][f(j)+j2] if f(i)+i2 !=i or f(j)+j2 != j])
        #per ogni soluzione ammissibile associata a quel punto
        for n in solutions[i][j]:
            #controlliamo se n e' la soluzione giusta
            if len(solutions[i][j])==1 or n not in row or n not in col or n not in block:
                #bingo! abbiamo risolto un nuovo punto
                setSolution(i,j,n)

#Finito! formattiamo l'output... Simile a quanto fatto sopra, 
#siccome non e' detto che tutti i punti vengano risolti
#inseriamo nel risultato anche le soluzioni ammissibili
m = [[m[i][j]and m[i][j]or [x for x in solutions[i][j]] for j in range9]for i in range9]
for x in m: print x 

[Elendil]

grazie grazie

[ago]

E' uscito oggi un articolo su come scrivere il sudoku solver in python (ancora devono pubblicare l'ultimo pezzo del programma). Il codice e' piu' Object Oriented di quanto avessi fatto io. http://www.linuxjournal.com/article/8729

Prendendo alcuni spunti dall'articolo ho riscritto il mio programma, in modo da utilizzare di piu' oggetti ed operazioni di insiemistica e minimizzare l'uso di indici:

#!/bin/python
#
# sudoku-solver v2
# Copyright 2005 Ago, all rights reserved
# Some ideas ripped-off from http://www.linuxjournal.com/article/8729

input="""
5 2 6   8 0 0   3 7 0
3 0 0   0 9 0   5 0 0
0 8 0   0 5 0   0 0 0

0 0 0   2 0 0   0 0 0
0 0 7   0 0 3   2 0 0
8 6 0   9 0 0   0 5 0

0 0 0   0 0 0   0 6 1
0 0 0   0 7 0   0 4 0
1 7 8   6 0 0   0 0 0
"""

def main(input):
    unsolvedCells = [ Cell(i) for i in range(81)]
    input = input.replace("-","0").replace("*","0").strip()
    for s in " ,;\n":
        input = input.replace(s,"")
    for cell,val in zip(unsolvedCells,input):
        cell.setValue(int(val))
    skimcells = [Cell.rows[i][j+i%3] for i in range(9) for j in [0,3,6]]
    nUnsolved = 82
    while len(unsolvedCells)<nUnsolved:
        nUnsolved = len(unsolvedCells)
        for c in skimcells: c.skim() 
        unsolvedCells = [c for c in unsolvedCells if not c.solved()]
    for row in Cell.rows:
            print [c.solved() and c.value or list(c.solutions) for c in row]

def range2solutions(range, excludeCell=None):
    return set (s for c in range for s in c.solutions if c is not excludeCell)
    
class Cell:
    rows    = [[] for i in range(9)]
    cols    = [[] for i in range(9)]
    subs    = [[] for i in range(9)]
    
    def __init__(self, pos):
        self.value = 0
        self.solutions = set(range(1,10))
        self.row = Cell.rows[pos/9]
        self.col = Cell.cols[pos%9]
        self.sub = Cell.subs[((pos/9)/3)*3+(pos%9)/3]
        self.row.append(self)
        self.col.append(self)
        self.sub.append(self)
    
    def solved(self):
        if self.value != 0: 
            return True
        elif len(self.solutions) == 1:
            self.setValue(self.solutions.pop())
        else:
            sol = set()
            for range in [self.row, self.col, self.sub]:
                solutions = range2solutions(range, self)
                sol = sol.union(self.solutions.difference(solutions))
            if sol: self.setValue(sol.pop())
        return self.value != 0
    
    def skim(self):
        sub = set(self.sub)
        def skimrange(range):
            range = set(range)
            subrange = sub.intersection(range)
            solsInSubXSubrange = range2solutions(sub.difference(subrange))
            solsNotInRange = range2solutions(subrange).difference(solsInSubXSubrange)
            for s in solsNotInRange:
                for c in range.difference(subrange):
                    c.solutions.difference_update(solsNotInRange)
        skimrange(self.row)
        skimrange(self.col)
    
    def setValue(self, val):
        if val: 
            self.value = val
            self.solutions = set()
            for other in self.row+self.col+self.sub:
                if other is self: continue
                other.solutions.discard(val)

main(input) 

[ago]

Il nuovo codice e' piu' prolisso ma anche piu' elegante e facile da leggere ()

Inoltre e' un buon esercizio per confrontare un approccio di progammazione funzionale ad un approccio di programmazione OO.

[ago]

Altro approccio interessante: http://aspn.activestate.com/ASPN/Coo.../Recipe/440542

In questo caso si usa la forza bruza. Si provano tutte le soluzioni finche' non se ne trova una che funziona. Il che' e' molto piu' lento, ma permette di risolvere problemi difficili senza conoscere le tecniche di riduzione. Nel mio caso le riduzioni sono esatte. Ma bisogna inserire le regole per eliminare le soluzioni, vedi ad es il metodo skim.

[ago]

Ok gente ecco il codice finale... Combina sia i miei metodi di riduzione analitica che quelli di bruta forza... Ho preso spunto dai links sopra...

Il nuovo codice e' ancora piu' object oriented ed elegante... Pythonico... Molto migliore di quello iniziale. Rispetto al codice sopra puo' risolvere sudokus di estrema difficolta' che non sono risolubili con le sole tecniche di riduzione... Non solo... Il mio codice e' 2-3 ordini di magnitudine piu' veloce di quello di ASPN (=100-1000 volte piu' veloce)...

#!/usr/bin/env python
#
# sudoku-solver version 3
#
# Some ideas ripped-off from:
# http://www.linuxjournal.com/article/8729
# http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/440542
# Pavol solver in
#    http://groups.google.com/group/comp.lang.python/browse_thread/thread/5087890f4c5e770d
#
# Copyright 2005 Ago,
# But you are free to copy, reuse, modify and distribute the code as you see fit

input='''
0,0,0,0,9,6,8,0,0
0,0,1,0,0,0,0,7,0
0,2,0,0,0,0,0,0,3
0,3,0,0,0,8,0,0,6
0,0,4,0,2,0,3,0,0
6,0,0,5,0,0,0,8,0
9,0,0,0,0,0,0,5,0
0,7,0,0,0,0,1,0,0
0,0,5,9,4,0,0,0,0
'''

from copy import deepcopy
class DeadEnd(Exception): pass
    
class Matrix:
    def __init__(self, input):
        self.changed = True
        self.rows = [[] for i in range(9)]
        self.cols  = [[] for i in range(9)]
        self.subs = [[] for i in range(9)]
        self.cells = [Cell(i,self) for i in range(81)]
        self.skimcells = [
            self.rows[i][j+i%3] for i in range(9) for j in [0,3,6]]
        input = [s in '-*' and 0 or int(s) for s in input if s not in ' ,;\n']
        for cell,val in zip(self.cells, input): cell.setValue(val)
                                    
    def solveByReduction(self):
        while True:
            self.changed = False
            for c in self.cells: c.solve()
            for c in self.skimcells: c.skim()
            if not self.changed: break

    def solveByBruteForce(self, level=0):
        lensols=[(len(c.solutions),c.pos) for c in self.cells if not c.solved]
        if not lensols: return True
        unsolved = min(lensols)[1]
        solutions = self.cells[unsolved].solutions
        matrix2 = deepcopy(self)
        for s in solutions:
            try:
                matrix2.cells[unsolved].setValue(s)
                matrix2.solveByReduction()
                if matrix2.solveByBruteForce(level+1):
                    self.update(matrix2)
                    return True
            except DeadEnd: pass
            matrix2 = deepcopy(self)
    
    def update(self, m):
        self.rows, self.cols, self.subs, self.cells, self.skimcells = \
            m.rows, m.cols, m.subs, m.cells, m.skimcells
    
    def __str__(self):
        return "\n".join(str([c for c in row ])[1:-1] for row in self.rows)


class Cell:
    def __init__(self, pos, matrix):
        self.solved = False
        self.matrix = matrix
        self.pos = pos
        self.row = matrix.rows[pos/9]
        self.col = matrix.cols[pos%9]
        self.sub = matrix.subs[((pos/9)/3)*3+(pos%9)/3]
        self.row.append(self)
        self.col.append(self)
        self.sub.append(self)
        self.solutions = set(range(1,10))
        
    def solve(self):
        if not self.solved:
            if len(self.solutions) == 1:
                self.setValue(self.solutions.pop())
            else:
                sol = set()
                for cells in [self.row, self.col, self.sub]:
                    otherSolutions = self.cells2sols(cells, self)
                    sol |= (self.solutions - otherSolutions)
                if len(sol) > 1: raise DeadEnd(3)
                if sol: self.setValue(sol.pop())
    
    def skim(self):
        submatrix = set(self.sub)
        for r in  (set(self.row), set(self.col)):
            subset1 = submatrix - r
            subset2 = r - submatrix
            solsNotIn1 = set(range(1,10)) - self.cells2sols(subset2)
            solsNotIn2 = set(range(1,10)) - self.cells2sols(subset1)
            for c in subset1: c.delSolutions(solsNotIn1)
            for c in subset2: c.delSolutions(solsNotIn2)
    
    def setValue(self, val):
        if val:
            self.solved = True
            self.solutions = set((val,))
            self.matrix.changed = True
            for other in self.row+self.col+self.sub:
                if other is self: continue
                if other.solutions == self.solutions: raise DeadEnd(1)
                other.delSolutions(self.solutions)
    
    def delSolutions(self, val):
        if not self.solved and val & self.solutions:
            self.solutions -= val
            self.matrix.changed = True
            if not self.solutions: raise DeadEnd(2)
                
    def __repr__(self):
        return str(
            self.solved and list(self.solutions)[0] or list(self.solutions))

    @staticmethod    
    def cells2sols(cells, exclude=None):
        return set(s for c in cells for s in c.solutions if c is not exclude)
            

if __name__=="__main__":
    matrix = Matrix(input)
    matrix.solveByReduction()
    matrix.solveByBruteForce()
    print matrix 

[ago]

Piccola modifica al codice ora ancor piu' veloce...

Se volete rovinare la vita di un amico appassionato al sudoku, provate a fargli risolvere:

0,0,0,0,9,6,8,0,0
0,0,1,0,0,0,0,7,0
0,2,0,0,0,0,0,0,3
0,3,0,0,0,8,0,0,6
0,0,4,0,2,0,3,0,0
6,0,0,5,0,0,0,8,0
9,0,0,0,0,0,0,5,0
0,7,0,0,0,0,1,0,0
0,0,5,9,4,0,0,0,0