sudoku-loesung

Code-Stücke können hier veröffentlicht werden.
Antworten
lemmi
User
Beiträge: 19
Registriert: Dienstag 28. März 2006, 17:45

Donnerstag 26. Juli 2007, 20:54

hi,

hab mich mal die letzten tage mit sudoku beschaeftigt (bin eigentlich kein fan davon, aber ich fands eine gute uebung).
bis jetzt kann das script nur etwas einfachere sudokus loesung, weil noch ein teil fehlt, aber so einige sachen gehen schon. wenns stiltechnisch etwas zu beanstanden gibt, bitte melden :)
zum script:
wenn ihr nicht im testlauf seid muesst ihr Sudoku nur instanzieren dann zeile fuer zeile eingeben und dabei leere felder als 0 eintragen.

Code: Alles auswählen

class Sudoku(object):
    def __init__(self, feld = []):
        self.__feld = feld
        del feld
        self.__istKomplett()
        self.__gestrichen = 1
        self.__main()
        self._ausgabe()

    def __istKomplett(self):
        if len(self.__feld) == 9:
            for i in range(9):
                for j in range(9):
                    self.__feld[i][j]=[self.__feld[i][j],1,2,3,4,5,6,7,8,9]
        else:
            self.__eingabe()        
            
    def _getFeld(self):
        return self.__feld
    
    def __eingabe(self):
        self.__feld = [[[0,1,2,3,4,5,6,7,8,9] for x in range(9)] for y in range(9)]
        for y in range(9):
            zeile = str(raw_input("%d. Zeile:" % (y+1)))
            for x in range(9):
                self.__feld[y][x][0] = int(zeile[x])

    def _ausgabe(self):
        for i in range(9):
            for j in range(9):
                print self.__feld[i][j][0],
            print
    
    def __main(self):
        while self.__gestrichen:
            self.__gestrichen = 0
            for y in range(9):
                for x in range(9):
                    self.__test_v(y,x)
                    self.__test_h(y,x)
                    self.__test_box(y,x)
                    if len([i for i in self.__feld[y][x] if i != 0]) == 1:
                        self.__feld[y][x][0] = [i for i in self.__feld[y][x] if i != 0][0]
    
    def __test_box(self, x, y):
        zahl = self.__feld[y][x][0]
        box_y = int(y / 3) * 3
        box_x = int(x / 3) * 3
        for y in range(3):
            for x in range(3):
                if not self.__feld[box_y + y][box_x + x][0]:
                    self.__feld[box_y + y][box_x + x][zahl] = 0
                    self.__gestrichen += 1                
                
        
    def __test_v(self, y, x):
        zahl = self.__feld[y][x][0]
        y  = [i for i in range(9) if i != y]
        for y in y:
            if not self.__feld[y][x][0]:
                self.__feld[y][x][zahl] = 0
                self.__gestrichen += 1
            
    def __test_h(self, y, x):
        zahl = self.__feld[y][x][0]
        x  = [i for i in range(9) if i != x]
        for x in x:
            if not self.__feld[y][x][0]:
                self.__feld[y][x][zahl] = 0
                self.__gestrichen += 1

if __name__ == '__main__':
    testfeld = [[6,8,3,0,7,4,0,0,9], \
                [0,0,4,8,0,1,0,0,0], \
                [7,9,1,3,2,0,4,8,0], \
                [0,3,6,0,1,0,0,0,2], \
                [0,7,8,0,3,0,5,4,0], \
                [1,0,0,0,4,0,3,6,0], \
                [0,4,7,0,5,2,1,3,6], \
                [0,0,0,4,0,7,9,0,0], \
                [9,0,0,1,8,0,7,5,4]]

    st = Sudoku(testfeld)
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Freitag 27. Juli 2007, 11:57

lemmi hat geschrieben:bis jetzt kann das script nur etwas einfachere sudokus loesung, weil noch ein teil fehlt, aber so einige sachen gehen schon. wenns stiltechnisch etwas zu beanstanden gibt, bitte melden :)
Stilistisch: Ja, ``del`` ist vollständig unnötig, da es sowieso gelöscht wird, wenn die Funktion ``__init__`` endet, in ``testfeld`` brauchst du die Backslashes nicht. Ansonsten ist der Code nicht PEP8 kompatibel und nutzt für meinen Geschmack auch zu viele Underscore-Namen und erst recht zu viele Doppel-Underscore-Namen. In Python gibt es seit 2.2.1 die Werte ``True`` und ``False``, also bitte nutze sie auch, statt mit Null und Eins zu arbeiten. Im Code gibt es keine Einzigen Kommentar, daher ist meine Motivation sehr gering, mir anzusehen wie er überhaupt funktioniert - selbst implementieren wäre warscheinlich einfacher. Daher vergiss nicht Kommentare zu schreiben.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
BlackJack

Freitag 27. Juli 2007, 12:20

Mindestens eine Zeile ist länger als 80 Zeichen. Die Namen folgen nicht der Konvention, also z.B. `__istKomplett()` statt `__ist_komplett()`. Es könnten ein paar mehr Leerzeichen nach Kommata sein. Und nicht überall sind Operatoren und Zuweisungen von Leerzeichen umgeben.

Die führenden doppelten Unterstriche bei den Methodennamen würde ich weglassen und, wenn überhaupt, mit einem Unterstrich beginnen.

In der `__init__()` wird eine Liste als Default-Wert übergeben. Default-Werte werden nur *einmal* ausgewertet wen die ``def``-Anweisung ausgeführt wird. Es teilen sich also alle `Sudoku`-Objekte die selbe Liste. Das scheint in diesem Fall kein Problem zu sein, aber `None` wäre IMHO auch hier ein besserer Default-Wert.

Den Namen `feld` explizit zu löschen, halte ich für übertrieben.

Von Methoden deren Name mit `is_` oder `ist_` beginnt, erwartet man normalerweise, dass sie das Objekt nicht verändern und `True` oder `False` zurückgeben.

Solange man nicht wirklich eine Liste mit Zahlen benötigt, ist `xrange()` in der Regel `range()` vorzuziehen.

`_getFeld()` wird nicht nur nicht benutzt ─ "getter" sind auch unpythonisch. Zusammen mit den vielen '__' in den Methodennamen scheint mir, Du versuchst eine andere Sprache in Python zu schreiben.

`raw_input()` liefert schon eine Zeichenkette, da muss man nicht noch einmal `str()` drauf aufrufen.

Wenn ich das Programm richtig verstanden habe, werden in jeder Liste in dem Feld zwei verschiedene Informationen gespeichert die man besser trennen sollte. Einmal der Inhalt des Feldes und dann welche Zahlen noch in Frage kommen, falls das Feld noch leer ist. Letzteres wäre in einem `set()` besser aufgehoben.

Man sollte auch Indexe nur verwenden, wenn es ohne nicht geht. Die Ausgabe käme zum Beispiel völlig ohne aus:

Code: Alles auswählen

    def ausgabe(self):
        for zeile in self.feld:
            for zelle in zeile:
                print zelle[0],  # Besser wäre: zelle.zahl
            print
Die innerste ``if``-Abfrage in `__main()` ist sehr unübersichtlich und kompliziert. Wenn man statt einer Liste ein Objekt mit Attributen für Zahl und verbleibende Möglichkeiten nehmen würde, wobei letzteres ein `set()` wäre, könnte das so aussehen:

Code: Alles auswählen

                    zelle = self.feld[y][x]
                    if len(zelle.moeglichkeiten) == 1:
                        zelle.zahl = zelle.moeglichkeiten.pop()
Zu guter letzt finde ich die Klasse nicht gut entworfen. Das ist ein Miniprogramm, dass eigentlich gar keine öffentliche API hat, von `__init__()` mal abgesehen und das nicht besonders flexibel verwendet werden kann. Man erzeugt es, es wird sofort losgerechnet, man hat keinen Einfluss auf die Ausgabe, und die und eine eventuelle Eingabe sind in der Klasse enthalten. Also Logik und GUI sind vermischt.
lemmi
User
Beiträge: 19
Registriert: Dienstag 28. März 2006, 17:45

Freitag 27. Juli 2007, 12:34

kommentieren werde ich alles noch im nachhinein schreiben, weil ich noch einiges mittlerweile aendern musste.
ich kann nicht mit true und false arbeiten, weil die zahlen groeßer als 1 werden und ich mir so einige if-abfragen spare.
ich wollte das ganze zeug eben mal so non_public wie moeglich bzw. noch einigermaßen sinnvoll machen. reiner uebungszweck.
kannst du mir noch sagen, wo der code nicht PEP8 kompatibel ist?
bin da noch nicht so vertraut mit.
aber danke erst mal :)
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Freitag 27. Juli 2007, 12:46

lemmi hat geschrieben:kannst du mir noch sagen, wo der code nicht PEP8 kompatibel ist?
bin da noch nicht so vertraut mit.
Im Moment habe ich keine Lust dir das aufzuschrieben, weil das länger dauert als das zu korrigieren. Wenn du aktuellen Code zeigst, kann ich dir aber ein Diff machen. Ansonsten lies doch einfach den PEP 8 ganz durch und gehe durch dein Programm zeile für Zeile durch und versuche das was du gelesen hast darauf einfach anzuwenden.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
lemmi
User
Beiträge: 19
Registriert: Dienstag 28. März 2006, 17:45

Freitag 27. Juli 2007, 12:50

hehe.. hab ja ich schon, deswegen hab ich auch gefragt und eigentlich nichts großartiges entdeckt. :roll:
werd mir aber erst mal den ein oder anderen vorschlag zu herzen nehmen und erst mal ausbessern.
Benutzeravatar
veers
User
Beiträge: 1219
Registriert: Mittwoch 28. Februar 2007, 20:01
Wohnort: Zürich (CH)
Kontaktdaten:

Freitag 27. Juli 2007, 14:08

lemmi
User
Beiträge: 19
Registriert: Dienstag 28. März 2006, 17:45

Sonntag 12. August 2007, 14:28

so, hab jetzt erst wieder etwas zeit gehabt mich mit dem script zu beschaeftigen.
ich hab das script um ein paar funktionen erweitert und etwas anders sortiert.
zusaetzlich ein paar kommentare zur vorgehensweise.
wenn ihr das script ausfuehrt werdet ihr kein komplettes ergebnis bekommen,
da ich ein sudoku genommen hab, was nicht mit meinen zwei loesungsmethoden zu loesen ist.
ich werde aber noch zusaetzlich eine weitere methode einbauen,
die dann die restlichen felder einfach ausprobiert.

edit:
hab gerade gemerkt, dass zum teil falshe ergebnisse raus kommen.
werd mich wohl die tage nochmal mit dem problem auseinandersetzen.
wem noch kurz irgentwas auffaellt, darf das sagen, aber bitte keine loesungen geben.

edit2:
update weiter unten
Zuletzt geändert von lemmi am Freitag 24. August 2007, 15:26, insgesamt 1-mal geändert.
lemmi
User
Beiträge: 19
Registriert: Dienstag 28. März 2006, 17:45

Mittwoch 15. August 2007, 20:42

so.. den fehler hab ich jetzt gefunden.
bis zu einem gewissen grad lassen sich sudokus mit diesem script loesen.
sollte es mit den methoden nicht loesbar sein wird abgebrochen.
wie gesagt, fuer diesen fall muss ich dann den rest durch "ausprobieren" loesen.

edit:
update weiter unten
lemmi
User
Beiträge: 19
Registriert: Dienstag 28. März 2006, 17:45

Freitag 24. August 2007, 15:45

sooo.. fast fertig.
mit diesem script sollte man jedes sudoku loesen koennen, solange es richtig eingegeben ist.
grund dafuer ist die backtrace funktion, die zum schluss alle fehlenden felder,
welche die anderen methoden nicht eindeutig loesen konnten, durch ausprobieren fuellt.

desweiteren hab ich das script noch etwas mehr comments verliehen,
die meisten methoden und variablen public gemacht und ein paar namen geaendert.
funktionieren tut soweit alles, geschwindigkeit ist auch akzeptabel
und man kann es auch einfach verwenden um ne gui drum herum zu schreiben, was dann wohl mein naechstes projekt sein wird.

auf meinem plan steht aber vorerst noch das ganze script vor falschen eingaben zu schutzen usw, aber in sachen verwendung und umfang wird sich wahrscheinlich nicht mehr viel aendern.

wenn jemand lust hat hier verbesserungen zu suchen darf er das gerne tun
und bescheid geben :)

script gibts hier
Zuletzt geändert von lemmi am Freitag 24. August 2007, 19:37, insgesamt 2-mal geändert.
schlangenbeschwörer
User
Beiträge: 419
Registriert: Sonntag 3. September 2006, 15:11
Wohnort: in den weiten von NRW
Kontaktdaten:

Freitag 24. August 2007, 16:30

-1. Verbesserungsvorschlag: Poste den Code ab Besten da, wo jeder Leserecht hat :wink:
lemmi
User
Beiträge: 19
Registriert: Dienstag 28. März 2006, 17:45

Freitag 24. August 2007, 19:19

musst rechtsklick und speichern unter.
ich koennte natuerlich auch noch ein .txt anfuegen, aber das muesstet ihr nur wieder weg machen.
Benutzeravatar
BlackVivi
User
Beiträge: 762
Registriert: Samstag 9. Dezember 2006, 14:29
Kontaktdaten:

Freitag 24. August 2007, 19:21

lemmi hat geschrieben:musst rechtsklick und speichern unter.
ich koennte natuerlich auch noch ein .txt anfuegen, aber das muesstet ihr nur wieder weg machen.
Für all deinen Code hier ein:

http://paste.pocoo.org/

Und füg' den Link hier rein... editier am besten auch deine alten Posts... der Syntax Highlighter is nit so toll.
Antworten