Ich habe mich noch nicht so lange mit Numpy befasst, finde den Ansatz aber höchst spannend. Trotzdem stelle ich fest, muss man sich etwas umgewöhnen, um diese Klasse bestens einzusetzen.
Am besten lernt man, wenn man es versucht! So habe ich ein kleines Programm zum Lösen der "Sudoku"-Aufgabe geschrieben. Ich denke, das ist ein Problem, für das NumPy sehr geeignet ist.
Code: Alles auswählen
"""
Lösen des Sudoku-Problems
"""
import numpy as np
import time
class sudokuLoesen():
def __init__(self, brett):
self.__brett = brett
self.__count = 0
self.__time = 0
self.__mitLog = False
self.__liste = []
self.__pruefung = ''
self.__state = False
self.__fault_z = np.empty([])
self.__fault_z = np.empty([])
self.__fault_z = np.empty([])
@property
def mitLog(self):
return self.__mitLog
@mitLog.setter
def mitLog(self, value):
self.__mitLog = value
@property
def brett(self):
return self.__brett
@brett.setter
def brett(self, value):
self.brett = value
@property
def laufzeit(self):
return self.__time
@property
def durchgaenge(self):
return self.__count
@property
def liste(self):
return self.__liste
@property
def pruefung(self):
return self.__pruefung
@property
def status(self):
return self.__state
@property
def fehlerZeile(self):
return self.__fault_z
@property
def fehlerSpalte(self):
return self.__fault_s
@property
def fehlerQuadrat(self):
return self.__fault_q
def listeMoeglichWerte(self, brett):
return self.__moeglicheZahlen(brett)
def __moeglicheZahlen(self, brett):
offen = np.ones((9, 9, 9), dtype=int)
# Index mit vorhandenen Zahlen bilden
index = np.where(brett > 0)
index = index + (brett[index] - 1,)
# Felder mit einer Zahl haben keine weiteren Zahlen möglich
offen[index[0], index[1]] = [0, 0, 0, 0, 0, 0, 0, 0, 0]
# Alle Spaltenwerte
offen[index[0], :, index[2]] = 0
# Alle Zeilenwerte
offen[:, index[1], index[2]] = 0
# Im 3er-Quadrat
for i in [0, 3, 6]:
for j in [0, 3, 6]:
index4 = np.where((index[0]>=i) & (index[0]<i+3) & (index[1]>=j) & (index[1]<j+3))
offen[i:i+3, j:j+3, index[2][index4]] = 0
return offen
def __einerSetzen(self, brett):
liste = []
offen = self.__moeglicheZahlen(brett)
# Anzahl Möglichkeiten pro Feld ermitteln, indem die Anzahl möglichen Zahlen berechnet werden
anz = np.zeros((9, 9), dtype=int)
for i in range(0,9):
anz[i] = np.sum(offen[i], axis=1)
# Alle Felder bei der nur noch eine Zahl möglich ist
einser = np.where(anz == 1) # [0] - die Zeile, [1] die Spalte der stellen die nur eine Zahl audfweisen
# Der Wert der Zahl ermitteln und zusammen mit der Position in das Brett eintragen
brett[einser] = np.where(offen[einser[0], einser[1]] == 1)[1] + 1
if self.__mitLog:
liste = [0, np.vstack((np.array(einser)+1, np.where(offen[einser[0], einser[1]] == 1)[1] + 1)).T]
return brett, liste
def __nurEinmalQuadrat(self, brett):
liste = []
offen = self.__moeglicheZahlen(brett)
# Die 3er-Quadrat bilden, es gibz insgesamt 9
for i in [0, 3, 6]:
for j in [0, 3, 6]:
zahlen = np.where(np.sum(np.sum(offen[i:i + 3, j:j + 3], axis=0), axis=0)==1)[0]
for n in zahlen:
pos = np.where(offen[i:i + 3, j:j + 3, n]==1)
brett[i + pos[0], j + pos[1]] = n + 1
if self.__mitLog:
p = np.split(np.array(pos).reshape(-1), 2)
liste.append([i + p[0][0] + 1, j + p[1][0] + 1, n + 1])
return brett, [1, np.array(liste)]
def __nurEinmalZeile(self, brett):
liste = []
offen = self.__moeglicheZahlen(brett)
# Berechnet in jeder Zeile (9) die Anzahl möglichen Zahlen pro Zelle
# Das Ergebnis ist ein 2d-Array. Im ersten Array ist die Zeilennummer, in der zweiten den mögliche Wert
line = np.where(np.sum(offen[:],axis=1) == 1) # [0] = zeile (x) [1] = wert - 1
# Es wird die Position innerhalb einr Zeile ermittelt, an der der Wert eingesetzt werden muss
# Das Ergebnis ist ein 2d-Array: Im ersten ist die Position aus dem Array line, im zweiten die
# Position innerhalb der Zeile
pos = np.where(offen[line[0], :, line[1]] == 1) # [0] = zeile von line, [1] = Position in der Zeile (y)
# Wert wird in das Brett eingefügt
if len(pos[0]) > 0:
brett[line[pos[0][0]], pos[1]] = line[1] + 1
if self.__mitLog:
liste = [2, np.vstack((line[0][pos[0]] + 1, pos[1] + 1, line[1] + 1)).T]
return brett, liste
def __nurEinmalSpalte(self, brett):
liste = []
offen = self.__moeglicheZahlen(brett)
# Berechnet in welcher Spalte es Zellen hat, bei denen nur noch ein möglicher Wert vorhanden ist
# Das Ergebnis ist ein 2d-Array: im ersten ist die Spaltennummer, im zweiten der Wert der möglich ist
spalte = np.where(np.sum(offen[:], axis=0) == 1) # [0] = spalte (x) [1] = wert - 1
# Es wird die Zeile gesucht, in der der gefundene Wert eingesetzt werden muss
# Das Ergebnis ist ein 2d-Array: im ersten sollte die Position in dem Array spalte sein (ist es aber nicht
# Es ist die Position + 1, aber das Ergebnis stimmt), im zweiten steht die Zeilennummer,
# in der der Wert eingesetzt werden muss
pos = np.where(offen[:, spalte[0], spalte[1]] == 1) # [0] = zeile von spalte, [1] = Position in der Spalte (y)
# Der Wert wird in das Brett eingesetzt.
if len(pos[1]) > 0:
brett[pos[0], np.array(spalte)[0, pos[1]]] = np.array(spalte)[1, pos[1]] + 1
if self.__mitLog:
liste = [3, np.vstack((pos[0] + 1, np.array(spalte)[0, pos[1]] + 1, np.array(spalte)[1, pos[1]] + 1)).T]
return brett, liste
def loesungPruefen(self, brett):
# In jede Zeile, Spalte und Quadrat muss die Summe aller Zellwerte 45 ergeben.
spalten = np.sum(brett, axis=0)
zeilen = np.sum(brett, axis=1)
quadrate = np.zeros((3, 3))
for i in [0, 3, 6]:
for j in [0, 3, 6]:
quadrate[int(i / 3), int(j / 3)] = np.sum(np.sum(brett[i:i + 3, j:j + 3], axis=0), axis=0)
if np.sum(spalten) == 405 and np.sum(zeilen) == 405 and np.sum(quadrate) == 405:
self.__pruefung = 'Korrekt gelöst'
self.__state = True
return True
else:
self.__fault_z = np.array(np.where(zeilen != 45))
v = zeilen[self.__fault_z]
self.__fault_z = np.vstack((self.__fault_z, v))
self.__fault_s = np.array(np.where(spalten != 45))
v = spalten[self.__fault_s]
self.__fault_s = np.vstack((self.__fault_s, v))
self.__fault_q = np.array(np.where(quadrate != 45))
v = quadrate[self.__fault_q[0], self.__fault_q[1]]
self.__fault_q = np.vstack((self.__fault_q[0], self.__fault_q[1], v))
self.__pruefung = 'Fehler erkannt:'
self.state = False
return False
def __alleFinden(self, brett):
count = 0
old = np.sum(brett)
while not np.sum(self.__moeglicheZahlen(brett)) == 0:
count += 1
brett, liste1 = self.__einerSetzen(brett)
brett, liste2 = self.__nurEinmalQuadrat(brett)
brett, liste3 = self.__nurEinmalZeile(brett)
brett, liste4= self.__nurEinmalSpalte(brett)
if self.__mitLog:
self.__liste.append(liste1)
self.__liste.append(liste2)
self.__liste.append(liste3)
self.__liste.append(liste4)
new = np.sum(brett)
if old == new or count > 10:
ok = self.loesungPruefen(brett)
return brett, count, ok
old = new
return brett, count, self.loesungPruefen(brett)
def berechne(self):
self.__count = ''
self.__d = 1
start = time.time()
self.__brett, count, korrekt = self.__alleFinden(self.__brett)
self.__count = str(count)
if not korrekt:
if self.__mitLog:
self.__liste.append([6])
offen = self.__moeglicheZahlen(self.__brett)
liste = np.array(np.where(offen[:, :] > 0)).T
brett_kopie = self.__brett.copy()
for wert in liste:
self.__d += 1
self.__brett[wert[0], wert[1]] = wert[2] + 1
if self.__mitLog:
self.__liste.append([4, np.array([[wert[0], wert[1], wert[2] + 1]])])
self.__brett, count, korrekt = self.__alleFinden(self.__brett)
self.__count += '; ' + str(self.__d) + '/'+ str(count)
if korrekt:
if self.__mitLog:
self.__liste.append([5, np.array([[0, 0, 0]])])
break
else:
if self.__mitLog:
self.__liste.append([6, np.array([[0, 0, 0]])])
self.__brett = brett_kopie.copy()
else:
if self.__mitLog:
self.__liste.append([5, np.array([[0, 0, 0]])])
ende = time.time()
self.__time = ende - start
return self.__brett
#### Main ######
if __name__ == "__main__":
brett = np.zeros((9, 9), dtype=int)
# Beispiel: schwer
brett[0] = [0, 0, 7, 0, 0, 1, 6, 0, 0]
brett[1] = [4, 0, 0, 2, 5, 0, 9, 0, 0]
brett[2] = [0, 0, 0, 0, 3, 0, 0, 2, 0]
brett[3] = [0, 8, 0, 0, 0, 0, 7, 0, 0]
brett[4] = [9, 7, 0, 0, 0, 0, 0, 6, 8]
brett[5] = [0, 0, 5, 0, 0, 0, 0, 1, 0]
brett[6] = [0, 3, 0, 0, 6, 0, 0, 0, 0]
brett[7] = [0, 0, 4, 0, 2, 7, 0, 0, 5]
brett[8] = [0, 0, 9, 4, 0, 0, 2, 0, 0]
sudoku = sudokuLoesen(brett)
sudoku.mitLog = True
# Lösung suchen
sudoku.berechne()
# Lösung übernehmen
loesung = sudoku.brett
print(loesung)
Gerne lerne ich von eurer Erfahrung...