Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
lehrkraefte:blc:informatik:ffprg1-2020:sudoku [2020/04/16 19:05] Ivo Blöchliger [Überprüfen, ob eine Zahl in ein bestimmtes Feld darf] |
lehrkraefte:blc:informatik:ffprg1-2020:sudoku [2020/05/04 16:40] (current) Ivo Blöchliger [Ausblick] |
||
---|---|---|---|
Line 72: | Line 72: | ||
<code python> | <code python> | ||
# Koordinaten von 0 bis 8 | # Koordinaten von 0 bis 8 | ||
- | def ok(zahl, x, y): | + | def ok(self, zahl, x, y): |
# Zeile überpruefen | # Zeile überpruefen | ||
# Spalte überpruefen | # Spalte überpruefen | ||
Line 84: | Line 84: | ||
</ | </ | ||
===== Alles ausprobieren, | ===== Alles ausprobieren, | ||
+ | ==== Gegebene Felder ==== | ||
+ | |||
+ | Als erstes brauchen wir ein Feld mit True/ | ||
+ | Schreiben Sie eine Methode dafür, oder verstehen Sie folgende Implementation | ||
+ | <code python> | ||
+ | def make_given(self): | ||
+ | self.given = [[self.feld[i][j]!=0 for j in range(9)] for i in range(9)] | ||
+ | </ | ||
+ | |||
+ | ==== Algorithmus ==== | ||
+ | Wir haben folgende Variablen, die den Zustand der Suche beschreiben: | ||
+ | * Das Feld mit Zahlen und Information, | ||
+ | * Aktuelle Position '' | ||
+ | Des Weiteren brauchen wir | ||
+ | * Eine Reihenfolge, | ||
+ | |||
+ | Die Idee ist folgende: Wir probieren alle möglichen Zahlen für ein Feld aus und schauen, ob sich damit das Feld vollständig ausfüllen lässt. Ist es vollständig ausgefüllt, | ||
+ | |||
+ | <code txt> | ||
+ | Initialisierung: | ||
+ | Aktuelles Feld (x,y)=(0,0) | ||
+ | | ||
+ | Wiederholen: | ||
+ | Sei z1 = feld[x][y], die Zahl an der aktuellen Position (0 wenn leer) | ||
+ | Sie z2 die nächst-grössere Zahl, die an die Position passt. | ||
+ | Wenn es z2 nicht gibt: | ||
+ | feld[x][y]=0 (wieder löschen) | ||
+ | (x,y) auf die nächste, vorhergehende Position setzen, die nicht vorgegeben ist. | ||
+ | Wenn es keine solche Position gibt: | ||
+ | | ||
+ | Sonst: | ||
+ | feld[x][y]=z2 (neue Zahl schreiben) | ||
+ | (x,y) auf die nächste, nachfolgende Position setzen, die nicht vorgegeben ist. | ||
+ | Wenn es keine solche Position gibt: | ||
+ | Melden, dass die Lösung gefunden wurde und abbrechen. | ||
+ | </ | ||
+ | |||
+ | Die Methode kann wie folgt aussehen: | ||
+ | |||
+ | <code python> | ||
+ | def solve(self): | ||
+ | x,y = 0,0 | ||
+ | while True: | ||
+ | # Tu wat, mit self.feld[x][y] und self.given[x][y] | ||
+ | </ | ||
+ | |||
+ | [[https:// | ||
+ | |||
===== Alles ausprobieren, | ===== Alles ausprobieren, | ||
+ | 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, | ||
+ | |||
+ | 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 ===== | ===== Ausblick ===== | ||
+ | Um sich die Zähne auszubeissen, | ||
+ | |||
+ | <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_____ | ||
+ | 1__76____+_______92+5________+6_____75_+____39___+_8_______+_23______+___1__4__+_9_______ | ||
+ | 2_____4__+___5___9_+_8__1____+7___5__18+3_4______+_________+___3_26__+_1_______+___4_____ | ||
+ | 7______2_+___8__1__+3________+_4___7__3+__1___5__+____2____+___1___4_+___56____+8_______7 | ||
+ | 7_____34_+4___8_5__+___2_____+___16___2+3____4___+_8_______+_21______+______73_+_________ | ||
+ | 7_____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____ | ||
+ | </ | ||
+ | |||
+ | ===== Zeit messen in Python ===== | ||
+ | <code python> | ||
+ | import time | ||
+ | start_time = time.time() | ||
+ | # | ||
+ | # Grosse Berechnung (z.B. Lösen eines Sudokus) | ||
+ | # | ||
+ | # Dauer ausgeben: | ||
+ | print(" | ||
+ | </ | ||