lehrkraefte:blc:informatik:ffprg1-2020:sudoku [https://fginfo.ksbg.ch Fachgruppe Informatik der KSBG]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Sudoku ======

Ziel ist es, ein Sudoku-Solver zu programmieren, der die allermeisten Sudokus in nützlicher Frist lösen kann.

===== Datenstruktur =====
Wir werden eine Klasse Sudoku programmieren. Darin werden die Zahlen in einem 2-dimensionalen Array 9x9-Array gespeichert.
Dazu werden wir Funktionen einbauen, die wir als Aufgaben bei den [[lehrkraefte:blc:informatik:ffprg1-2020:funktionen|Funktionen]] schon programmiert haben.

<hidden Klasse zum Starten>
<code python sudoku.py>


class Sudoku:
    
    def __init__(self):
        self.feld = [[0 for i in range(9)] for j in range(9)]
        
    # Liest ein Sudoku als String ein, z.B.
    # "003020600900305001001806400008102900700000008006708200002609500800203009005010300"
    # "200080300\n060070084\n030500209\n000105408\n\n000000000\n402706000\n301007040\n720040060\n004010003"
    def parse(self,s):
        x=0
        y=0
        for c in s:
            if (c>="0" and c<="9") or (c=="."):
                if c==".":
                    c="0"
                self.feld[x][y] = int(c)
                x+=1
                if (x==9):
                    x=0;
                    y+=1

    # Liest ein Sudoku von einer Text-Datei ein.
    def fromFile(self,f):
        file1 = open(f,"r")
        sudoku = file1.read()
        file1.close()
        self.parse(sudoku)
            
    # Umwandlung in ASCII-Art
    def __str__(self):
        hbar1 = ("#==="+"===="*2)*3+"#\n"
        hbar2 = ("#---"+"+---"*2)*3+"#\n"
        symbols = [str(i) for i in range(10)]
        symbols[0] = " "
        separators = ["|", "|", "#"]
        res = hbar1
        for y in range(9):
            res += "#"
            for x in range(9):    
                res += " "+symbols[self.feld[x][y]]+" "+separators[x%3]
            res+="\n"
            if y%3==2:
                res += hbar1
            else:
                res += hbar2
        return res
        
# ENDE der Klasse Sudoku        
    
# Beginn vom Hauptprogramm

s = Sudoku()
s.parse("003020600900305001001806400008102900700000008006708200002609500800203009005010300")
print(s)

</code>
</hidden>
===== Überprüfen, ob eine Zahl in ein bestimmtes Feld darf =====
Ziel: Eine Methode, die überprüft, ob eine Zahl in ein bestimmtes Feld darf:
<code python>
  # Koordinaten von 0 bis 8
  def ok(self, zahl, x, y):
    # Zeile überpruefen
    # Spalte überpruefen
    a = x - x%3
    b = y - y%3
    # a,b ist die Koordinate oben links im 3x3-Subquadrat. Erklaeren Sie warum!
    # Subquadrat ueberpruefen
    
    # Alle Tests durch? Also
    return True
</code>
===== Alles ausprobieren, simpel =====
==== Gegebene Felder ====

Als erstes brauchen wir ein Feld mit True/False-Werten, das angibt, ob die Zahl vorgegeben ist oder nicht.
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)]
</code>

==== Algorithmus ====
Wir haben folgende Variablen, die den Zustand der Suche beschreiben:
  * Das Feld mit Zahlen und Information, ob die einzelnen Zahlen vorgegeben sind oder nicht (''self.given[x][y]'')
  * Aktuelle Position ''(x,y)''
Des Weiteren brauchen wir
  * Eine Reihenfolge, um die Felder durchzugehen (z.B. zeilenweise).

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, sind wir fertig. Gibt es auch für das erste Feld keine Möglichkeit, hat das Sudoku keine Lösung.

<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:
       Melden, dass das Sudoku keine Lösung hat und abbrechen.
  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.
</code>      

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]
</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_____
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____
</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>