Sudoku Loesung finden

[BlackJack]

Und was genau willst Du damit jetzt sagen!?

Zumal da gestern noch ein etwas anderes Sudoku stand was nicht lösbar war weil die Ausgangssituation schon die Regeln verletzte.

[ramin]

Naja, was ich sagen will: dieses Script scheint nur einfache Sudokus zu lösen - falls ich es unverständlich ausgedrückt haben sollte. Deshalb al Beispiel ein Sudoku, welches ein Mensch lösen kann (siehe Lösung) allerdings dieses Script nicht - weshalb ich meinte, dass da wohl noch etwas fehlt.

Sorry, dass ich mich beim Abtippen des Beispiel-Sudoku einmal verschrieben habe, ist aber mittlerweile wie festgestellt korrigiert.

Und was genau willst Du damit jetzt sagen!?

Zumal da gestern noch ein etwas anderes Sudoku stand was nicht lösbar war weil die Ausgangssituation schon die Regeln verletzte.

[BlackJack]

Mein Skript löst das Sudoku. Und muss wohl auch nicht weiter optimiert werden bei ca. 0.2 Sekunden auf einem "lahmen" Athlon mit 1 Ghz.

Code: Alles auswählen

bj@s8n:~/src/cvs/sandbox> time ./sudoku.py
[[[7, 5, 6, 1, 8, 4, 3, 2, 9],
 [1, 9, 4, 6, 2, 3, 7, 5, 8],
 [3, 8, 2, 9, 7, 5, 4, 1, 6],
 [9, 3, 1, 7, 5, 6, 2, 8, 4],
 [8, 6, 7, 4, 1, 2, 9, 3, 5],
 [2, 4, 5, 8, 3, 9, 6, 7, 1],
 [5, 7, 9, 2, 6, 1, 8, 4, 3],
 [4, 1, 8, 3, 9, 7, 5, 6, 2],
 [6, 2, 3, 5, 4, 8, 1, 9, 7]]]

real    0m0.197s
user    0m0.167s
sys     0m0.021s

[Olliminatore]

Tatsächlich bin ich auch fehlerhaft.
Du/Ihr habt vollkommen Recht.
Ich hatte mir damals schon fast gedacht, dass es nicht vollständig ist.
Ich bin mir ziemlich sicher dass der Artikel über Sudoku damals in Wikipedia nicht so ausführlich war. Demnach habe ich die Schnittmengen-Methode angewandt.
Glücklicher weise ist auch das letzte schwere(eindeutige) Sudokurätsel(von ramin) nach dieser Methode(ohne würfeln u Backtracking-Methode) lösbar, nachdem ich einen weiteren Kombinations-Schritt meinem Script hinzugefügt habe.
Mein Script darf natürlich nach belieben verwendet werden(zB als Referenz mehrerer Lösungswege).
[edit]
Leider kann es (immer noch) nicht die ganz schweren Sudokus lösen.
[/edit]
Noch eine Erklärung zu dem letzten Kombinationsschritt; Nachdem der Iterationsschritt keine einelementigen Kandidaten mehr erbrachte, habe ich eine Kandidatenmenge aus noch möglichen Zweierpaaren gesammelt und überprüft ob sie sich in x und y Reihe überschneiden(Quadrat wäre auch noch möglich). Dies war einzig in dem Feld 7,7 der Fall womit ich wieder ein einelementiges Feld[8] hatte, usw.
(Die container Variable wird praktisch erst nach dem 2. Funktionsdurchlauf nützlich.)

Nochmal das komplette Script; (falls es fehlerhaft ist werde ich es löschen und durch ein besseres ersetzen )

Code: Alles auswählen

from copy import deepcopy

Sudoku2="""
4.6.5.12.
...4....8
.92....7.
.2..8....
7..1.3..6
....9..4.
.1....56.
2....5...
.45.1.3.2
""" #4_6_5_12_+___4____8+_92____7_+_2__8____+7__1_3__6+____9__4_+_1____56_+2____5___+_45_1_3_2

numbers=[]
for data in Sudoku2.splitlines(9):
    row=[]
    if len(data)>8:
        for value in data: 
            if value.isdigit(): row.append(int(value))
            elif value=="." or value=="x": row.append(0)
        numbers.append(row)
Sudoku1=numbers    
su_len=len(Sudoku1)

class Sudoku:

    def __init__(self, values=None):
        self.Sudoku1=values
        for x in self.Sudoku1: print x
        givenValues=0
        self.contain=[[i] for i in xrange(1,su_len+1)] ## make empty container
        for x in xrange(su_len):    ## convert all values to list
            for y in xrange(su_len):
                if not self.Sudoku1[x][y]: self.Sudoku1[x][y]=range(1,su_len+1)
                else:
                    self.Sudoku1[x][y]=[self.Sudoku1[x][y]]
                    givenValues+=1
        print "given values =",givenValues
        self.reduceSu(0)

    def countSu(self):
        " sum all possible values for check "
        printxl,printyl=[],[]
        for x in xrange(su_len):
            printlx,printly,printtlist=[],[],[]
            for y in xrange(su_len):
                printlx.append(len(self.Sudoku1[x][y]))
                printly.append(len(self.Sudoku1[y][x]))
                printtlist.append((y+1,self.Sudoku1[x][y]))
            printxl.append(sum(printlx)-su_len)
            printyl.append(sum(printly)-su_len)
            print printtlist
        print "horizontal sum",sum(printxl),printxl  
        print "vertical sum",sum(printyl),printyl
        return sum(printxl)

    def NakedSingle(self,x,y,xq,xy,yq):
        """Method-A For Sole Candidate"""
        for i in xrange(su_len):
            if i!=x: self._remove(xy,i,y)    ## clear vertical
            if i!=y: self._remove(xy,x,i)    ## clear horizontal
            qx,qy=divmod(i,3)
            xx,yy=xq+qx,yq+qy
            if (xx,yy)!=(x,y): self._remove(xy,xx,yy)  ## clear square
    
    def reduceSu(self,c):
        """ Iter over all fields and search single values """
        for x in xrange(su_len):
            xq,xqr=divmod(x,3)
            xq,xqr=xq*3,xqr*3
            h_xcontain=deepcopy(self.contain)   ## reset the 3 containers
            h_ycontain=deepcopy(self.contain)   ## for Hidden Single/Subsets
            h_qcontain=deepcopy(self.contain)
            h2_xSubset,h2_ySubset,h2_qSubset,h_qpair=[],[],[],[]  ## Method C2(Hidden Subset)
            for y in xrange(su_len):
                xy,yx,yq=self.Sudoku1[x][y],self.Sudoku1[y][x],(y/3)*3
                if not len(xy)-1:    ## Method-A1 Naked Single Number
                    h_xcontain[xy[0]-1].extend(xy*3)   ## mark container
                    self.NakedSingle(x,y,xq,xy[0],yq)
                else:   ## fill container with possible values
                    for i in xy: h_xcontain[i-1].append(y)
                if not len(yx)-1: h_ycontain[yx[0]-1].extend([yx[0]]*3)   ## mark
                else:
                    for i in yx: h_ycontain[i-1].append(y)
                qx,qy=divmod(y,3)
                xx,yy=xq+qx,xqr+qy
                xxyy=self.Sudoku1[xx][yy]
                if not len(xxyy)-1: h_qcontain[xxyy[0]-1].extend([xxyy[0]]*3)   ## mark
                else:
                    for i in xxyy: h_qcontain[i-1].append((xx,yy))  ## end A1      
            for i in xrange(su_len):   ## check containers for sole/double values
                ## Solve Method A2 (Hidden Single)
                if len(h_xcontain[i])==2: self.Sudoku1[x][h_xcontain[i][1]]=[i+1]
                elif len(h_xcontain[i])==3: ## hidden double value
                    h2_xSubset+=[(h_xcontain[i][1],h_xcontain[i][2],i+1)]
                if len(h_ycontain[i])==2: self.Sudoku1[h_ycontain[i][1]][x]=[i+1]
                elif len(h_ycontain[i])==3:
                    h2_ySubset+=[(h_ycontain[i][1],h_ycontain[i][2],i+1)]
                if len(h_qcontain[i])==2:    ## hidden single square-value
                    self.Sudoku1[h_qcontain[i][1][0]][h_qcontain[i][1][1]]=[i+1]
                ## End /Method-A /
                elif len(h_qcontain[i])==3:   ## double possible values
                    (x1,y1),(x2,y2)=h_qcontain[i][1],h_qcontain[i][2]
                    h2_qSubset+=[(h_qcontain[i][0],x1,y1,x2,y2)]
           ## Solve Method-B1 FIXME - Block/Block and Column/Row Interactions        
            for xy,x1,y1,x2,y2 in h2_qSubset:
                if x1==x2:  ## clear horizontal
                    for j in xrange(su_len): 
                        if y1>j or j>y2: self._remove(xy,x1,j)
                elif y1==y2: ## clear vertical
                    for j in xrange(su_len):
                        if x1>j or j>x2: self._remove(xy,j,y1)
            ## End/B Begin Solve Method-C2 - Hidden Subset
            ## If two cells in the same row/column/block have only the same two candidates,
                else: h_qpair+=[(x1,y1,x2,y2,xy)]
            for i in xrange(len(h_qpair)-1):
                h2=[j for j in h_qpair[i+1:] if h_qpair[i][:-1]==j[:-1]]
                if h2:
                    for x1,y1 in (h_qpair[i][:2],h_qpair[i][2:4]): self.Sudoku1[x1][y1]=[h_qpair[i][-1],h2[0][-1]]
            for i in xrange(len(h2_xSubset)-1):
                h2=[j for j in h2_xSubset[i+1:] if h2_xSubset[i][:2]==j[:2]]
                if h2:
                    for h2_y in h2[0][:2]: self.Sudoku1[x][h2_y]=[h2_xSubset[i][2],h2[0][-1]]
            for i in xrange(len(h2_ySubset)-1):
                h2=[j for j in h2_ySubset[i+1:] if h2_ySubset[i][:2]==j[:2]]
                if h2:
                    for h2_x in h2[0][:2]: self.Sudoku1[h2_x][x]=[h2_ySubset[i][2],h2[0][-1]]
            ## End/ Method-C2
        cs=self.countSu()
        if c!=cs: return self.reduceSu(cs)
        ## FIXME Method-D? 
        for x in  xrange(su_len): ## remove low candidates from 3*square
            xq=x/3*3
            for x3 in  xrange(0,su_len,3):
                qx3_ls,qy3_ls=[],[]
                for y3 in  xrange(x3,3+x3):

                    if 1<len(self.Sudoku1[x][y3])<4: qx3_ls+=self.Sudoku1[x][y3]
                    if 1<len(self.Sudoku1[y3][x])<4: qy3_ls+=self.Sudoku1[y3][x]
                qx3_ls=self._comSquare(qx3_ls,x,xq,x3)
                qy3_ls=self._comSquare(qy3_ls,x,xq,x3)
                for xy,xx,yy in qx3_ls: self._remove(xy,xx,yy)
                for xy,xx,yy in qy3_ls: self._remove(xy,yy,xx)
        cs=self.countSu()
        if c!=cs: return self.reduceSu(cs)
        return

    def _comSquare(self,qx3_ls,x,xq,x3):
        qx3set,qxy3=set(qx3_ls),[]
        if len(qx3_ls)>6 and len(qx3set)==3 or len(qx3_ls)==4 and len(qx3set)==2:
            for r in xrange(su_len):
                r1,r2=divmod(r,3)
                if r1+xq!=x: qxy3+=[[v,r1+xq,r2+x3] for v in qx3set]
        return qxy3

    def _remove(self,nr,xr,yr):
        try: self.Sudoku1[xr][yr].remove(nr) #;print nr,"removed from ",xr,yr
        except ValueError: return

print   ## solution
for x in Sudoku(Sudoku1).Sudoku1:
    c=[]
    for y in x:
        if len(y)-1: c.append(y)
        else: c+=y
    print c

[edit]
Einen anderen Datentyp als "list" zu nehmen, lohnt sich glaube ich nicht bei der Kurze der Listen. Ich wüsste jetzt auch nicht, wo ich "yield" verwenden könnte.

[Olliminatore]

Ich hätte nie gedacht, dass Sudoku so komplex wird wenn man es logisch lösen will. So viele Techniken/Methoden sind notwendig um schwere Sudokus (logical no"guess") zu lösen. Auf englischen Seiten stößt man auf Begriffe wie Seafood, X-Wing, Swordfish, Jellyfish, Squirmbag...
(Die eben genannten Techniken sind nicht in meinem Script implementiert, nur die Einfachsten.)
Es hat auch noch niemand alle Methoden gefunden(um alle zu lösen). Hier ein Paar Links die sich damit beschäftigen:

Sudoku Solver Group by logic
Technik Erläuterungen
Sudoku Programmers Forum
(Dort im Forum ist auch der deutsche Autor des auf Wikipedia verlinkten Sudoku-Solvers.)

Mein obiges Script ist auch in soweit noch nicht fertig, dass es "Dreier Paare" in der Methode-B/C erkennt. Ich bin auch bloß ein Hobby Programmierer und habe mein PythonWissen von hier, es war faszinierend, man hat nachgedacht, dazu gelernt, es hat Spaß gemacht. (Würde mich freuen wenn jemand drauf aufbaut oder weiter führt und zeigt wie gut Python ist.) Meine Freunde haben mir leider verboten weiter zu machen.
Ende