Differences

This shows you the differences between two versions of the page.

--- lehrkraefte:blc:informatik:ffprg1-2020:sudoku [2020/04/16 19:20]
Ivo Blöchliger [Algorithmus]
+++ lehrkraefte:blc:informatik:ffprg1-2020:sudoku [2020/05/04 16:40] (current)
Ivo Blöchliger [Ausblick]
@@ Line 72: / Line 72: @@
 <code python>
   # Koordinaten von 0 bis 8
-  def ok(zahl, x, y):
+  def ok(self, zahl, x, y):
     # Zeile überpruefen
     # Spalte überpruefen
@@ Line 90: / Line 90: @@
 <code python>
   def make_given(self):
-    self.given = [[feld[i][j]!=0 for j in range(9)] for i in range(9)]
+    self.given = [[self.feld[i][j]!=0 for j in range(9)] for i in range(9)]
 </code>
@@ Line 127: / Line 127: @@
     x,y = 0,0
     while True:
-       # Tu wat!
+       # Tu wat, mit self.feld[x][y] und self.given[x][y]
 </code>
+[[https://fginfo.ksbg.ch/~ivo/videos/sudoku-alles-ausprobieren-simpel.mp4|Video-Erklärung dazu]]
 ===== Alles ausprobieren, effizienter =====
+Die Reihenfolge der durchprobierten Felder ist beliebig. Diese kann sogar dynamisch gewählt werden. Damit die Suche effizienter wird, sollten zuerst jene Felder ausprobiert werden, wo noch am wenigsten Zahlen möglich sind, idealerweise nur eine (oder Null, um festzustellen, dass "man auf dem Holzweg ist").
+Die Anzahl möglicher Zahlen könnte jedes Mal neu berechnet werden, oder beim Setzen einer Zahl nachführen. Dazu müssen allerdings die Zustände gespeichert werden, oder beim Zurückgehen neu berechnet werden.
 ===== Ausblick =====
+Um sich die Zähne auszubeissen, hier gibt es einige der schwierigsten Sudokus: http://minimumsudoku.com/Sudoku.html
+<code txt>
+____24_8_+_3_______+____6____+___1__3_5+2_4______+______7__+_5_3__1__+6__5___4_+_________
+____42_8_+_3_______+____6____+___1__3_5+2_4______+______7__+_5_3__1__+6__5___4_+_________
+____45_7_+6___8____+_3_______+___7__3_2+__1______+5________+4______5_+_____16__+_2_3_____
+____5_6__+___7___5_+__1______+4______17+_8__2____+_______3_+65____2__+_____14__+___3_____
+___3__1_7+4___7____+______5__+61____3__+____48_2_+_5_______+2______48+___1_____+_________
+___3__1_7+4___8____+______5__+61____3__+____49_2_+_5_______+2______49+___1_____+_________
+___3__1_8+6___8____+______5__+71____3__+____46_2_+_5_______+2______64+___1_____+_________
+___3_56__+___2___5_+_1_______+____4__81+27_______+_________+5_____2__+3__7_____+__8_1____
+___6___71+4___7____+________8+516______+____3_2__+_8___4___+2_____43_+___1_____+_________
+__1_5____+____6__8_+______3__+62______5+___4__1__+8________+2______6_+_8_3_____+_9_1_____
+_2__3_4__+___1___7_+5________+_3__24___+_______81+_________+1_76_____+_____72__+8________
+_684_____+______51_+_________+_2__7____+1_____4__+___6____8+5___1____+3_______6+_____6_2_
+_7___1___+_3_____4_+______2__+___35___7+8_____1__+___4_____+1___4___6+___5___3_+2________
+_83___7__+___6_2_4_+_________+____3_8__+6__7_____+_1______5+2______6_+5___8____+___1_____
+_93___7__+___6_2_4_+_________+____3_9__+6__8_____+_1______5+2______6_+5___9____+___1_____
+__76____+_______92+5________+6_____75_+____39___+_8_______+_23______+___1__4__+_9_______
+_____4__+___5___9_+_8__1____+7___5__18+3_4______+_________+___3_26__+_1_______+___4_____
+______2_+___8__1__+3________+_4___7__3+__1___5__+____2____+___1___4_+___56____+8_______7
+_____34_+4___8_5__+___2_____+___16___2+3____4___+_8_______+_21______+______73_+_________
+_____34_+4___8_5__+___2_____+___61___2+3____4___+_8_______+_21______+______73_+_________
+_______81+6___7____+_________+___8_1_4_+7_2______+3__4_____+2_____7__+____6_3__+_8_5_____
+______6_1+7_2______+4__3_____+____8__2_+_6__1____+______4__+3______8_+___4_1___+___65____
+____4__78+1__2_____+_________+6_____1__+_7__8____+_____2__5+_48____3_+___6_15__+_________
+____4_58_+_36______+_2_____4_+8___25___+______7__+________6+___7_61__+2________+___3_____
+____5__74+8_1______+_________+_7_24____+6_____1__+_________+2__1_63__+_4_____2_+___8_____
+____6__51+_42______+_________+__7___4__+1___5____+___3___8_+___4_76__+53_______+___2_____
+____61___+_9_____3_+_________+6_1___7__+___75__8_+4________+___2__4_9+_5_3_____+______1__
+____7_2_4+__5_2_6__+8________+3__1___5_+_4__6____+_________+_2____4__+___5_3___+___8_____
+____764__+5_2______+_________+___51_3__+_8_3_____+67_______+__82_____+_______65+_______8_
+____8_3__+_24______+____1____+6_8___1__+3__5_____+___2_____+_7____53_+___4___2_+8________
+___1__78_+5_23_____+_4_______+6__7___3_+_9______2+_________+1_____5__+____28___+____4____
+</code>
+===== Zeit messen in Python =====
+<code python>
+import time
+start_time = time.time()
+#
+# Grosse Berechnung (z.B. Lösen eines Sudokus)
+#
+# Dauer ausgeben:
+print("--- %s seconds ---" % (time.time() - start_time))
+</code>