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()
Wenn euch noch andere Anwendungsfälle bekannt sein sollten schreibt Sie ruhig hier dazu.
mfg tlb