Kleine Sachen mit Python

Das Acht-Damenproblem ⇓

Noch'n Sudoku-Löser ⇓

Das Acht-Damenproblem

Die Aufgabe beim altbekannten Acht-Damenproblem ist es, acht Damen des Schachspieles so auf ein Schachbrett mit 8x8-Feldern aufzustellen, dass sie sich nicht gegenseitig schlagen können.

Eine Dame zieht dabei horizontal in einer Zeile, vertikal in einer Spalte und diagonal auf der Haupt- und Nebendiagonalen bis zum letzten Feld am jeweiligen Brettrand.

Das Problem kann man zu einem N-Damenproblem auf NxN-Feldern verallgemeinern.

Das Problem lässt mit Pythonmitteln elegant mit wenigen Zeilen lösen. Der rekursive Algorithmis liefert im Prinzip alle Lösungen für ein gegebenes N.

Einige Erläuterungen zum Python-Code:

1) Die Funktion fzelle(i,k) gibt einfach ein Zweiertupel zurück.

Die Funktion sindBedroht(zelle1,zelle2) überprüft, ob zwei Damen in zwei Zellen sich einander bedrohen. Liegen die Zellen in einer Spalte, auf einer Nebendiagonalen, auf einer Hauptdiagonalen oder in einer Reihe?

2) Die Funktion istVertraeglichMit(damenListe,zelle) überprüft, ob eine neue Zelle verträglich ist mit einer Liste von Damenpositionen. Eine Damenposition ist ein Tupel (i,k) für die Reihe i und die Spalte k. Die Damenpositionen in der Liste sind selbst untereinander verträglich, sie bedrohen sich also gegenseitig nicht und stellen damit eine Zwischenlösung dar.

Die Funktion verwendet eine sogenannte Listencomp (list comprehension). Diese hat hier den Aufbau

ergebnisListe=[f(elem) for elem in elemListe],

wobei für jedes Element elem der Liste die Funktion f(elem) berechnet wird, das Ergebnis wird der ergebnisListe hinzugefügt.

Der Iterator reduce aus dem Modul functools iteriert kumulierend über die Liste istSicher und führt dabei die genannte lambda-Funktion aus; für eine Liste [b1,b2,b3,b4] mit 4 boolschen Werten wird dann der Ausdruck (((b1 and b2) and b3) and b4) berechnet und zurück gegeben.

3) Die Funktion nDamenProblem(anzahlDamen) ruft die Hilfsfunktion setzeDame(reihe) mit der Anzahl der gewünschten Damen auf.

4) Die Hilfsfunktion setzeDame(reihe) ruft für die Fälle reihe>0 mit setzeDame(reihe-1) sich selbst wieder auf. Im Fall reihe==0 gibt es keine Lösung und die leere Liste [] wird in einer Liste zurück gegeben.

Die Funktion verwendet wieder eine Listencomp. Diese hat hier den Aufbau

ergebnisListe=[f(elem1,elem2) for elem1 in elemListe1
for elem2 in elemListe2 if bedingung(elem1,elem2)].

Es wird geschachtelt iteriert, die elem1-Schleife ist die äußere, die elem2-Schleife die innere Schleife. Die Funktion f(elem1,elem2) wird nur dann ausgeführt, wenn der Bedingungsausdruck hinter dem if erfüllt ist, wenn also gilt: bedingung(elem1,elem2)==True.

Die Funktion setzeDame(reihe-1) gibt beim Erstaufruf alle bisher möglichen Zwischenlösungen für die ersten (anzahlDamen-1) Damen zurück. Dann wird für die letzte Spalte (und für alle bisherigen Zwischenlösungen) überprüft, ob die Spaltenzellen jeweils verträglich sind mit der gerade betrachteten Zwischenlösung. Wenn dieses für eine Zelle der Fall ist, wird die Zelle mit loesung+[(reihe,spalte)] zur Lösung hinzugefügt. Wenn keine der Spaltenzellen verträglich mit der gerade betrachteten Zwischenlösung ist, wird diese auch nicht der Ergebnisliste angehängt und wird somit verworfen.

Wie startet die Rekursion am Ende der Aufrufkette? Beim Schritt reihe==0 mit der leeren Lösung [[]], beim zweiten Schritt mit der Lösungsliste (für 8 Damen):

[[(1,1)],[(1,2)],[(1,3)],[(1,4)],[(1,5)],[(1,6)],[(1,7)],[(1,8)]],

denn es gilt ja istVertraeglichMit([],zelle)==True für all diese Zellen.

Etwas Testerei

Mit 'Anzahl' ist hier die Anzahl der gefundenen Lösungen gemeint.

Das Programm läuft natürlich nur auf einem Prozessorkern, man bräuchte einen Algorithmus, der sich leicht parallelisieren lässt. Rekursive Algorithmen scheinen da wenig geeignet zu sein.

# Beginning Test ...

# Finished Test.

Lösungen N=5

Spiegellösung

[(1, 1), (2, 3), (3, 5), (4, 2), (5, 4)]

X
		X
				X
	X
			X

[(1, 5), (2, 3), (3, 1), (4, 4), (5, 2)]

				X
		X
X
			X
	X

[(1, 2), (2, 4), (3, 1), (4, 3), (5, 5)]

	X
			X
X
		X
				X

[(1, 4), (2, 2), (3, 5), (4, 3), (5, 1)]

			X
	X
				X
		X
X

[(1, 3), (2, 1), (3, 4), (4, 2), (5, 5)]

		X
x
			x
	x
				x

[(1, 3), (2, 5), (3, 2), (4, 4), (5, 1)]

		X
				x
	x
			x
x

[(1, 4), (2, 1), (3, 3), (4, 5), (5, 2)]

			X
X
		X
				X
	X

[(1, 2), (2, 5), (3, 3), (4, 1), (5, 4)]

	X
				X
		X
X
			X

[(1, 5), (2, 2), (3, 4), (4, 1), (5, 3)]

				X
	X
			X
X
		X

[(1, 1), (2, 4), (3, 2), (4, 5), (5, 3)]

X
			X
	X
				X
		X

Lösungen N=6

[(1, 2), (2, 4), (3, 6), (4, 1), (5, 3), (6, 5)]

	X
			X
					X
X
		X
				X

[(1, 5), (2, 3), (3, 1), (4, 6), (5, 4), (6, 2)]

				X
		X
X
					X
			X
	X

[(1, 4), (2, 1), (3, 5), (4, 2), (5, 6), (6, 3)]

			X
X
				X
	X
					X
		X

[(1, 3), (2, 6), (3, 2), (4, 5), (5, 1), (6, 4)]

		X
					X
	X
				X
X
			X

Da fällt doch gleich die strenge Regelmäßigkeit, die Symmetrien, der kleinen Lösungsmenge auf.

Die Rekursionskette für N=6

# Beginning Test ...

1 1 |
1 2 |
1 3 |
1 4 |
1 5 |
1 6 |
1 1 | 2 3 |
1 1 | 2 4 |
1 1 | 2 5 |
1 1 | 2 6 |
1 2 | 2 4 |
1 2 | 2 5 |
1 2 | 2 6 |
1 3 | 2 1 |
1 3 | 2 5 |
1 3 | 2 6 |
1 4 | 2 1 |
1 4 | 2 2 |
1 4 | 2 6 |
1 5 | 2 1 |
1 5 | 2 2 |
1 5 | 2 3 |
1 6 | 2 1 |
1 6 | 2 2 |
1 6 | 2 3 |
1 6 | 2 4 |
1 1 | 2 3 | 3 5 |
1 1 | 2 3 | 3 6 |
1 1 | 2 4 | 3 2 |
1 1 | 2 4 | 3 6 |
1 1 | 2 5 | 3 2 |
1 1 | 2 6 | 3 2 |
1 1 | 2 6 | 3 4 |
1 2 | 2 4 | 3 1 |
1 2 | 2 4 | 3 6 |
1 2 | 2 5 | 3 1 |
1 2 | 2 5 | 3 3 |
1 2 | 2 6 | 3 1 |
1 2 | 2 6 | 3 3 |
1 3 | 2 1 | 3 4 |
1 3 | 2 1 | 3 6 |
1 3 | 2 5 | 3 2 |
1 3 | 2 6 | 3 2 |
1 3 | 2 6 | 3 4 |
1 4 | 2 1 | 3 3 |
1 4 | 2 1 | 3 5 |
1 4 | 2 2 | 3 5 |
1 4 | 2 6 | 3 1 |
1 4 | 2 6 | 3 3 |
1 5 | 2 1 | 3 4 |
1 5 | 2 1 | 3 6 |
1 5 | 2 2 | 3 4 |
1 5 | 2 2 | 3 6 |
1 5 | 2 3 | 3 1 |
1 5 | 2 3 | 3 6 |
1 6 | 2 1 | 3 3 |
1 6 | 2 1 | 3 5 |
1 6 | 2 2 | 3 5 |
1 6 | 2 3 | 3 1 |
1 6 | 2 3 | 3 5 |
1 6 | 2 4 | 3 1 |
1 6 | 2 4 | 3 2 |
1 1 | 2 3 | 3 5 | 4 2 |
1 1 | 2 3 | 3 6 | 4 2 |
1 1 | 2 4 | 3 2 | 4 5 |
1 1 | 2 4 | 3 6 | 4 3 |
1 1 | 2 5 | 3 2 | 4 6 |
1 1 | 2 6 | 3 2 | 4 5 |
1 1 | 2 6 | 3 4 | 4 2 |
1 2 | 2 4 | 3 1 | 4 3 |
1 2 | 2 4 | 3 6 | 4 1 |
1 2 | 2 4 | 3 6 | 4 3 |
1 2 | 2 5 | 3 1 | 4 4 |
1 2 | 2 5 | 3 1 | 4 6 |
1 2 | 2 5 | 3 3 | 4 1 |
1 2 | 2 5 | 3 3 | 4 6 |
1 2 | 2 6 | 3 1 | 4 3 |
1 2 | 2 6 | 3 3 | 4 1 |
1 3 | 2 1 | 3 4 | 4 2 |
1 3 | 2 1 | 3 6 | 4 2 |
1 3 | 2 1 | 3 6 | 4 4 |
1 3 | 2 5 | 3 2 | 4 4 |
1 3 | 2 6 | 3 2 | 4 5 |
1 3 | 2 6 | 3 4 | 4 1 |
1 3 | 2 6 | 3 4 | 4 2 |
1 4 | 2 1 | 3 3 | 4 5 |
1 4 | 2 1 | 3 3 | 4 6 |
1 4 | 2 1 | 3 5 | 4 2 |
1 4 | 2 2 | 3 5 | 4 3 |
1 4 | 2 6 | 3 1 | 4 3 |
1 4 | 2 6 | 3 1 | 4 5 |
1 4 | 2 6 | 3 3 | 4 5 |
1 5 | 2 1 | 3 4 | 4 6 |
1 5 | 2 1 | 3 6 | 4 4 |
1 5 | 2 2 | 3 4 | 4 1 |
1 5 | 2 2 | 3 4 | 4 6 |
1 5 | 2 2 | 3 6 | 4 1 |
1 5 | 2 2 | 3 6 | 4 3 |
1 5 | 2 3 | 3 1 | 4 4 |
1 5 | 2 3 | 3 1 | 4 6 |
1 5 | 2 3 | 3 6 | 4 4 |
1 6 | 2 1 | 3 3 | 4 5 |
1 6 | 2 1 | 3 5 | 4 2 |
1 6 | 2 2 | 3 5 | 4 1 |
1 6 | 2 3 | 3 1 | 4 4 |
1 6 | 2 3 | 3 5 | 4 2 |
1 6 | 2 4 | 3 1 | 4 5 |
1 6 | 2 4 | 3 2 | 4 5 |
1 1 | 2 3 | 3 5 | 4 2 | 5 4 |
1 1 | 2 4 | 3 2 | 4 5 | 5 3 |
1 1 | 2 5 | 3 2 | 4 6 | 5 3 |
1 2 | 2 4 | 3 1 | 4 3 | 5 5 |
1 2 | 2 4 | 3 6 | 4 1 | 5 3 |
1 2 | 2 4 | 3 6 | 4 1 | 5 5 |
1 2 | 2 4 | 3 6 | 4 3 | 5 5 |
1 2 | 2 5 | 3 1 | 4 6 | 5 4 |
1 2 | 2 5 | 3 3 | 4 1 | 5 4 |
1 2 | 2 5 | 3 3 | 4 6 | 5 4 |
1 2 | 2 6 | 3 1 | 4 3 | 5 5 |
1 2 | 2 6 | 3 3 | 4 1 | 5 4 |
1 3 | 2 1 | 3 4 | 4 2 | 5 5 |
1 3 | 2 1 | 3 6 | 4 2 | 5 5 |
1 3 | 2 1 | 3 6 | 4 4 | 5 2 |
1 3 | 2 5 | 3 2 | 4 4 | 5 1 |
1 3 | 2 5 | 3 2 | 4 4 | 5 6 |
1 3 | 2 6 | 3 2 | 4 5 | 5 1 |
1 3 | 2 6 | 3 4 | 4 1 | 5 5 |
1 3 | 2 6 | 3 4 | 4 2 | 5 5 |
1 4 | 2 1 | 3 3 | 4 5 | 5 2 |
1 4 | 2 1 | 3 3 | 4 6 | 5 2 |
1 4 | 2 1 | 3 5 | 4 2 | 5 6 |
1 4 | 2 2 | 3 5 | 4 3 | 5 1 |
1 4 | 2 2 | 3 5 | 4 3 | 5 6 |
1 4 | 2 6 | 3 1 | 4 3 | 5 5 |
1 4 | 2 6 | 3 1 | 4 5 | 5 2 |
1 4 | 2 6 | 3 3 | 4 5 | 5 2 |
1 5 | 2 1 | 3 4 | 4 6 | 5 3 |
1 5 | 2 1 | 3 6 | 4 4 | 5 2 |
1 5 | 2 2 | 3 4 | 4 1 | 5 3 |
1 5 | 2 2 | 3 4 | 4 6 | 5 3 |
1 5 | 2 2 | 3 6 | 4 1 | 5 3 |
1 5 | 2 3 | 3 1 | 4 4 | 5 2 |
1 5 | 2 3 | 3 1 | 4 6 | 5 2 |
1 5 | 2 3 | 3 1 | 4 6 | 5 4 |
1 5 | 2 3 | 3 6 | 4 4 | 5 2 |
1 6 | 2 2 | 3 5 | 4 1 | 5 4 |
1 6 | 2 3 | 3 5 | 4 2 | 5 4 |
1 6 | 2 4 | 3 2 | 4 5 | 5 3 |
1 2 | 2 4 | 3 6 | 4 1 | 5 3 | 6 5 |
1 3 | 2 6 | 3 2 | 4 5 | 5 1 | 6 4 |
1 4 | 2 1 | 3 5 | 4 2 | 5 6 | 6 3 |
1 5 | 2 3 | 3 1 | 4 6 | 5 4 | 6 2 |

Lösungen:

[[(1 2), (2, 4), (3, 6), (4, 1), (5, 3), (6, 5)],

[(1, 3), (2, 6), (3, 2), (4, 5), (5, 1), (6, 4)],

[(1, 4), (2, 1), (3, 5), (4, 2), (5, 6), (6, 3)],

[(1, 5), (2, 3), (3, 1), (4, 6), (5, 4), (6, 2)]]

N: 6 | Anzahl: 4

# Finished Test.

Ich habe zunächst gedacht, nur 4 Lösungen im Fall N=6, da kann doch etwas nicht stimmen! Warum gibt es etwa keine Lösung mit der Zelle (1,1)? Einige Beispiele zeigen, dass es keine Lösung zu geben scheint, wenn eine Diagonalzelle (blaues Kreuz) gesetzt ist.

Man wird im Internet sicherlich etliche erschöpfende Ausführungen zum Damenproblem finden können.

X
			X
	X
				X
		X
					X

X
		X
				X
					X
			X
	X

X
					X
	X
				X
		X
			X

X
					X
			X
	X
				X
		X

Quellcode für Python 3

achtdamen.htm

achtdamen.py

Noch'n Sudoku-Löser — nachgebaut

Vor einiger Zeit trieb ich mich ein wenig in der rein funktionalen Programmiersprache Haskell herum. Haskell hat etwas, einen großen Reiz, Haskell ist elegant und bündig. Ich stolperte dabei über ein kleines, feines Haskell- Programm, Maggesi's Sudoku-Löser (http://web.math.unifi.it/users/maggesi/haskell_sudoku_solver.html) , das mich doch etliche Tage in den Bann zog nach dem Motto: Was passiert denn da in Gottes Namen nur? Ich habe es dabei für mich etwas Lesbarer gemacht und um Textausgaben erweitert: Maggesi's Sudoku-Löser. Python hat ja bei Haskell etliche Anleihen gemacht – was liegt näher, als einen kleinen prototypischen Löser in Python zu versuchen?
Das Rätsel Maggesi stellt das Sudoku-Spielfeld durch eine Funktion dar, ein Beispiel f : (1,2) → [7,8,9]. Ich mache es mir einfacher und nehme eine schlichte Datenstruktur, ein Zweiertupel aus den beiden Feldkoordinaten und einer Liste mit den möglichen Werten für das Feld, ein Beispiel ((1,2),[7,8,9]).

Der Algorithmus 1) getIntialList(inputList) Die Eingabeliste wird zunächst in eine Problemliste der Form [((1,2),5),((1,5),6),…,((9,8),6)] umgewandet, aus der ich die Initialliste erhalte, das ist eine Liste mit den möglichen Werten für jedes Sudoku-Feld. Die Python-Funktion zip (in Haskell: zip) fügt die Elemente zweier Listen elementweise zu einer neuen Liste von Zweiertupeln zusammen. Die Python-Funktion reduce (in Haskell: foldr) ist eine Faltungsfunktion, hier werden die Elemente einer Liste, hier problemList, mit Hilfe einer zweistelligen Funktion, hier das selbstdefinierte adjustCell, mit einem Startwert beginnend, hier sp, zusammengefasst. Ein Beispiel: reduce(lambda x,y:x+y,[1,2,3,4],0) berechnet ((((0+1)+2)+3)+4). Die Funktion ist hier einfach die normale Addition. Die Funktion verwendet Listencomps (list comprehensions), die Python auch von Haskell übernommen hat. Ein Beispiel: [k*k for k in [1,2,3,4,5,6] if k%2==0] erzeugt die Liste [4,16,25,36], der Operator % berechnet den Rest einer Dividion: 7%2=1. Die Elemente der Initialliste haben zunächst für alle Felder die Gestalt ((i,k),[1,2,3,4,5,6,7,8,9]). Das reduce-Konstrukt reduce(adjustCell,problemList,sp) wendet dann mitttels der Funktion adjustCell die drei Sudoku-Regeln an und löscht in der Werteliste [1,2,3,4,5,6,7,8,9] diejenigen Werte, die schon in Reihen, Zeilen und Dreier-Blöcken vorhanden sind; für das erste Feld erhält man etwa ((1,1),[3,9]).
2) adjustCell(sp,pp) Diese Funktion wendet die Sudoku-Regeln auf eine Zelle oder Feld an und löscht entsprechend aus der Werteliste vList den Wert val.
3) adjustCells(sol,pp) Diese Funktion wendet adjustCell auf eine Zwischenlösungliste sol an. sol ist eine Liste von Zweiertupeln aus Koordinatenpaaren und möglichen Feldwerten.
4) generateAll(solutionsList,cell) Diese Funktion wendet adjustCells auf eine Liste von Zwischenlösungslisten solutionsList an. Die aktuelle Lösungsliste sol ist eine Liste von Zweiertupeln, jeweils bestehend aus der Zelle und den möglichen Zellenwerten. dict(sol) macht daraus ein Wörterbuch (dictionary), dict(sol)[cell] liefert die möglichen Zellenwerte für die Zelle.
5) solveSudoku(inputList) Die Hauptroutine. Die Funktion erzeugt im Prinzip alle Lösungen des Sudoku-Rätsels ausgehend von der Liste, die die Initialliste enthält. Die Funktion generateAll schnappt sich den Initialwert [initialList] und das erste Element von allCells und wird ausgeführt; die zurück gegebene Ergebnisliste wird zusammen mit den zweiten Element von allCells für den nächsten Aufruf von generateAll verwendet, und so fort, bis auch das letzte Element von allCells verarbeitet worden ist. Man erhält eine Liste von Lösungen; die Liste ist leer, wenn es keine Lösung gibt. Prachtvoll!

Die Lösung Die eine Lösung für das verwendete Sudoku-Rätsel. Das Haskell-Programm konstruierte die gleiche Lösung.


Einblicke
Die vollständige Initialliste: Die gesetzten Felder sind blau gekennzeichnet.	Die Anzahl der Zwischenlösungen für jeden Iterationsschritt:
# Beginning Test ... ((1, 1), [3, 9]) ((1, 2), [5]) ((1, 3), [2, 3, 7, 9]) ((1, 4), [2, 3, 4, 7, 9]) ((1, 5), [6]) ((1, 6), [2, 3, 4, 9]) ((1, 7), [3, 4, 8, 9]) ((1, 8), [4, 8, 9]) ((1, 9), [1]) ((2, 1), [1, 3, 6, 9]) ((2, 2), [2, 6]) ((2, 3), [4]) ((2, 4), [8]) ((2, 5), [1, 2]) ((2, 6), [1, 2, 3, 5, 9]) ((2, 7), [3, 6, 9]) ((2, 8), [7((2, 9), [3, 6, 9]) ((3, 1), [8]) ((3, 2), [6, 7]) ((3, 3), [1, 3, 6, 7, 9]) ((3, 4), [1, 3, 4, 7, 9]) ((3, 5), [1, 4, 7]) ((3, 6), [1, 3, 4, 9]) ((3, 7), [3, 4, 6, 9]) ((3, 8), [5]) ((3, 9), [2]) ((4, 1), [2]) ((4, 2), [4, 6, 8]) ((4, 3), [1, 6, 8, 9]) ((4, 4), [1, 4]) ((4, 5), [5]) ((4, 6), [7]) ((4, 7), [1, 4, 6, 8, 9]) ((4, 8), [3]) ((4, 9), [4, 6, 9]) ((5, 1), [1, 4, 6, 9]) ((5, 2), [4, 6, 7, 8]) ((5, 3), [1, 5, 6, 7, 8, 9]) ((5, 4), [1, 2, 3, 4]) ((5, 5), [1, 2, 4, 8]) ((5, 6), [1, 2, 3, 4, 8]) ((5, 7), [1, 2, 4, 6, 7, 8, 9]) ((5, 8), [1, 2, 4, 8, 9]) ((5, 9), [4, 6, 7, 9]) ((6, 1), [1, 4]) ((6, 2), [3]) ((6, 3), [1, 7, 8]) ((6, 4), [6]) ((6, 5), [9]) ((6, 6), [1, 2, 4, 8]) ((6, 7), [1, 2, 4, 7, 8]) ((6, 8), [1, 2, 4, 8]) ((6, 9), [5]) ((7, 1), [7]) ((7, 2), [9]) ((7, 3), [2, 3, 6]) ((7, 4), [1, 2, 4, 5]) ((7, 5), [1, 2, 4]) ((7, 6), [1, 2, 4, 5]) ((7, 7), [1, 2, 3, 4]) ((7, 8), [1, 2, 4]) ((7, 9), [8]) ((8, 1), [3, 4]) ((8, 2), [1]) ((8, 3), [2, 3, 8]) ((8, 4), [2, 4, 7, 9]) ((8, 5), [2, 4, 7, 8]) ((8, 6), [6]) ((8, 7), [5]) ((8, 8), [2, 4, 9]) ((8, 9), [3, 4, 7, 9]) ((9, 1), [5]) ((9, 2), [2, 4, 8]) ((9, 3), [2, 8]) ((9, 4), [1, 2, 4, 7, 9]) ((9, 5), [3]) ((9, 6), [1, 2, 4, 8, 9]) ((9, 7), [1, 2, 4, 7, 9]) ((9, 8), [6]) ((9, 9), [4, 7, 9]) # Finished Test.	# Beginning Test … (1, 1) 1 (1, 2) 2 (1, 3) 2 (1, 4) 6 (1, 5) 18 (1, 6) 18 (1, 7) 28 (1, 8) 42 (1, 9) 25 (2, 1) 25 (2, 2) 71 (2, 3) 96 (2, 4) 96 (2, 5) 96 (2, 6) 67 (2, 7) 161 (2, 8) 154 (2, 9) 154 (3, 1) 60 (3, 2) 60 (3, 3) 44 (3, 4) 44 (3, 5) 132 (3, 6) 136 (3, 7) 120 (3, 8) 120 (3, 9) 120 (4, 1) 120 (4, 2) 120 (4, 3) 256 (4, 4) 640 (4, 5) 740 (4, 6) 740 (4, 7) 740 (4, 8) 704 (4, 9) 704 (5, 1) 408 (5, 2) 836 (5, 3) 1024 (5, 4) 2098 (5, 5) 3227 (5, 6) 5298 (5, 7) 6261 (5, 8) 6293 (5, 9) 3769 (6, 1) 739 (6, 2) 858 (6, 3) 858 (6, 4) 182 (6, 5) 182 (6, 6) 182 (6, 7) 114 (6, 8) 180 (6, 9) 122 (7, 1) 122 (7, 2) 122 (7, 3) 122 (7, 4) 308 (7, 5) 580 (7, 6) 224 (7, 7) 236 (7, 8) 133 (7, 9) 13 (8, 1) 13 (8, 2) 13 (8, 3) 13 (8, 4) 26 (8, 5) 42 (8, 6) 28 (8, 7) 28 (8, 8) 28 (8, 9) 11 (9, 1) 1 (9, 2) 1 (9, 3) 1 (9, 4) 1 (9, 5) 1 (9, 6) 1 (9, 7) 1 (9, 8) 1 (9, 9) 1 # Finished Test.
Wird die 5 in der ersten Zeile im Feld (1,2) nicht gesetzt, so werden nach einer kleinen Zeit 55 Lösungen gefunden.	# Beginning Test .. Anzahl: 55 # Finished Test.
Wird zusätzlich im Ausgangsrätsel im Feld (7,5) eine 1 gesetzt, wird keine Lösung gefunden.	# Beginning Test ... Anzahl: 0 # Finished Test.
Anmerkung Der angegebene Algorithmus ist natürlich nur programmiertechnisch elegant, er findet einfach nur alle Lösungen und ist an keiner Stelle zeitlich optimiert oder lösungstechnisch trickreich. Es kam mir auf die schlichte Eleganz an, wie sie ja auch (noch im größeren Maße) das Maggesi-Programm in Haskell zeigt.

Quellcode für Python 3

sudoku-py.html

sudoku.py.txt


© 2015 Bernd Ragutt Alle Rechte vorbehalten		letzte Änderung: 22. Februar 2018 Kruschtkiste