Sudoku Loesung finden

Stellt hier eure Projekte vor.
Internetseiten, Skripte, und alles andere bzgl. Python.
BlackJack

Beitragvon BlackJack » Sonntag 9. Oktober 2005, 22:21

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
User
Beiträge: 8
Registriert: Sonntag 15. Mai 2005, 15:07

Beitragvon ramin » Montag 10. Oktober 2005, 10:03

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.

BlackJack hat geschrieben: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

Beitragvon BlackJack » Montag 10. Oktober 2005, 22:51

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
Benutzeravatar
Olliminatore
User
Beiträge: 55
Registriert: Montag 30. Mai 2005, 16:03
Wohnort: schönsten Stadt Deutschlands
Kontaktdaten:

Beitragvon Olliminatore » Dienstag 18. Oktober 2005, 10:17

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 :P)
  1. from copy import deepcopy
  2.  
  3. Sudoku2="""
  4. 4.6.5.12.
  5. ...4....8
  6. .92....7.
  7. .2..8....
  8. 7..1.3..6
  9. ....9..4.
  10. .1....56.
  11. 2....5...
  12. .45.1.3.2
  13. """ #4_6_5_12_+___4____8+_92____7_+_2__8____+7__1_3__6+____9__4_+_1____56_+2____5___+_45_1_3_2
  14.  
  15. numbers=[]
  16. for data in Sudoku2.splitlines(9):
  17.     row=[]
  18.     if len(data)>8:
  19.         for value in data:
  20.             if value.isdigit(): row.append(int(value))
  21.             elif value=="." or value=="x": row.append(0)
  22.         numbers.append(row)
  23. Sudoku1=numbers    
  24. su_len=len(Sudoku1)
  25.  
  26. class Sudoku:
  27.  
  28.     def __init__(self, values=None):
  29.         self.Sudoku1=values
  30.         for x in self.Sudoku1: print x
  31.         givenValues=0
  32.         self.contain=[[i] for i in xrange(1,su_len+1)] ## make empty container
  33.         for x in xrange(su_len):    ## convert all values to list
  34.             for y in xrange(su_len):
  35.                 if not self.Sudoku1[x][y]: self.Sudoku1[x][y]=range(1,su_len+1)
  36.                 else:
  37.                     self.Sudoku1[x][y]=[self.Sudoku1[x][y]]
  38.                     givenValues+=1
  39.         print "given values =",givenValues
  40.         self.reduceSu(0)
  41.  
  42.     def countSu(self):
  43.         " sum all possible values for check "
  44.         printxl,printyl=[],[]
  45.         for x in xrange(su_len):
  46.             printlx,printly,printtlist=[],[],[]
  47.             for y in xrange(su_len):
  48.                 printlx.append(len(self.Sudoku1[x][y]))
  49.                 printly.append(len(self.Sudoku1[y][x]))
  50.                 printtlist.append((y+1,self.Sudoku1[x][y]))
  51.             printxl.append(sum(printlx)-su_len)
  52.             printyl.append(sum(printly)-su_len)
  53.             print printtlist
  54.         print "horizontal sum",sum(printxl),printxl  
  55.         print "vertical sum",sum(printyl),printyl
  56.         return sum(printxl)
  57.  
  58.     def NakedSingle(self,x,y,xq,xy,yq):
  59.         """Method-A For Sole Candidate"""
  60.         for i in xrange(su_len):
  61.             if i!=x: self._remove(xy,i,y)    ## clear vertical
  62.             if i!=y: self._remove(xy,x,i)    ## clear horizontal
  63.             qx,qy=divmod(i,3)
  64.             xx,yy=xq+qx,yq+qy
  65.             if (xx,yy)!=(x,y): self._remove(xy,xx,yy)  ## clear square
  66.    
  67.     def reduceSu(self,c):
  68.         """ Iter over all fields and search single values """
  69.         for x in xrange(su_len):
  70.             xq,xqr=divmod(x,3)
  71.             xq,xqr=xq*3,xqr*3
  72.             h_xcontain=deepcopy(self.contain)   ## reset the 3 containers
  73.             h_ycontain=deepcopy(self.contain)   ## for Hidden Single/Subsets
  74.             h_qcontain=deepcopy(self.contain)
  75.             h2_xSubset,h2_ySubset,h2_qSubset,h_qpair=[],[],[],[]  ## Method C2(Hidden Subset)
  76.             for y in xrange(su_len):
  77.                 xy,yx,yq=self.Sudoku1[x][y],self.Sudoku1[y][x],(y/3)*3
  78.                 if not len(xy)-1:    ## Method-A1 Naked Single Number
  79.                     h_xcontain[xy[0]-1].extend(xy*3)   ## mark container
  80.                     self.NakedSingle(x,y,xq,xy[0],yq)
  81.                 else:   ## fill container with possible values
  82.                     for i in xy: h_xcontain[i-1].append(y)
  83.                 if not len(yx)-1: h_ycontain[yx[0]-1].extend([yx[0]]*3)   ## mark
  84.                 else:
  85.                     for i in yx: h_ycontain[i-1].append(y)
  86.                 qx,qy=divmod(y,3)
  87.                 xx,yy=xq+qx,xqr+qy
  88.                 xxyy=self.Sudoku1[xx][yy]
  89.                 if not len(xxyy)-1: h_qcontain[xxyy[0]-1].extend([xxyy[0]]*3)   ## mark
  90.                 else:
  91.                     for i in xxyy: h_qcontain[i-1].append((xx,yy))  ## end A1      
  92.             for i in xrange(su_len):   ## check containers for sole/double values
  93.                 ## Solve Method A2 (Hidden Single)
  94.                 if len(h_xcontain[i])==2: self.Sudoku1[x][h_xcontain[i][1]]=[i+1]
  95.                 elif len(h_xcontain[i])==3: ## hidden double value
  96.                     h2_xSubset+=[(h_xcontain[i][1],h_xcontain[i][2],i+1)]
  97.                 if len(h_ycontain[i])==2: self.Sudoku1[h_ycontain[i][1]][x]=[i+1]
  98.                 elif len(h_ycontain[i])==3:
  99.                     h2_ySubset+=[(h_ycontain[i][1],h_ycontain[i][2],i+1)]
  100.                 if len(h_qcontain[i])==2:    ## hidden single square-value
  101.                     self.Sudoku1[h_qcontain[i][1][0]][h_qcontain[i][1][1]]=[i+1]
  102.                 ## End /Method-A /
  103.                 elif len(h_qcontain[i])==3:   ## double possible values
  104.                     (x1,y1),(x2,y2)=h_qcontain[i][1],h_qcontain[i][2]
  105.                     h2_qSubset+=[(h_qcontain[i][0],x1,y1,x2,y2)]
  106.            ## Solve Method-B1 FIXME - Block/Block and Column/Row Interactions        
  107.             for xy,x1,y1,x2,y2 in h2_qSubset:
  108.                 if x1==x2:  ## clear horizontal
  109.                     for j in xrange(su_len):
  110.                         if y1>j or j>y2: self._remove(xy,x1,j)
  111.                 elif y1==y2: ## clear vertical
  112.                     for j in xrange(su_len):
  113.                         if x1>j or j>x2: self._remove(xy,j,y1)
  114.             ## End/B Begin Solve Method-C2 - Hidden Subset
  115.             ## If two cells in the same row/column/block have only the same two candidates,
  116.                 else: h_qpair+=[(x1,y1,x2,y2,xy)]
  117.             for i in xrange(len(h_qpair)-1):
  118.                 h2=[j for j in h_qpair[i+1:] if h_qpair[i][:-1]==j[:-1]]
  119.                 if h2:
  120.                     for x1,y1 in (h_qpair[i][:2],h_qpair[i][2:4]): self.Sudoku1[x1][y1]=[h_qpair[i][-1],h2[0][-1]]
  121.             for i in xrange(len(h2_xSubset)-1):
  122.                 h2=[j for j in h2_xSubset[i+1:] if h2_xSubset[i][:2]==j[:2]]
  123.                 if h2:
  124.                     for h2_y in h2[0][:2]: self.Sudoku1[x][h2_y]=[h2_xSubset[i][2],h2[0][-1]]
  125.             for i in xrange(len(h2_ySubset)-1):
  126.                 h2=[j for j in h2_ySubset[i+1:] if h2_ySubset[i][:2]==j[:2]]
  127.                 if h2:
  128.                     for h2_x in h2[0][:2]: self.Sudoku1[h2_x][x]=[h2_ySubset[i][2],h2[0][-1]]
  129.             ## End/ Method-C2
  130.         cs=self.countSu()
  131.         if c!=cs: return self.reduceSu(cs)
  132.         ## FIXME Method-D?
  133.         for x in  xrange(su_len): ## remove low candidates from 3*square
  134.             xq=x/3*3
  135.             for x3 in  xrange(0,su_len,3):
  136.                 qx3_ls,qy3_ls=[],[]
  137.                 for y3 in  xrange(x3,3+x3):
  138.  
  139.                     if 1<len(self.Sudoku1[x][y3])<4: qx3_ls+=self.Sudoku1[x][y3]
  140.                     if 1<len(self.Sudoku1[y3][x])<4: qy3_ls+=self.Sudoku1[y3][x]
  141.                 qx3_ls=self._comSquare(qx3_ls,x,xq,x3)
  142.                 qy3_ls=self._comSquare(qy3_ls,x,xq,x3)
  143.                 for xy,xx,yy in qx3_ls: self._remove(xy,xx,yy)
  144.                 for xy,xx,yy in qy3_ls: self._remove(xy,yy,xx)
  145.         cs=self.countSu()
  146.         if c!=cs: return self.reduceSu(cs)
  147.         return
  148.  
  149.     def _comSquare(self,qx3_ls,x,xq,x3):
  150.         qx3set,qxy3=set(qx3_ls),[]
  151.         if len(qx3_ls)>6 and len(qx3set)==3 or len(qx3_ls)==4 and len(qx3set)==2:
  152.             for r in xrange(su_len):
  153.                 r1,r2=divmod(r,3)
  154.                 if r1+xq!=x: qxy3+=[[v,r1+xq,r2+x3] for v in qx3set]
  155.         return qxy3
  156.  
  157.     def _remove(self,nr,xr,yr):
  158.         try: self.Sudoku1[xr][yr].remove(nr) #;print nr,"removed from ",xr,yr
  159.         except ValueError: return
  160.  
  161. print   ## solution
  162. for x in Sudoku(Sudoku1).Sudoku1:
  163.     c=[]
  164.     for y in x:
  165.         if len(y)-1: c.append(y)
  166.         else: c+=y
  167.     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.
Zuletzt geändert von Olliminatore am Dienstag 1. November 2005, 18:45, insgesamt 1-mal geändert.
Love Jamba <!--Olliminatore-->input<?/> Boycott Jamba

Code: Alles auswählen

def olliminiert(optimiert, eliminiert, terminiert):
Benutzeravatar
Olliminatore
User
Beiträge: 55
Registriert: Montag 30. Mai 2005, 16:03
Wohnort: schönsten Stadt Deutschlands
Kontaktdaten:

Beitragvon Olliminatore » Samstag 29. Oktober 2005, 16:07

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
Love Jamba <!--Olliminatore-->input<?/> Boycott Jamba

Code: Alles auswählen

def olliminiert(optimiert, eliminiert, terminiert):

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder