Python-Codebeispiel zur Implementierung des Sudoku-Lösungsprogramms

Vor kurzem nehme ich meine Kinder mit, um Sudoku zu lernen. Ich habe online nach Lösungen für verwandte Programme gesucht. Ich hoffe, dass es für alle hilfreich ist, Python zu lernen.

Ich habe zufällig ein Programm entdeckt, das mit dem Linux-System geliefert wird. Ich habe das Sudoku-Spiel geöffnet und ein paar Spiele gespielt. Leider bin ich ein Sudoku-Neuling und habe noch nie Sudoku gespielt, und ich konnte nicht einmal ein paar Schritte machen, bevor ich ins Schlamassel geriet.

Also hatte ich vor, die starke Rechenleistung des Computers zu nutzen, um Sudoku gewaltsam zu lösen, was ziemlich viel Spaß machte.

Im Folgenden werden einige meiner Ideen und Erfahrungen beim Schreiben von Sudoku-Programmen festgehalten.

1. Grundlegende Lösung für das Sudoku-Spiel

Programmieren im Allgemeinen ist eine Methodik. Unabhängig vom Programm muss der Problemlösungsprozess in mehrere einfache Methoden unterteilt werden, die der Computer umsetzen kann. Wie das Sprichwort sagt: Einfachheit führt zu Größe. Für einen Computer, der nur 0 und 1 verstehen kann, ist es umso notwendiger, die Schritte zu unterteilen und das Problem Schritt für Schritt zu lösen.

Lassen Sie uns zunächst über die Grundkonzepte zum Lösen von Sudoku nachdenken.

Sudoku hat insgesamt 81 Gitter, neun horizontal und neun vertikal, und ist in 9 Gitter mit neun Quadraten unterteilt. Die Regeln sind einfach: Die Zahlen in jedem Raster müssen sicherstellen, dass es in den horizontalen und vertikalen Reihen und im Neunquadrat-Raster keine identischen Zahlen gibt.

Unsere allgemeine Idee besteht also darin, zu versuchen, die Zahl ab der ersten Lücke einzutragen, beginnend mit 1. Wenn 1 die Anforderung von neun horizontalen und vertikalen Quadraten ohne Wiederholung nicht erfüllt, dann füllen Sie 2 aus und so weiter on Analog dazu wird diese Zelle unterbrochen, bis eine Zahl ausgefüllt ist, die vorübergehend den Regeln entspricht, und der Vorgang wird wiederholt, indem zum nächsten Feld gewechselt wird.

Wenn Sie ein bestimmtes Feld erreichen und feststellen, dass es unzählige Optionen gibt, bedeutet dies, dass das vorherige Feld falsch ausgefüllt wurde. Kehren Sie dann zum vorherigen Feld zurück und versuchen Sie es mit 9 aus dem vorherigen Feld, bis Sie zurückkehren Gehen Sie an dieser Stelle zum falschen Feld.

Auf diese Weise können wir die wichtigen Schritte regeln:

•Finden Sie das nächste Leerzeichen
•Fügen Sie abwechselnd die Zahlen 1 bis 9 in die Zelle ein
•Rekursiv beurteilen, ob die eingegebene Zahl den Regeln entspricht

2. Programm

Zunächst verwendet der Sudoku-Test ein Programm, das von der finnischen Mathematikerin Inkara entwickelt wurde 3 Monate Das schwierigste Sudoku, das jemals auf der Welt erstellt wurde. Wie folgt:

stellt das Leerzeichen mit 0 dar und stellt das Sudoku als verschachtelte Liste dar, sodass die Anzahl der Zeilen und Spalten jedes Rasters genau der entsprechenden Anzahl jedes Rasters entspricht Raster in der Liste.

Das Programm lautet wie folgt:

 #coding=utf-8
 import datetime
 class solution(object):
   def __init__(self,board):
     self.b = board
     self.t = 0
 
   def check(self,x,y,value):#检查每行每列及每宫是否有相同项
     for row_item in self.b[x]:
       if row_item == value:
         return False
     for row_all in self.b:
       if row_all[y] == value:
         return False
     row,col=x/3*3,y/3*3
     row3col3=self.b[row][col:col+3]+self.b[row+1][col:col+3]+self.b[row+2][col:col+3]
     for row3col3_item in row3col3:
       if row3col3_item == value:
         return False
     return True
 
   def get_next(self,x,y):#得到下一个未填项
     for next_soulu in range(y+1,9):
       if self.b[x][next_soulu] == 0:
         return x,next_soulu
     for row_n in range(x+1,9):
       for col_n in range(0,9):
         if self.b[row_n][col_n] == 0:
           return row_n,col_n
     return -1,-1 #若无下一个未填项，返回-1
 
   def try_it(self,x,y):#主循环
     if self.b[x][y] == 0:
       for i in range(1,10):#从1到9尝试
         self.t+=1
         if self.check(x,y,i):#符合 行列宫均无条件 的
           self.b[x][y]=i #将符合条件的填入0格
           next_x,next_y=self.get_next(x,y)#得到下一个0格
           if next_x == -1: #如果无下一个0格
             return True #返回True
           else:    #如果有下一个0格，递归判断下一个0格直到填满数独
             end=self.try_it(next_x,next_y)
             if not end:  #在递归过程中存在不符合条件的，即 使try_it函数返回None的项
               self.b[x][y] = 0  #回朔到上一层继续
             else:
               return True
 
   def start(self):
     begin = datetime.datetime.now()
     if self.b[0][0] == 0:
       self.try_it(0,0)
     else:
       x,y=self.get_next(0,0)
       self.try_it(x,y)
     for i in self.b:
       print i
     end = datetime.datetime.now()
     print '\ncost time:', end - begin
     print 'times:',self.t
     return
 
 
 s=solution([[8,0,0,0,0,0,0,0,0],
     [0,0,3,6,0,0,0,0,0],
     [0,7,0,0,9,0,2,0,0],
     [0,5,0,0,0,7,0,0,0],
     [0,0,0,8,4,5,7,0,0],
     [0,0,0,1,0,0,0,3,0],
     [0,0,1,0,0,0,0,6,8],
     [0,0,8,5,0,0,0,1,0],
     [0,9,0,0,0,0,4,0,0]])
 73 s.start()

Es ist erwähnenswert, dass die verwendete rekursive Beurteilung geschickt zur vorherigen Ebene zurückkehren kann, wenn der falsche Zweig genommen wird. Die spezifische Implementierung besteht darin, eine for-Schleife zu verwenden, um kontinuierlich Zahlen von 1 bis 9 einzugeben, während der Aufzeichnungsunterbrechungspunkt erreicht wird. Bestimmen Sie anhand des Rückgabewerts der nächsten Ebene, ob ein Backtrack durchgeführt werden soll.

Die Programmausgabe lautet wie folgt:

[8, 1, 2, 7, 5, 3, 6, 4, 9]
[9, 4, 3, 6, 8, 2, 1, 7, 5]
[6, 7, 5, 4, 9, 1, 2, 8, 3]
[1, 5, 4, 2, 3, 7, 8, 9, 6]
[3, 6, 9, 8, 4, 5, 7, 2, 1]
[2, 8, 7, 1, 6, 9, 5, 3, 4]
[5, 2, 1, 9, 7, 4, 3, 6, 8]
[4, 3, 8, 5, 2, 6, 9, 1, 7]
[7, 9, 6, 3, 1, 8, 4, 5, 2]

cost time: 0:00:00.060687
times: 45360

Sie können sehen, dass das Programm zwar viele Operationen hat, aber dennoch sehr schnell ist.

Das obige ist der detaillierte Inhalt vonPython-Codebeispiel zur Implementierung des Sudoku-Lösungsprogramms. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!