Startseite
Informatik
Algorithmen
Sortieren
Komprimieren
Suchen
DRUCK
2004
2005
2006
2007
2008
2009
Damenproblem
Damenproblem-kongruenzfrei
Springerproblem
Solitaire
Primzahltest
Datenstrukturen
Software-Engineering
Programmiersprachen
Künstliche Intelligenz
Schach
Privates
Inhalt
Damenproblem
Acht Damen auf dem Schachbrett dürfen sich nicht gegenseitig schlagen können.
Acht Damen auf dem Schachbrett dürfen sich nicht gegenseitig schlagen können.
Einführung
Theorie: Damenproblem
Also ich hab' kein Problem mit Damen
— Sie etwa? Was ist denn nun das Problem mit den Damen?
:-)
Definition
Das
Damenproblem
(8-Queens-Problem)
ist die Bezeichnung für die bereits im Jahre 1850 von
C. F. Gauß
(1777-1855)
aufgegriffene Aufgabe:
Die Gangart der Dame im Schachspiel finden Sie unter Schachregeln.
- Man finde eine Stellung für acht Damen auf einem Schachbrett, so dass keine zwei Damen sich gegenseitig schlagen können.
[INFODUDEN S. 151ff]
8x8-Brett
beschränken lässt.
Das
Acht-Damenproblem
formuliert er zum allgemeinen Damenproblem für ein
NxN-Brett
mit
N
Damen um.
Die Gangart der Dame im Schachspiel finden Sie unter Schachregeln.
Eine Lösung des Damenproblems
Alle Lösungen finden Sie weiter unten
Alle Lösungen finden Sie weiter unten
Der Algorithums
... zum Damenproblem lässt sich auf ein Suchproblem zurückführen:
eine vollständige
Tiefensuche
(Backtracking).
Hierzu sei mal ein kurzer Pseudoalgorithmus exemplarisch für den konkreten Fall „Schachbrett” angeführt.
Hierzu sei mal ein kurzer Pseudoalgorithmus exemplarisch für den konkreten Fall „Schachbrett” angeführt.
Die rekursive Suche zum Acht-Damenproblem
Suche(Zeile) // Die Rekursion muss mit der 1. Zeile angestoßen werden!
{
Wenn (Zeile > 8)
Dann:
// Rekursionsabbruch: eine Lösung gefunden
Gib das Brett aus!
Andernfalls:
Zähle mit Spalte von 'a' bis 'h' // jede Spalte wird betrachtet
{
Wenn (Kann eine Dame auf das Brett[Spalte,Zeile] plaziert werden,
ohne geschlagen zu werden?)
Dann:
1. Setze eine Dame auf das Brett[Spalte,Zeile]
2. Setze die Suche in der nächsten Zeile fort:
Suche(Zeile + 1); // (Tiefensuche)
3. Nimm die Dame wieder vom Brett[Spalte,Zeile]
}
}
Brett := LeeresBrett;
// Gibt alle Lösungen aus, in dem Fall die 92 Lösungen.
Suche(1);
Die
Rekursionstiefe
liegt bei maximal 8, da es auf dem Schachbrett 8 Zeilen bzw. 8 Spalten gibt.
Der Branchingfaktor liegt zwischen 1 und 8.
Der Branchingfaktor liegt zwischen 1 und 8.
Der unaufhörliche Drang zur Verallgemeinerung
So manchem ist es nicht genug, nur das Damenproblem auf ein
NxN-Damenproblem
bzw.
N2-Damenproblem
mit
N Damen
auszuweiten.
Die zwei Dimensionen des Bretts sind sogar noch zu wenig!
:-)
Wunderbar — statt einem quadratischen Brett einen Würfel oder mehr!
Ein Nk-Damenproblem mit der maximal möglichen Anzahl von Damen, das wäre doch mal eine Herausforderung! :-)
Wunderbar — statt einem quadratischen Brett einen Würfel oder mehr!
Ein Nk-Damenproblem mit der maximal möglichen Anzahl von Damen, das wäre doch mal eine Herausforderung! :-)
Implementierung
Implementierung: Damenproblem
Implementierung mit Java
Folgende Realisierung in Java zur Lösung des Damenproblems besteht aus zwei Dateien.
- QueenProblem.java implementiert den Algorithmus zum N-Damenproblem und enthält das Hauptprogramm.
- BoardOfQueens.java
implementiert ein
NxN-Brett,auf dem nur Damen plaziert werden können. Dieses Brett gibt z. B. Auskunft darüber, ob eine Dame auf einem Feld plaziert werden kann.
QueenProblem.java
import java.util.LinkedList;
import java.util.Iterator;
/**
* Der Algorithmus zum N-Damenproblem.
*
* Nur die private Methode "solve" bezeichnet den eigentlichen, rekursiven
* Algorithmus zum Damenproblem.
*/
public class QueenProblem {
/**
* Löst ein N-Damenproblem und gibt alle gefundenen Lösungen als Liste zurück.
* @param N Die Mächtigkeit des zugrundeliegenden Brettes (NxN-Brett).
* @return Liste aller gefundenen Lösungen.
* Eine Lösung besteht in Form einer BoardOfQueens-Instanz.
*/
public static LinkedList solve(int N) {
// Die zunächst leere Liste der Lösungen instanziieren.
LinkedList results = new LinkedList();
// Das Ausgangsbrett instanziieren, ein leeres NxN-Brett.
BoardOfQueens emptyboard = new BoardOfQueens(N);
// Das eigentliche Lösungsverfahren!
QueenProblem.solve(results, emptyboard, 0);
// Alle Lösungen als Liste zurückgeben!
return results;
}
/**
* Löst das Damenproblem rekursiv mittels Tiefensuche.
* Die Suchtiefe wird durch die Anzahl der Spalten des zugrundeliegenden
* Brettes bestimmt. Wenn alle Spalten mit Erfolg abgearbeitet werden konnten,
* liegt eine Lösung vor, das aktuelle Brett wird in diesem Falle als Kopie
* der Lösungsliste hinzugefügt.
* @param results Die Lösungsliste.
* @param current Das aktuelle Brett.
* @param x Der aktuelle Spaltenindex des Brettes.
*/
private static void solve(LinkedList results, BoardOfQueens current, int x) {
// Gibt es eine weitere Spalte, die noch besucht werden kann?
if (x < current.getN()) {
/* Lösungen suchen! */
for (int y = 0; y < current.getN(); y++) {
if (current.canSetQueenAt(x, y)) {
// Setze Dame auf Feld(x, y)
current.setQueenAt(x, y);
// Rekursionsschritt mit der nächsten Spalte(x + 1)
QueenProblem.solve(results, current, x + 1);
// Nimm die Dame wieder vom Feld(x, y),
// d.h. alten Zustand des Brettes wieder herstellen
current.unsetQueenAt(x, y);
}
// else: Dame kann nicht gesetzt werden (Sackgasse),
// deshalb weitere Suche in die Tiefe nicht nötig.
}
} else {
/* Lösung gefunden! */
// Aktuelles Brett als Klon in die Lösungsliste eintragen,
// damit der rekursiv angelegte Algorithmus auch noch nach weiteren
// Lösungen suchen kann.
results.add(current.clone());
}
}
/**
* Das Hauptprogramm, welches das Damenproblem für viele verschiedengroße
* Bretter lösen kann.
* Jedes einzelne Argument wird als natürliche Zahl N interpretiert
* (N-Damenproblem).
* @param arguments Die Argumente der Konsole, erwünscht ist nur die
* Auflistung natürlicher Zahlen (größer als Null).
*/
public static void main(String[] arguments) {
for (int i = 0; i < arguments.length; i++) {
try {
int N = Integer.parseInt(arguments[i]);
if (N > 0) {
/* Löse das N-Damenproblem! */
// Berechne alle Lösungen zum NxN-Brett.
LinkedList results = QueenProblem.solve(N);
// Gib lediglich die Anzahl der gefundenen Lösungen aus.
System.out.print("(" + N + " x " + N + ")");
System.out.println(" -> " + results.size() + " Result(s)\n");
// Gib die gefundenen Lösungen aus, falls vorhanden.
Iterator iterator = results.listIterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
} else {
System.err.println("Argument must be greater than '0'.");
}
} catch (NumberFormatException nfe) {
System.err.println(nfe.getMessage());
}
}
}
}
BoardOfQueens.java
/**
* Diese Klasse repräsentiert ein NxN-Brett, auf dem nur Damen stehen können
* und vereinfacht insbesondere den Algorithmus zum N-Damenproblem erheblich.
*/
public class BoardOfQueens implements Cloneable {
/**
* Gibt die Größe des Brettes an: NxN-Brett.
*/
private int N;
/**
* Ein zweidimensionales Array, welches das Brett darstellt.
* Jedes Feld gibt an, ob eine Dame drauf steht oder nicht (boolean).
*/
private boolean[][] board;
/**
* Instanziiert ein NxN-Brett.
* @param N Die Mächtigkeit des Brettes.
* Ein übliches Schachbrett wird mit 8 instanziiert.
*/
public BoardOfQueens(int N) {
// NxN-Brett
this.N = N;
this.board = new boolean[this.N][this.N];
// Jedes einzelne Feld wird als leer (false) gekennzeichnet.
for (int x = 0; x < this.N; x++) {
for (int y = 0; y < this.N; y++) {
this.board[x][y] = false;
}
}
}
/**
* Erzeugt eine neue BoardOfQueens-Instanz und sichert darin den aktuellen
* Zustand der aktuellen Objekt-Instanz.
* @return Eine Kopie des aktuellen Objekts.
*/
public Object clone() {
BoardOfQueens result = new BoardOfQueens(this.N);
for (int x = 0; x < this.N; x++) {
for (int y = 0; y < this.N; y++) {
result.board[x][y] = this.board[x][y];
}
}
return result;
}
/**
* Gibt die Mächtigkeit des Brettes zurück (NxN-Brett).
* @return Die Anzahl der Spalten bzw. der Zeilen.
*/
public int getN() {
return this.N;
}
/**
* Prüft, ob eine Dame auf das Feld(x, y) gesetzt werden kann.
* Eine Dame kann bzw. sollte nur gesetzt werden,
* wenn die Dame auf dem Feld(x, y) von keiner anderen bereits gesetzten
* Dame geschlagen werden kann.
* Diese Methode prüft nun konkret, ob die x-te Spalte leer ist,
* ob die y-te Zeile leer ist, ob die beiden Diagonalen, die
* durch das Feld(x, y) führen, leer sind.
* @param x Der Spaltenindex des Brettes.
* @param y Der Zeilenindex des Brettes.
* @return true, Dame kann auf das Feld(x, y) gesetzt werden.
*/
public boolean canSetQueenAt(int x, int y) {
return this.isEmptyCol(x)
&& this.isEmptyRow(y)
&& this.isEmptyFalling(x, y)
&& this.isEmptyRising(x, y);
}
/**
* Setzt eine Dame auf das Feld(x, y).
* @param x Der Spaltenindex des Brettes.
* @param y Der Zeilenindex des Brettes.
*/
public void setQueenAt(int x, int y) {
this.board[x][y] = true;
}
/**
* Nimmt eine Dame vom Feld(x, y).
* @param x Der Spaltenindex des Brettes.
* @param y Der Zeilenindex des Brettes.
*/
public void unsetQueenAt(int x, int y) {
this.board[x][y] = false;
}
/**
* Gibt den aktuellen Zustand des Brettes in Form eines Diagramms zurück.
* @return Das Diagramm als Zeichenkette.
*/
public String toString() {
String result = "";
for (int x = 0; x < this.N; x++) {
for (int y = 0; y < this.N; y++) {
if (this.board[x][y]) {
result += "|D";
} else {
result += "| ";
}
}
result += "|\n";
}
return result;
}
/* HILFSMETHODEN */
/**
* Prüft, ob die x-te Spalte leer ist.
* @param x Der Spaltenindex des Brettes.
* @return true, die x-te Spalte ist leer.
*/
private boolean isEmptyCol(int x) {
for (int y = 0; y < this.N; y++) {
if (this.board[x][y]) {
return false;
}
}
return true;
}
/**
* Prüft, ob die y-te Zeile leer ist.
* @param y Der Zeilenindex des Brettes.
* @return true, die y-te Zeile ist leer.
*/
private boolean isEmptyRow(int y) {
for (int x = 0; x < this.N; x++) {
if (this.board[x][y]) {
return false;
}
}
return true;
}
/**
* Prüft, ob die fallende Diagonale, die durch das Feld(x, y) führt,
* leer ist.
* @param x Der Spaltenindex des Brettes.
* @param y Der Zeilenindex des Brettes.
* @return true, die fallende Diagonale durch (x,y) ist leer.
*/
private boolean isEmptyFalling(int x, int y) {
int min = Math.min(x, y);
x -= min;
y -= min;
while (Math.max(x, y) < this.N) {
if (this.board[x][y]) {
return false;
}
x++;
y++;
}
return true;
}
/**
* Prüft, ob die steigende Diagonale, die durch das Feld(x, y) führt,
* leer ist.
* @param x Der Spaltenindex des Brettes.
* @param y Der Zeilenindex des Brettes.
* @return true, die steigende Diagonale durch (x,y) ist leer.
*/
private boolean isEmptyRising(int x, int y) {
int min = Math.min(x, this.N - y - 1);
x -= min;
y += min;
while (Math.max(x, this.N - y - 1) < this.N) {
if (this.board[x][y]) {
return false;
}
x++;
y--;
}
return true;
}
}
Ergebnisse
Ergebnisse zum Damenproblem
Um Lösungen zum oben angegebenen Algorithmus zu erhalten,
muss das Hauptprogramm mit den entsprechenden Parametern ausgeführt werden.
Hierzu ein paar Beispiele:
C:\> java QueenProblem 8
gibt alle Lösungen zum Damenproblem im Sinne der von Gauß aufgegriffenen Aufgabe aus (Schachbrett).C:\> java QueenProblem 6
gibt alle Lösungen zum Damenproblem bzgl. eines6x6-Brettesaus.C:\> java QueenProblem 1 2 3 4 5 6 7 8
gibt alle Lösungen zum Damenproblem bzgl. der Bretter1x1, 2x2, 3x3, ... 8x8aus.
java QueenProblem 1 2 3 4 5 6 7 8
(1 x 1) -> 1 Result(s)
|D|
(2 x 2) -> 0 Result(s)
(3 x 3) -> 0 Result(s)
(4 x 4) -> 2 Result(s)
| |D| | |
| | | |D|
|D| | | |
| | |D| |
| | |D| |
|D| | | |
| | | |D|
| |D| | |
(5 x 5) -> 10 Result(s)
|D| | | | |
| | |D| | |
| | | | |D|
| |D| | | |
| | | |D| |
|D| | | | |
| | | |D| |
| |D| | | |
| | | | |D|
| | |D| | |
| |D| | | |
| | | |D| |
|D| | | | |
| | |D| | |
| | | | |D|
| |D| | | |
| | | | |D|
| | |D| | |
|D| | | | |
| | | |D| |
| | |D| | |
|D| | | | |
| | | |D| |
| |D| | | |
| | | | |D|
| | |D| | |
| | | | |D|
| |D| | | |
| | | |D| |
|D| | | | |
| | | |D| |
|D| | | | |
| | |D| | |
| | | | |D|
| |D| | | |
| | | |D| |
| |D| | | |
| | | | |D|
| | |D| | |
|D| | | | |
| | | | |D|
| |D| | | |
| | | |D| |
|D| | | | |
| | |D| | |
| | | | |D|
| | |D| | |
|D| | | | |
| | | |D| |
| |D| | | |
(6 x 6) -> 4 Result(s)
| |D| | | | |
| | | |D| | |
| | | | | |D|
|D| | | | | |
| | |D| | | |
| | | | |D| |
| | |D| | | |
| | | | | |D|
| |D| | | | |
| | | | |D| |
|D| | | | | |
| | | |D| | |
| | | |D| | |
|D| | | | | |
| | | | |D| |
| |D| | | | |
| | | | | |D|
| | |D| | | |
| | | | |D| |
| | |D| | | |
|D| | | | | |
| | | | | |D|
| | | |D| | |
| |D| | | | |
(7 x 7) -> 40 Result(s)
|D| | | | | | |
| | |D| | | | |
| | | | |D| | |
| | | | | | |D|
| |D| | | | | |
| | | |D| | | |
| | | | | |D| |
|D| | | | | | |
| | | |D| | | |
| | | | | | |D|
| | |D| | | | |
| | | | | |D| |
| |D| | | | | |
| | | | |D| | |
|D| | | | | | |
| | | | |D| | |
| |D| | | | | |
| | | | | |D| |
| | |D| | | | |
| | | | | | |D|
| | | |D| | | |
|D| | | | | | |
| | | | | |D| |
| | | |D| | | |
| |D| | | | | |
| | | | | | |D|
| | | | |D| | |
| | |D| | | | |
| |D| | | | | |
| | | |D| | | |
|D| | | | | | |
| | | | | | |D|
| | | | |D| | |
| | |D| | | | |
| | | | | |D| |
| |D| | | | | |
| | | |D| | | |
| | | | | |D| |
|D| | | | | | |
| | |D| | | | |
| | | | |D| | |
| | | | | | |D|
| |D| | | | | |
| | | | |D| | |
|D| | | | | | |
| | | |D| | | |
| | | | | | |D|
| | |D| | | | |
| | | | | |D| |
| |D| | | | | |
| | | | |D| | |
| | |D| | | | |
|D| | | | | | |
| | | | | | |D|
| | | |D| | | |
| | | | | |D| |
| |D| | | | | |
| | | | |D| | |
| | | | | | |D|
| | | |D| | | |
|D| | | | | | |
| | |D| | | | |
| | | | | |D| |
| |D| | | | | |
| | | | | |D| |
| | |D| | | | |
| | | | | | |D|
| | | |D| | | |
|D| | | | | | |
| | | | |D| | |
| |D| | | | | |
| | | | | | |D|
| | | | |D| | |
| | |D| | | | |
|D| | | | | | |
| | | | | |D| |
| | | |D| | | |
| | |D| | | | |
|D| | | | | | |
| | | | | |D| |
| |D| | | | | |
| | | | |D| | |
| | | | | | |D|
| | | |D| | | |
| | |D| | | | |
|D| | | | | | |
| | | | | |D| |
| | | |D| | | |
| |D| | | | | |
| | | | | | |D|
| | | | |D| | |
| | |D| | | | |
| | | | |D| | |
| | | | | | |D|
| |D| | | | | |
| | | |D| | | |
| | | | | |D| |
|D| | | | | | |
| | |D| | | | |
| | | | | |D| |
| |D| | | | | |
| | | | |D| | |
|D| | | | | | |
| | | |D| | | |
| | | | | | |D|
| | |D| | | | |
| | | | | | |D|
| |D| | | | | |
| | | |D| | | |
| | | | | |D| |
|D| | | | | | |
| | | | |D| | |
| | |D| | | | |
| | | | | | |D|
| | | |D| | | |
|D| | | | | | |
| | | | |D| | |
| |D| | | | | |
| | | | | |D| |
| | | |D| | | |
|D| | | | | | |
| | |D| | | | |
| | | | | |D| |
| |D| | | | | |
| | | | | | |D|
| | | | |D| | |
| | | |D| | | |
|D| | | | | | |
| | | | |D| | |
| |D| | | | | |
| | | | | |D| |
| | |D| | | | |
| | | | | | |D|
| | | |D| | | |
| |D| | | | | |
| | | | | | |D|
| | | | |D| | |
| | |D| | | | |
|D| | | | | | |
| | | | | |D| |
| | | |D| | | |
| | | | | |D| |
|D| | | | | | |
| | |D| | | | |
| | | | |D| | |
| | | | | | |D|
| |D| | | | | |
| | | |D| | | |
| | | | | | |D|
| | |D| | | | |
| | | | | |D| |
| |D| | | | | |
| | | | |D| | |
|D| | | | | | |
| | | |D| | | |
| | | | | | |D|
| | | | |D| | |
| |D| | | | | |
| | | | | |D| |
|D| | | | | | |
| | |D| | | | |
| | | | |D| | |
|D| | | | | | |
| | | |D| | | |
| | | | | | |D|
| | |D| | | | |
| | | | | |D| |
| |D| | | | | |
| | | | |D| | |
|D| | | | | | |
| | | | | |D| |
| | | |D| | | |
| |D| | | | | |
| | | | | | |D|
| | |D| | | | |
| | | | |D| | |
| |D| | | | | |
| | | | | |D| |
| | |D| | | | |
| | | | | | |D|
| | | |D| | | |
|D| | | | | | |
| | | | |D| | |
| | |D| | | | |
|D| | | | | | |
| | | | | |D| |
| | | |D| | | |
| |D| | | | | |
| | | | | | |D|
| | | | |D| | |
| | | | | | |D|
| |D| | | | | |
| | | |D| | | |
| | | | | |D| |
|D| | | | | | |
| | |D| | | | |
| | | | |D| | |
| | | | | | |D|
| |D| | | | | |
| | | | | |D| |
| | |D| | | | |
|D| | | | | | |
| | | |D| | | |
| | | | | |D| |
|D| | | | | | |
| | |D| | | | |
| | | | |D| | |
| | | | | | |D|
| |D| | | | | |
| | | |D| | | |
| | | | | |D| |
| |D| | | | | |
| | | | |D| | |
|D| | | | | | |
| | | |D| | | |
| | | | | | |D|
| | |D| | | | |
| | | | | |D| |
| | |D| | | | |
|D| | | | | | |
| | | |D| | | |
| | | | | | |D|
| | | | |D| | |
| |D| | | | | |
| | | | | |D| |
| | |D| | | | |
| | | | |D| | |
| | | | | | |D|
|D| | | | | | |
| | | |D| | | |
| |D| | | | | |
| | | | | |D| |
| | |D| | | | |
| | | | | | |D|
| | | |D| | | |
|D| | | | | | |
| | | | |D| | |
| |D| | | | | |
| | | | | |D| |
| | | |D| | | |
| |D| | | | | |
| | | | | | |D|
| | | | |D| | |
| | |D| | | | |
|D| | | | | | |
| | | | | |D| |
| | | |D| | | |
| | | | | | |D|
|D| | | | | | |
| | |D| | | | |
| | | | |D| | |
| |D| | | | | |
| | | | | | |D|
| |D| | | | | |
| | | |D| | | |
| | | | | |D| |
|D| | | | | | |
| | |D| | | | |
| | | | |D| | |
| | | | | | |D|
| | |D| | | | |
| | | | | |D| |
| |D| | | | | |
| | | | |D| | |
|D| | | | | | |
| | | |D| | | |
| | | | | | |D|
| | | |D| | | |
|D| | | | | | |
| | | | |D| | |
| |D| | | | | |
| | | | | |D| |
| | |D| | | | |
| | | | | | |D|
| | | | |D| | |
| | |D| | | | |
|D| | | | | | |
| | | | | |D| |
| | | |D| | | |
| |D| | | | | |
(8 x 8) -> 92 Result(s)
|D| | | | | | | |
| | | | |D| | | |
| | | | | | | |D|
| | | | | |D| | |
| | |D| | | | | |
| | | | | | |D| |
| |D| | | | | | |
| | | |D| | | | |
|D| | | | | | | |
| | | | | |D| | |
| | | | | | | |D|
| | |D| | | | | |
| | | | | | |D| |
| | | |D| | | | |
| |D| | | | | | |
| | | | |D| | | |
|D| | | | | | | |
| | | | | | |D| |
| | | |D| | | | |
| | | | | |D| | |
| | | | | | | |D|
| |D| | | | | | |
| | | | |D| | | |
| | |D| | | | | |
|D| | | | | | | |
| | | | | | |D| |
| | | | |D| | | |
| | | | | | | |D|
| |D| | | | | | |
| | | |D| | | | |
| | | | | |D| | |
| | |D| | | | | |
| |D| | | | | | |
| | | |D| | | | |
| | | | | |D| | |
| | | | | | | |D|
| | |D| | | | | |
|D| | | | | | | |
| | | | | | |D| |
| | | | |D| | | |
| |D| | | | | | |
| | | | |D| | | |
| | | | | | |D| |
|D| | | | | | | |
| | |D| | | | | |
| | | | | | | |D|
| | | | | |D| | |
| | | |D| | | | |
| |D| | | | | | |
| | | | |D| | | |
| | | | | | |D| |
| | | |D| | | | |
|D| | | | | | | |
| | | | | | | |D|
| | | | | |D| | |
| | |D| | | | | |
| |D| | | | | | |
| | | | | |D| | |
|D| | | | | | | |
| | | | | | |D| |
| | | |D| | | | |
| | | | | | | |D|
| | |D| | | | | |
| | | | |D| | | |
| |D| | | | | | |
| | | | | |D| | |
| | | | | | | |D|
| | |D| | | | | |
|D| | | | | | | |
| | | |D| | | | |
| | | | | | |D| |
| | | | |D| | | |
| |D| | | | | | |
| | | | | | |D| |
| | |D| | | | | |
| | | | | |D| | |
| | | | | | | |D|
| | | | |D| | | |
|D| | | | | | | |
| | | |D| | | | |
| |D| | | | | | |
| | | | | | |D| |
| | | | |D| | | |
| | | | | | | |D|
|D| | | | | | | |
| | | |D| | | | |
| | | | | |D| | |
| | |D| | | | | |
| |D| | | | | | |
| | | | | | | |D|
| | | | | |D| | |
|D| | | | | | | |
| | |D| | | | | |
| | | | |D| | | |
| | | | | | |D| |
| | | |D| | | | |
| | |D| | | | | |
|D| | | | | | | |
| | | | | | |D| |
| | | | |D| | | |
| | | | | | | |D|
| |D| | | | | | |
| | | |D| | | | |
| | | | | |D| | |
| | |D| | | | | |
| | | | |D| | | |
| |D| | | | | | |
| | | | | | | |D|
|D| | | | | | | |
| | | | | | |D| |
| | | |D| | | | |
| | | | | |D| | |
| | |D| | | | | |
| | | | |D| | | |
| |D| | | | | | |
| | | | | | | |D|
| | | | | |D| | |
| | | |D| | | | |
| | | | | | |D| |
|D| | | | | | | |
| | |D| | | | | |
| | | | |D| | | |
| | | | | | |D| |
|D| | | | | | | |
| | | |D| | | | |
| |D| | | | | | |
| | | | | | | |D|
| | | | | |D| | |
| | |D| | | | | |
| | | | |D| | | |
| | | | | | | |D|
| | | |D| | | | |
|D| | | | | | | |
| | | | | | |D| |
| |D| | | | | | |
| | | | | |D| | |
| | |D| | | | | |
| | | | | |D| | |
| |D| | | | | | |
| | | | |D| | | |
| | | | | | | |D|
|D| | | | | | | |
| | | | | | |D| |
| | | |D| | | | |
| | |D| | | | | |
| | | | | |D| | |
| |D| | | | | | |
| | | | | | |D| |
|D| | | | | | | |
| | | |D| | | | |
| | | | | | | |D|
| | | | |D| | | |
| | |D| | | | | |
| | | | | |D| | |
| |D| | | | | | |
| | | | | | |D| |
| | | | |D| | | |
|D| | | | | | | |
| | | | | | | |D|
| | | |D| | | | |
| | |D| | | | | |
| | | | | |D| | |
| | | |D| | | | |
|D| | | | | | | |
| | | | | | | |D|
| | | | |D| | | |
| | | | | | |D| |
| |D| | | | | | |
| | |D| | | | | |
| | | | | |D| | |
| | | |D| | | | |
| |D| | | | | | |
| | | | | | | |D|
| | | | |D| | | |
| | | | | | |D| |
|D| | | | | | | |
| | |D| | | | | |
| | | | | |D| | |
| | | | | | | |D|
|D| | | | | | | |
| | | |D| | | | |
| | | | | | |D| |
| | | | |D| | | |
| |D| | | | | | |
| | |D| | | | | |
| | | | | |D| | |
| | | | | | | |D|
|D| | | | | | | |
| | | | |D| | | |
| | | | | | |D| |
| |D| | | | | | |
| | | |D| | | | |
| | |D| | | | | |
| | | | | |D| | |
| | | | | | | |D|
| |D| | | | | | |
| | | |D| | | | |
|D| | | | | | | |
| | | | | | |D| |
| | | | |D| | | |
| | |D| | | | | |
| | | | | | |D| |
| |D| | | | | | |
| | | | | | | |D|
| | | | |D| | | |
|D| | | | | | | |
| | | |D| | | | |
| | | | | |D| | |
| | |D| | | | | |
| | | | | | |D| |
| |D| | | | | | |
| | | | | | | |D|
| | | | | |D| | |
| | | |D| | | | |
|D| | | | | | | |
| | | | |D| | | |
| | |D| | | | | |
| | | | | | | |D|
| | | |D| | | | |
| | | | | | |D| |
|D| | | | | | | |
| | | | | |D| | |
| |D| | | | | | |
| | | | |D| | | |
| | | |D| | | | |
|D| | | | | | | |
| | | | |D| | | |
| | | | | | | |D|
| |D| | | | | | |
| | | | | | |D| |
| | |D| | | | | |
| | | | | |D| | |
| | | |D| | | | |
|D| | | | | | | |
| | | | |D| | | |
| | | | | | | |D|
| | | | | |D| | |
| | |D| | | | | |
| | | | | | |D| |
| |D| | | | | | |
| | | |D| | | | |
| |D| | | | | | |
| | | | |D| | | |
| | | | | | | |D|
| | | | | |D| | |
|D| | | | | | | |
| | |D| | | | | |
| | | | | | |D| |
| | | |D| | | | |
| |D| | | | | | |
| | | | | | |D| |
| | |D| | | | | |
| | | | | |D| | |
| | | | | | | |D|
|D| | | | | | | |
| | | | |D| | | |
| | | |D| | | | |
| |D| | | | | | |
| | | | | | |D| |
| | |D| | | | | |
| | | | | |D| | |
| | | | | | | |D|
| | | | |D| | | |
|D| | | | | | | |
| | | |D| | | | |
| |D| | | | | | |
| | | | | | |D| |
| | | | |D| | | |
|D| | | | | | | |
| | | | | | | |D|
| | | | | |D| | |
| | |D| | | | | |
| | | |D| | | | |
| |D| | | | | | |
| | | | | | | |D|
| | | | |D| | | |
| | | | | | |D| |
|D| | | | | | | |
| | |D| | | | | |
| | | | | |D| | |
| | | |D| | | | |
| |D| | | | | | |
| | | | | | | |D|
| | | | | |D| | |
|D| | | | | | | |
| | |D| | | | | |
| | | | |D| | | |
| | | | | | |D| |
| | | |D| | | | |
| | | | | |D| | |
|D| | | | | | | |
| | | | |D| | | |
| |D| | | | | | |
| | | | | | | |D|
| | |D| | | | | |
| | | | | | |D| |
| | | |D| | | | |
| | | | | |D| | |
| | | | | | | |D|
| |D| | | | | | |
| | | | | | |D| |
|D| | | | | | | |
| | |D| | | | | |
| | | | |D| | | |
| | | |D| | | | |
| | | | | |D| | |
| | | | | | | |D|
| | |D| | | | | |
|D| | | | | | | |
| | | | | | |D| |
| | | | |D| | | |
| |D| | | | | | |
| | | |D| | | | |
| | | | | | |D| |
|D| | | | | | | |
| | | | | | | |D|
| | | | |D| | | |
| |D| | | | | | |
| | | | | |D| | |
| | |D| | | | | |
| | | |D| | | | |
| | | | | | |D| |
| | |D| | | | | |
| | | | | | | |D|
| |D| | | | | | |
| | | | |D| | | |
|D| | | | | | | |
| | | | | |D| | |
| | | |D| | | | |
| | | | | | |D| |
| | | | |D| | | |
| |D| | | | | | |
| | | | | |D| | |
|D| | | | | | | |
| | |D| | | | | |
| | | | | | | |D|
| | | |D| | | | |
| | | | | | |D| |
| | | | |D| | | |
| | |D| | | | | |
|D| | | | | | | |
| | | | | |D| | |
| | | | | | | |D|
| |D| | | | | | |
| | | |D| | | | |
| | | | | | | |D|
|D| | | | | | | |
| | |D| | | | | |
| | | | | |D| | |
| |D| | | | | | |
| | | | | | |D| |
| | | | |D| | | |
| | | |D| | | | |
| | | | | | | |D|
|D| | | | | | | |
| | | | |D| | | |
| | | | | | |D| |
| |D| | | | | | |
| | | | | |D| | |
| | |D| | | | | |
| | | |D| | | | |
| | | | | | | |D|
| | | | |D| | | |
| | |D| | | | | |
|D| | | | | | | |
| | | | | | |D| |
| |D| | | | | | |
| | | | | |D| | |
| | | | |D| | | |
|D| | | | | | | |
| | | |D| | | | |
| | | | | |D| | |
| | | | | | | |D|
| |D| | | | | | |
| | | | | | |D| |
| | |D| | | | | |
| | | | |D| | | |
|D| | | | | | | |
| | | | | | | |D|
| | | |D| | | | |
| |D| | | | | | |
| | | | | | |D| |
| | |D| | | | | |
| | | | | |D| | |
| | | | |D| | | |
|D| | | | | | | |
| | | | | | | |D|
| | | | | |D| | |
| | |D| | | | | |
| | | | | | |D| |
| |D| | | | | | |
| | | |D| | | | |
| | | | |D| | | |
| |D| | | | | | |
| | | |D| | | | |
| | | | | |D| | |
| | | | | | | |D|
| | |D| | | | | |
|D| | | | | | | |
| | | | | | |D| |
| | | | |D| | | |
| |D| | | | | | |
| | | |D| | | | |
| | | | | | |D| |
| | |D| | | | | |
| | | | | | | |D|
| | | | | |D| | |
|D| | | | | | | |
| | | | |D| | | |
| |D| | | | | | |
| | | | | |D| | |
|D| | | | | | | |
| | | | | | |D| |
| | | |D| | | | |
| | | | | | | |D|
| | |D| | | | | |
| | | | |D| | | |
| |D| | | | | | |
| | | | | | | |D|
|D| | | | | | | |
| | | |D| | | | |
| | | | | | |D| |
| | |D| | | | | |
| | | | | |D| | |
| | | | |D| | | |
| | |D| | | | | |
|D| | | | | | | |
| | | | | |D| | |
| | | | | | | |D|
| |D| | | | | | |
| | | |D| | | | |
| | | | | | |D| |
| | | | |D| | | |
| | |D| | | | | |
|D| | | | | | | |
| | | | | | |D| |
| |D| | | | | | |
| | | | | | | |D|
| | | | | |D| | |
| | | |D| | | | |
| | | | |D| | | |
| | |D| | | | | |
| | | | | | | |D|
| | | |D| | | | |
| | | | | | |D| |
|D| | | | | | | |
| | | | | |D| | |
| |D| | | | | | |
| | | | |D| | | |
| | | | | | |D| |
|D| | | | | | | |
| | |D| | | | | |
| | | | | | | |D|
| | | | | |D| | |
| | | |D| | | | |
| |D| | | | | | |
| | | | |D| | | |
| | | | | | |D| |
|D| | | | | | | |
| | | |D| | | | |
| |D| | | | | | |
| | | | | | | |D|
| | | | | |D| | |
| | |D| | | | | |
| | | | |D| | | |
| | | | | | |D| |
| |D| | | | | | |
| | | |D| | | | |
| | | | | | | |D|
|D| | | | | | | |
| | |D| | | | | |
| | | | | |D| | |
| | | | |D| | | |
| | | | | | |D| |
| |D| | | | | | |
| | | | | |D| | |
| | |D| | | | | |
|D| | | | | | | |
| | | |D| | | | |
| | | | | | | |D|
| | | | |D| | | |
| | | | | | |D| |
| |D| | | | | | |
| | | | | |D| | |
| | |D| | | | | |
|D| | | | | | | |
| | | | | | | |D|
| | | |D| | | | |
| | | | |D| | | |
| | | | | | |D| |
| | | |D| | | | |
|D| | | | | | | |
| | |D| | | | | |
| | | | | | | |D|
| | | | | |D| | |
| |D| | | | | | |
| | | | |D| | | |
| | | | | | | |D|
| | | |D| | | | |
|D| | | | | | | |
| | |D| | | | | |
| | | | | |D| | |
| |D| | | | | | |
| | | | | | |D| |
| | | | |D| | | |
| | | | | | | |D|
| | | |D| | | | |
|D| | | | | | | |
| | | | | | |D| |
| |D| | | | | | |
| | | | | |D| | |
| | |D| | | | | |
| | | | | |D| | |
|D| | | | | | | |
| | | | |D| | | |
| |D| | | | | | |
| | | | | | | |D|
| | |D| | | | | |
| | | | | | |D| |
| | | |D| | | | |
| | | | | |D| | |
| |D| | | | | | |
| | | | | | |D| |
|D| | | | | | | |
| | |D| | | | | |
| | | | |D| | | |
| | | | | | | |D|
| | | |D| | | | |
| | | | | |D| | |
| |D| | | | | | |
| | | | | | |D| |
|D| | | | | | | |
| | | |D| | | | |
| | | | | | | |D|
| | | | |D| | | |
| | |D| | | | | |
| | | | | |D| | |
| | |D| | | | | |
|D| | | | | | | |
| | | | | | |D| |
| | | | |D| | | |
| | | | | | | |D|
| |D| | | | | | |
| | | |D| | | | |
| | | | | |D| | |
| | |D| | | | | |
|D| | | | | | | |
| | | | | | | |D|
| | | |D| | | | |
| |D| | | | | | |
| | | | | | |D| |
| | | | |D| | | |
| | | | | |D| | |
| | |D| | | | | |
|D| | | | | | | |
| | | | | | | |D|
| | | | |D| | | |
| |D| | | | | | |
| | | |D| | | | |
| | | | | | |D| |
| | | | | |D| | |
| | |D| | | | | |
| | | | |D| | | |
| | | | | | |D| |
|D| | | | | | | |
| | | |D| | | | |
| |D| | | | | | |
| | | | | | | |D|
| | | | | |D| | |
| | |D| | | | | |
| | | | |D| | | |
| | | | | | | |D|
|D| | | | | | | |
| | | |D| | | | |
| |D| | | | | | |
| | | | | | |D| |
| | | | | |D| | |
| | |D| | | | | |
| | | | | | |D| |
| |D| | | | | | |
| | | |D| | | | |
| | | | | | | |D|
|D| | | | | | | |
| | | | |D| | | |
| | | | | |D| | |
| | |D| | | | | |
| | | | | | |D| |
| |D| | | | | | |
| | | | | | | |D|
| | | | |D| | | |
|D| | | | | | | |
| | | |D| | | | |
| | | | | |D| | |
| | |D| | | | | |
| | | | | | |D| |
| | | |D| | | | |
|D| | | | | | | |
| | | | | | | |D|
| |D| | | | | | |
| | | | |D| | | |
| | | | | |D| | |
| | | |D| | | | |
|D| | | | | | | |
| | | | |D| | | |
| | | | | | | |D|
| |D| | | | | | |
| | | | | | |D| |
| | |D| | | | | |
| | | | | |D| | |
| | | |D| | | | |
| |D| | | | | | |
| | | | | | | |D|
| | | | |D| | | |
| | | | | | |D| |
|D| | | | | | | |
| | |D| | | | | |
| | | | | |D| | |
| | | |D| | | | |
| | | | | | |D| |
|D| | | | | | | |
| | |D| | | | | |
| | | | |D| | | |
| |D| | | | | | |
| | | | | | | |D|
| | | | | |D| | |
| | | |D| | | | |
| | | | | | |D| |
|D| | | | | | | |
| | | | | | | |D|
| |D| | | | | | |
| | | | |D| | | |
| | |D| | | | | |
| | | | | |D| | |
| | | | | | | |D|
| |D| | | | | | |
| | | |D| | | | |
|D| | | | | | | |
| | | | | | |D| |
| | | | |D| | | |
| | |D| | | | | |
| | | | | | |D| |
|D| | | | | | | |
| | |D| | | | | |
| | | | | | | |D|
| | | | | |D| | |
| | | |D| | | | |
| |D| | | | | | |
| | | | |D| | | |
| | | | | | |D| |
| |D| | | | | | |
| | | |D| | | | |
|D| | | | | | | |
| | | | | | | |D|
| | | | |D| | | |
| | |D| | | | | |
| | | | | |D| | |
| | | | | | |D| |
| |D| | | | | | |
| | | | | |D| | |
| | |D| | | | | |
|D| | | | | | | |
| | | |D| | | | |
| | | | | | | |D|
| | | | |D| | | |
| | | | | | |D| |
| | |D| | | | | |
|D| | | | | | | |
| | | | | |D| | |
| | | | | | | |D|
| | | | |D| | | |
| |D| | | | | | |
| | | |D| | | | |
| | | | | | |D| |
| | |D| | | | | |
| | | | | | | |D|
| |D| | | | | | |
| | | | |D| | | |
|D| | | | | | | |
| | | | | |D| | |
| | | |D| | | | |
| | | | | | |D| |
| | | |D| | | | |
| |D| | | | | | |
| | | | |D| | | |
| | | | | | | |D|
|D| | | | | | | |
| | |D| | | | | |
| | | | | |D| | |
| | | | | | |D| |
| | | |D| | | | |
| |D| | | | | | |
| | | | | | | |D|
| | | | | |D| | |
|D| | | | | | | |
| | |D| | | | | |
| | | | |D| | | |
| | | | | | |D| |
| | | | |D| | | |
| | |D| | | | | |
|D| | | | | | | |
| | | | | |D| | |
| | | | | | | |D|
| |D| | | | | | |
| | | |D| | | | |
| | | | | | | |D|
| |D| | | | | | |
| | | |D| | | | |
|D| | | | | | | |
| | | | | | |D| |
| | | | |D| | | |
| | |D| | | | | |
| | | | | |D| | |
| | | | | | | |D|
| |D| | | | | | |
| | | | |D| | | |
| | |D| | | | | |
|D| | | | | | | |
| | | | | | |D| |
| | | |D| | | | |
| | | | | |D| | |
| | | | | | | |D|
| | |D| | | | | |
|D| | | | | | | |
| | | | | |D| | |
| |D| | | | | | |
| | | | |D| | | |
| | | | | | |D| |
| | | |D| | | | |
| | | | | | | |D|
| | | |D| | | | |
|D| | | | | | | |
| | |D| | | | | |
| | | | | |D| | |
| |D| | | | | | |
| | | | | | |D| |
| | | | |D| | | |
Kongruenzfrei
Anmerkungen zur kongruenzfreien Lösungsmenge des Damenproblems
Ein Ansatz zur kongruenzfreien Lösungsmenge
Der aufmerksame Leser dürfte schon herausgefunden haben,
dass viele Lösungen mittels Spiegelungen und Drehungen
(kongruente Operationen)
in andere Lösungen überführt werden können.
Um die Lösungsmenge kongruenzfrei zu halten, bedarf es nur ein paar kleiner Veränderungen oben angegebener Klassen:
Um die Lösungsmenge kongruenzfrei zu halten, bedarf es nur ein paar kleiner Veränderungen oben angegebener Klassen:
- Das Brett
BoardOfQueensmuss um eine Vergleichsoperation (z. B. isSameBoard(otherBoard)) erweitert werden, so dass es mit anderen Brettern auf kongruente Ähnlichkeit verglichen werden kann. - Der Lösungsalgorithmus im Hauptprogramm
QueenProblemmuss eigentlich nur, bevor eine weitere neue Lösung der Lösungsliste hinzugefügt wird, die bereits in der Lösungsliste abgelegten Lösungen mit der neuen Lösung auf kongruente Ähnlichkeit vergleichen.
Nur wenn noch keine Lösung, die zur neuen Lösung kongruent ist, existiert, kann die neue Lösung in die Lösungsliste aufgenommen werden.
Zählen
Ermittlung der Anzahl aller möglichen Lösungen zum Damenproblem
Das Zählen der Lösungen
Zur Ermittlung der Anzahl aller möglichen Lösungen des Damenproblems muss eigentlich nur die oben angegebene Klasse
Als Ergebnis erwartet man für große Bretter sehr viele Lösungen, d. h. die Anzahl aller möglichen Lösungen könnte möglicherweise den Wertebereich eines normalen Integers überschreiten, deshalb wird hier die Klasse
QueenProblem
abgeändert bzw. vereinfacht werden.
Als Ergebnis erwartet man für große Bretter sehr viele Lösungen, d. h. die Anzahl aller möglichen Lösungen könnte möglicherweise den Wertebereich eines normalen Integers überschreiten, deshalb wird hier die Klasse
BigInteger
(Klasse für beliebig große Zahlen)
zum Zählen verwendet.
QueenProblemCounter.java
import java.math.BigInteger;
/**
* Der Algorithmus dieser Klasse zählt die Lösungen zum N-Damenproblem.
*
* Nur die private Methode "count" bezeichnet den eigentlichen, rekursiven
* Algorithmus zum Damenproblem.
*/
public class QueenProblemCounter {
/**
* Zählt die Lösungen zum N-Damenproblem.
* @param N Die Mächtigkeit des zugrundeliegenden Brettes (NxN-Brett).
* @return Anzahl aller gefundenen Lösungen.
*/
public static BigInteger count(int N) {
// Das Ausgangsbrett instanziieren, ein leeres NxN-Brett.
BoardOfQueens emptyboard = new BoardOfQueens(N);
// Das eigentliche Lösungsverfahren!
return count(emptyboard, 0);
}
/**
* Zählt die Lösungen des Damenproblem rekursiv mittels Tiefensuche.
* Die Suchtiefe wird durch die Anzahl der Spalten des zugrundeliegenden
* Brettes bestimmt. Wenn alle Spalten mit Erfolg abgearbeitet werden konnten,
* liegt eine Lösung vor.
* @param current Das aktuelle Brett.
* @param x Der aktuelle Spaltenindex des Brettes.
* @return Die Anzahl der bereits besuchten Lösungen.
*/
private static BigInteger count(BoardOfQueens current, int x) {
BigInteger result = BigInteger.ZERO;
// Gibt es eine weitere Spalte, die noch besucht werden kann?
if (x < current.getN()) {
/* Lösungen suchen! */
for (int y = 0; y < current.getN(); y++) {
if (current.canSetQueenAt(x, y)) {
// Setze Dame auf Feld(x, y)
current.setQueenAt(x, y);
// Rekursionsschritt mit der nächsten Spalte(x + 1)
result = result.add(count(current, x + 1));
// Nimm die Dame wieder vom Feld(x, y),
// d.h. alten Zustand des Brettes wieder herstellen
current.unsetQueenAt(x, y);
}
// else: Dame kann nicht gesetzt werden (Sackgasse),
// deshalb weitere Suche in die Tiefe nicht nötig.
}
} else {
/* Lösung gefunden! */
// result wird um 1 erhöht.
result = result.add(BigInteger.ONE);
}
return result;
}
/**
* Das Hauptprogramm, welches die Lösungen des Damenproblems für viele
* verschiedengroße Bretter zählen kann.
* Jedes einzelne Argument wird als natürliche Zahl N interpretiert
* (N-Damenproblem).
* @param arguments Die Argumente der Konsole, erwünscht ist nur die
* Auflistung natürlicher Zahlen (größer als 0).
*/
public static void main(String[] arguments) {
for (int i = 0; i < arguments.length; i++) {
try {
int N = Integer.parseInt(arguments[i]);
if (N > 0) {
// Berechne die Anzahl aller Lösungen zum NxN-Brett.
BigInteger results = count(N);
// Gib lediglich die Anzahl der gefundenen Lösungen aus.
System.out.print("(" + N + " x " + N + ")");
System.out.println(" -> " + results.toString() + " Result(s)\n");
} else {
System.err.println("Argument must be greater than '0'.");
}
} catch (NumberFormatException nfe) {
System.err.println(nfe.getMessage());
}
}
}
}
Im Folgenden werden die Lösungen zu den ersten 18 Brettgrößen des N-Damenproblems gezählt:
java QueenProblemCounter 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
(1 x 1) -> 1 Result(s)
(2 x 2) -> 0 Result(s)
(3 x 3) -> 0 Result(s)
(4 x 4) -> 2 Result(s)
(5 x 5) -> 10 Result(s)
(6 x 6) -> 4 Result(s)
(7 x 7) -> 40 Result(s)
(8 x 8) -> 92 Result(s)
(9 x 9) -> 352 Result(s)
(10 x 10) -> 724 Result(s)
(11 x 11) -> 2680 Result(s)
(12 x 12) -> 14200 Result(s)
(13 x 13) -> 73712 Result(s)
(14 x 14) -> 365596 Result(s)
(15 x 15) -> 2279184 Result(s)
(16 x 16) -> 14772512 Result(s)
(17 x 17) -> 95815104 Result(s)
(18 x 18) -> 666090624 Result(s)
Optimierung
Bessere Laufzeiten durch mittels Permutationsalgorithmus
Statt Suchen, Permutieren!
Wenn man alle Permutationen folgender Zeilen überprüft, gibt es deutlich weniger Brettkonfigurationen zu prüfen.
|D| | | | | | | |
| |D| | | | | | |
| | |D| | | | | |
| | | |D| | | | |
| | | | |D| | | |
| | | | | |D| | |
| | | | | | |D| |
| | | | | | | |D|
Es muss nur noch
Dieser Permutationsansatz kann auch auf NxN-Bretter übertragen werden.
Selbstverständlich überlasse ich es Ihrem Ehrgeiz, diesen Ansatz zu realisieren.
8!
mal
(8 * 7 * 6 * 5 * 4 * 3 * 2 * 1)
überprüft werden, ob eine Lösung vorliegt, anstatt dies
88
mal
(8 * 8 * 8 * 8 * 8 * 8 * 8 * 8)
zu tun.
Dieser Permutationsansatz kann auch auf NxN-Bretter übertragen werden.
Selbstverständlich überlasse ich es Ihrem Ehrgeiz, diesen Ansatz zu realisieren.
Quellenangabe
-
[INFODUDEN]
Duden Informatik: 1993 Auflage2, Bibliographisches Institut & F. A. Brockhaus AG ISBN 3-411-05232-5 Ein Sachlexikon für Studium und Praxis