backtracking magisches quadrat

[thelittlebug]

Ich versuche mich gerade am BackTracking und habe gerade einen Solver für magische Quadrate fertiggestellt. Im Moment kann er nur Quadrate 3er Ordnung erstellen, da fehlt noch ein wenig für Allgemeines.

Eine Erklärung zu magischen Quadraten findet man unter http://www.magic-squares.de/

Am besten fand ich ja die Optimierungsmöglichkeiten. Man kann viele Wege bereits vorher ausschließen bevor man Sie komplett durchrechnet. Mit Sicherheit habe ich noch nicht alle Optimierungsmöglichkeiten ausgeschöpft. Aber die Zahlen sprechen für sich:

1. Version -> alle Möglichkeiten dumm durchprobieren: 8,6 Sekunden auf meinem Notebook
2. Version -> nur die gröbsten Sachen Filtern: ~1,2 Sekunden
3. Version -> so gut wie alles bei Aussicht auf Fehlschlag filtern: ~0,04 Sekunden

Ich möchte euch bitten meinen Code auf stilistische Fehler zu überprüfen da ich noch relativ neu in der Pythonprogrammierung bin. Sicherlich ist vieles nicht der schönste Weg

Code: Alles auswählen

#!/usr/bin/python
# -*- coding: utf-8 -*-

#import psyco
#psyco.full()

class Solver:
    def __init__(self, width):
        self.qua = [0]*width**2 #erzeugt platz für magisches uadrat
        self.width = width
        self.ms = (width**3+width)/2 #berechne magische summe
        
    def checkline(self, line):
        '''Überprüft auf Magische Summe horizontal'''
        count = 0
        wl = self.width*line
        for i in range(self.width):
            count += self.qua[wl+i]
        if count == self.ms: return 1
        else: return 0
    
    def checkrow(self, row):
        '''Überprüft auf Magische Summe vertikal'''
        count = 0
        for i in range(self.width):
            count += self.qua[self.width*i+row]
        if count == self.ms: return 1
        else: return 0
    
    def checkdia(self, rl):
        count = 0
        for i in range(self.width):
            if (rl==1): count += self.qua[self.width*i+i]
            if (rl==2): count += self.qua[self.width*(i+1)-(i+1)]
        if count == self.ms: return 1
        else: return 0
    
    def checker(self, sum):
        '''Überprüft ein ganzes Quadrat auf Eigenschaft "magisch"'''
        if (self.checkrow(0) and self.checkrow(1) and self.checkrow(2) and self.checkline(0) and self.checkline(1) and self.checkline(2) and checkdia(1) and checkdia(2)):
            return 1
        else:
            return 0
    
    def solve(self, where = 0):
        '''Rekursiver Löser mit Fehlwegabfragen'''
        for count in range(1,10):
            if count not in self.qua:
                self.qua[where] = count
                if where == 2 or where == 5: #wenn die erste od. 2te zeile schon nicht stimmt, kanns nimma besser werden
                    if self.checkline((where+1)/3-1): self.solve(where+1)
                elif where == 6: # 1te spalte
                    if self.checkrow(0): self.solve(where+1)
                elif where == 7: # 2te spalte und 1ste diagonale
                    if (self.checkrow(1) and self.checkdia(2)): self.solve(where+1)
                elif where == 8: # quadrat gefüllt
                    if self.checkline(2): # letzte zeile
                        if (self.checkrow(2) and self.checkdia(1)): # fehlt nur noch letzte spalte und letzte diagonale
                            print self.qua[0:3] # jo, hat alles gepasst, zeig lösung
                            print self.qua[3:6]
                            print self.qua[6:9]
                            print
                else: # wenn es nichts zu prüfen gibt fülle weiter aus
                    self.solve(where+1)
                self.qua[where] = 0 #backtracking

mysolver = Solver(3)
mysolver.solve()

Mit dem nun gewonnen Wissen über Backtracking möchte ich einige Solver probieren: Sudoku, 4Gewinnt, TacTacToe, Schach ( na das kann ja was werden ), Sokoban, Dame, Mühle, Solitaire ( Das Brettspiel ), und den Puzzle Mode von Super Collapse III

Wenn euch noch andere Anwendungsfälle bekannt sein sollten schreibt Sie ruhig hier dazu.

mfg tlb

[Leonidas]

Stilistische Sachen:

• Kommentare in gleicher Zeile wie Code: Das macht diie Zeilen unnötig lang und schwer lesbar. Besser Kommentare in eigene Zeilen packen.
• Bei if braucht man keine Klammern und sollte man keine Klammern schreiben.
• ifs sollten nicht als Einzeiler geschrieben werden. (von den Funktionen ist das egal, nur vom PEP8 nicht)
• Statt 0 und 1 besser False und True nutzen, ist aussagekräftiger.

[thelittlebug]

Hi Leonidas,

Danke für die Hinweise, hab es gleich ausgebessert. ( Sollte ich es oben im Originalpost von mir auch ändern? )
Gibt es funktionell auch Teile zu verbessern? Nutze ich zu sehr den C Stil?

mfg tlb

[BlackJack]

Zu lange Zeilen wurden ja schon erwähnt. Ich persönlich würde noch längere Namen benutzen. Zum Beispiel `magic_sum` statt `ms`. Dann kann man sich in der `__init__()` den Kommentar sparen, dass dort die magische Summe berechnet wird und überall wo man `magic_sum` benutzt, ist auch klarer wofür der Name steht, ohne das man erst die "Definition" suchen muss.

Ein weiterer stilistischer Punkt sind Leerzeichen um Operatoren. Aus Gründen der Lesbarkeit sollte man eigentlich welche setzen.

Dann eine Sache, die Du ständig machst, ist das Überprüfen einer Bedingung mit ``if`` um dann entweder 0 oder 1 zurückzugeben. Dort kannst Du gleich das Ergebnis der Bedingung, ohne ``if`` zurückgeben, das ist doch schon als Wahrheitswert zu gebrauchen. Also:

Code: Alles auswählen

if answer == 42 and viking == 'eric':
    return True
else:
    return False
# =>
return answer == 42 and viking == 'eric'

Du machst einiges "von Hand", für das es schon fertige Funktionen gibt. Zum Beispiel die `sum()` Funktion. Damit bekommt man `Solver.checkline()` in zwei Zeilen:

Code: Alles auswählen

    def checkline(self, line):
        '''Überprüft auf Magische Summe horizontal'''
        row_start = line * self.width
        return sum(self.qua[row_start:row_start+self.width]) == self.ms

Die `Solver.checkrow()` Methode sollte wohl besser `Solver.checkcolumn()` heissen. Sowohl `line` = Zeile als auch `row` = Reihe, sind horizontal. Und mit `sum()` und der Schrittweite bei Slices kann man auch diese Methode massiv kürzen:

Code: Alles auswählen

    def checkcolumn(self, column):
        '''Überprüft auf Magische Summe vertikal'''
        return sum(self.qua[column::self.width]) == self.ms

Und wie soll's auch anders sein: `Solver.checkdia()` lässt sich ebenfalls nach diesem Muster schreiben. Bei der einen Diagonale fängt man bei Index 0 an und geht in vierer Schritten weiter, bei der anderen fängt man bei Index 2 (oben rechts) an und geht in zweier Schritten durch die Liste. Bei den zweier Schritten muss man aufpassen, dass man das Feld ganz rechts unten nicht mehr erwischt, darum braucht man `end`:

Code: Alles auswählen

    def checkdia(self, rl):
        start, end, stride = ((0, None, 4), (2, -1, 2))[rl]
        return sum(self.qua[start:end:stride]) == self.ms

Achtung! Dazu musste ich den Wertebereich von `rl` von 1 und 2 auf 0 und 1 "verschieben", also auch die ganzen Aufrufe anpassen.

In `Solver.checker()` wird der Parameter `sum` nicht benutzt, dafür aber `checkdia` was es nicht gibt. Das sollte wohl `self.checkdia` heissen. Interessant, dass das Programm trotzdem läuft. Bis dahin scheint die Abfrage nie zu kommen.

[thelittlebug]

Hi BlackJack,

Danke für die vielen Verbesserungsvorschläge

Bei den If's hast du natürlich zu 100% Recht.
Das mit sum ist für mich neu sieht aber sehr gut aus.
Solver.checker() wurde benutzt bevor ich begonnen habe zu optimieren, scheinbar ist da was beim Suchen&Ersetzen schief gegangen

Ich werde das Ganze gleich mal ausprobieren und auf Quadrate beliebiger Ordnung ( sprich Kantenlänge ) erweitern.

mfg tlb

[BlackJack]

So würde ich das lösen:

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import division

# import psyco
# psyco.full()

class Solver(object):
    """Magic square solver.
    
    size : int
        Size of a row/column of the square.
    magic_sum : int
        The sum of each row, column and diagonal in a valid magic square.
    numbers : int
        Number of cells in the square.
    used : [bool]
        Keeps track of (un)used numbers in the square.
    sums : [([int], bool)]
        Contains tupels for every index of the solution.
        
        The tupels contain a list with a sum for row, column, or ─where
        applicable─ diagonal this index belongs to and a boolean that tells
        wether this is the index of the last cell in that row, column, or
        diagonal.
        
        The list with a single integer value is there to simulate a pointer
        to an int like in C.
    solution : [int]
        The (partial) solution as flat list.
    """
    def __init__(self, size):
        """Creates a magic square solver for given `size`."""
        self.size = size
        self.magic_sum = (size**3 + size) // 2
        self.numbers = size**2
        self.used = [False] * (self.numbers + 1)
        self.sums = [[] for dummy in xrange(self.numbers)]
        self.solution = [0] * self.numbers
        # 
        # Set up the (partial) sums for rows, columns and diagonals for each
        # cell in the solution.
        # 
        row_sums = [[0] for dummy in xrange(size)]
        column_sums = [[0] for dummy in xrange(size)]
        diagonal_sum_a, diagonal_sum_b = [0], [0]
        for row in xrange(size):
            for column in xrange(size):
                index = row * size + column
                self.sums[index].append((row_sums[row],
                                         column == size - 1))
                self.sums[index].append((column_sums[column],
                                         row == size - 1))
            self.sums[row * size + row].append((diagonal_sum_a,
                                                row == size - 1))
            self.sums[row * size + size - row - 1].append((diagonal_sum_b,
                                                           row == size - 1))
    
    def put_number(self, index, number):
        """Puts `number` at `index` if certain constraints hold.
        
        Returns `True` if the number was actually put into the square, `False`
        otherwise.
        """
        if self.used[number]:
            return False
        
        is_possible = True
        # 
        # Add `number` to all sums belonging to the cell at `index` and
        # check constraints.
        # 
        for last_index, (sum_, is_last) in enumerate(self.sums[index]):
            sum_[0] += number
            if (sum_[0] > self.magic_sum
                or (is_last and sum_[0] != self.magic_sum)):
                is_possible = False
                break
        # 
        # Roll back changes or actually put `number` into `self.solution`.
        # 
        if not is_possible:
            sums = self.sums[index]
            for i in xrange(last_index + 1):
                sums[i][0][0] -= number
        else:
            self.used[number] = True
            self.solution[index] = number
        
        return is_possible
    
    def remove_number(self, index):
        """Removes the number at `index`."""
        number = self.solution[index]
        for sum_ in self.sums[index]:
            sum_[0][0] -= number
        self.used[number] = False
        self.solution[index] = 0
    
    def print_solution(self):
        """Prints the solution."""
        for line_start in xrange(0, len(self.solution), self.size):
            print self.solution[line_start:line_start + self.size]
        print
    
    def solve(self, index=0):
        """Solves the magic square.
        
        Prints all possible magic squares of `self.size`.
        """
        if index == self.numbers:
            self.print_solution()
        else:
            for number in xrange(1, self.numbers + 1):
                if self.put_number(index, number):
                    self.solve(index + 1)
                    self.remove_number(index)

solver = Solver(3)
solver.solve()

Aber schon bei einer Kantenlänge von 4 wird das einfach zu langsam, bzw. der Suchraum wird trotz Einschränkungen zu gross.