Das Springerproblem

1. Aufgabe

Gegenstand dieser Aufgabe ist das klassische Springerproblem des Schachspiels. Die Springerfigur wird dazu auf ein beliebiges Feld eines n×n Schachbretts gestellt. Das Problem besteht nun darin, eine Zugfolge zu finden, bei der der Springer, entsprechend seiner Bewegungsmöglichkeiten im Schach, nacheinander alle Felder des Schachbrettes besetzt – jedes Feld genau einmal! Prinzipiell ist von vorneherein nicht klar, ob es überhaupt eine Lösung gibt. Wenn ja, kann es auch sein, dass mehrere Zugfolgen existieren? Eine mögliche Lösung des Springerproblems auf einem realen Schachbrett (also mit 64 Feldern) finden Sie in Abbildung 1 vor:

Eine Lösung des Springerproblems.

Abbildung 1. Eine Lösung des Springerproblems.


Mit den Rechnern der aktuellen Generation wird es sehr schwer sein, für ein 8×8 Schachbrett alle Lösungen zu bestimmen. Wir konzentrieren uns deshalb in der Aufgabe auf kleinere Bretter. Die Anzahl realistisch ermittelbarer Lösungen für kleinere Schachbretter können Sie Abbildung 2 entnehmen:

Einige Resultate des Springerproblems.

Abbildung 2. Einige Resultate des Springerproblems.


Die Zugregel für einen Springer kann man so beschreiben: Von seinem Ausgangsfeld kann er zuerst zwei Felder in eine beliebige Richtung gehen (keine Diagonale) und dann noch ein Feld zur Seite treten. Befindet er sich in einem der mittleren Felder des Spielfeldes, so gibt es 8 Zielfelder, die er betreten kann (siehe dazu auch Abbildung 3). Steht er hingegen mehr in der Nähe des Schachbrettrands, so verringert sich die Anzahl der Sprungmöglichkeiten entsprechend.

Zugmöglichkeiten des Springers auf einem Schachbrett.

Abbildung 3. Zugmöglichkeiten des Springers auf einem Schachbrett.

1.1 Lösungsstrategie „Trial and Error

Wir erläutern eine Lösungsstrategie für das Springerproblem am Beispiel eines 3x4-Schachbretts und erklären in einzelnen Schritten den Ablauf. Exemplarisch legen wir für den Springer die Startposition in der linken unteren Ecke fest, also das Feld mit den Koordinaten (2,0), wobei wir den Ursprung des Bretts in der linken, oberen Ecke zu Grunde legen. Es wäre aber auch jedes andere Feld zur Erörterung der Lösungsstrategie geeignet (Abbildung 4). Die „1“ symbolisiert, dass es sich um den ersten Zug des Springers handelt:

Ausgangssituation 1: Springer wird im linken unteren Feld platziert.

Abbildung 4. Ausgangssituation „1“: Springer wird im linken unteren Feld platziert.


Anhand der Ausgangsposition des Springers bestimmen wir nun eine Liste seiner möglichen Züge, die er von der aktuellen Position aus bestreiten kann. Sitzt der Springer auf dem Feld (2,0), so hat er in diesem Fall die Wahl zwischen zwei Zielfeldern (0,1) und (1,2), um weiter voran zu schreiten. Sie finden diese Felder in Abbildung 5 grau hinterlegt vor. Wir entscheiden uns für das erste Feld aus der Liste, auf dem Schachbrett nehmen wir durch die „2“ eine entsprechende Nummerierung vor:

Spielsituation 2: Springer zieht von Feld (2,0) nach Feld (0,1).

Abbildung 5. Spielsituation „2“: Springer zieht von Feld (2,0) nach Feld (0,1).


Von der aktuellen Springerposition ausgehend bestimmen wir wieder alle möglichen Felder, auf die der Springer nun springen kann. Es ist wieder eine Liste mit zufälligerweise zwei Positionen, dieses Mal sind es die Felder (1,3) und (2,2), siehe Abbildung 6. Wir wählen wieder das erste Element aus der Liste aus und setzen die Figur auf das Feld (1,3):

Spielsituation 3: Springer zieht von Feld (0,1) nach Feld (1,3).

Abbildung 6. Spielsituation „3“: Springer zieht von Feld (0,1) nach Feld (1,3).


Es wurden bei weitem noch nicht alle Felder des Schachbretts besucht. Von der Springerposition (1,3) ausgehend bietet sich dieses Mal aber nur ein einziges Feld (2,1) für den Folgezug an, siehe Abbildung 7:

Spielsituation 4: Springer zieht von Feld (1,3) nach Feld (2,1).

Abbildung 7. Spielsituation „4“: Springer zieht von Feld (1,3) nach Feld (2,1).


Und noch einmal gilt es diese Runde zu drehen. Dieses Mal können wir zwei Felder (0,0) und (0,2) als mögliche nächste Kandidaten ausmachen. Wir entscheiden uns in Abbildung 8 für das Feld (0,0):

Spielsituation 5: Springer zieht von Feld (2,1) nach Feld (0,0).

Abbildung 8. Spielsituation „5“: Springer zieht von Feld (2,1) nach Feld (0,0).


Ich verspreche es, diese Runde drehen wir jetzt zum letzen Mal. Es gibt wieder nur ein einziges Feld zum Weiterspielen, in Abbildung 9 erkennen Sie das weitere Vorgehen:

Spielsituation 6: Springer zieht von Feld (0,0) nach Feld (1,2).

Abbildung 9. Spielsituation „6“: Springer zieht von Feld (0,0) nach Feld (1,2).


Wir sind an einer entscheidenden Stelle in der Betrachtung der Lösungsstrategie angekommen. Wenn Sie Abbildung 9 betrachten, werden Sie erkennen, dass es von der aktuellen Springerposition aus betrachtet keine weitere Möglichkeit gibt, zu springen und damit zu einer Lösung des Springerproblems zu gelangen. Jetzt kommen die Listen mit den möglichen Folgezügen aus den vorherigen Schritten zum Zuge. Offensichtlich war die Auswahl eines Folgezugs in den Schritten zuvor nicht Erfolg versprechend. Wir müssen die Figur also auf die vorherige Ausgangssituation zurücksetzen. Da wir in diesem Schritt (im konkret vorliegenden Beispiel) aber nur einen einzigen Folgezug hatten, müssen wir gleich noch eine weitere Ausgangssituation zurücksetzen und kommen damit in Abbildung 7 an. Dort hatten wir, vom Spielfeld mit der Nummer 4 ausgehend, die zwei möglichen Folgezüge (0,0) und (0,2) zur Auswahl. Die Entscheidung für (0,0) hat nicht zum Ziel geführt, also versuchen wir es jetzt mit der zweiten Alternative (0,2), siehe Abbildung 10. Wir verstehen jetzt, zu welchem Zweck die Listen mit den möglichen Folgezügen aufzubewahren sind. Gelangt man in einem bestimmten Schritt in die missliche Situation, dass es keine Folgezüge mehr gibt, muss man einen oder mehrere Schritte rückgängig machen und mit einem alternativen Folgezug sein Glück von Neuem versuchen.

Springer geht zur Spielsituation 4 zurück und springt jetzt von (2,1) nach Feld (0,2).

Abbildung 10. Springer geht zur Spielsituation „4“ zurück und springt jetzt von (2,1) nach Feld (0,2).


Dieses Verfahren läuft solange weiter, bis alle Felder des Schachbrettes besucht worden sind (und man damit eine Lösung gefunden hat), oder man feststellt, dass es keine Lösung gibt. Möchte man alle Lösungen zu einer bestimmten Schachbrettgröße finden, bricht man das Verfahren nach dem Entdecken einer Lösung nicht ab, sondern hinterlegt die gefundene Lösung in einer geeigneten Datenstruktur und setzt das Verfahren mit den noch vorhandenen Alternativzügen fort. Wenn Sie alles richtig gemacht haben, werden Sie bei dem betrachteten Beispiel eines 3x4-Schachbretts zwei Lösungen aufspüren, die Sie in Abbildung 11 betrachten können:

Zwei Lösungen des Springerproblems auf einem 3x4-Schachbrett.

Abbildung 11. Zwei Lösungen des Springerproblems auf einem 3x4-Schachbrett.


Die dargelegte Lösungsstrategie ist in der Informatik unter dem Begriff „Trial and Error“ geläufig. Sie findet immer dann Anwendung, wenn zur Lösung eines Problems kein systematisches Verfahren zur Verfügung steht. Bei der „Trial and Error“-Methode werden nacheinander alle in Frage kommenden Lösungskandidaten durchprobiert, bis eine oder mehrere Lösungen gefunden wurden.

Im Falle des Springerproblems bedeutet dies, dass nach dem Setzen des Springers auf ein Ausgangsfeld maximal 8 Möglichkeiten zu betrachten sind, um auf das nächste Feld zu springen. Auf diesem Feld gibt es wiederum maximal 8 Möglichkeiten, um zum nächsten Feld weiterzuziehen usw. Geht es auf einem bestimmten Spielfeld überhaupt nicht mehr weiter, wird der letzte Schritt (beziehungsweise die letzten Schritte) zurückgenommen, und es werden stattdessen alternative Zugmöglichkeiten ausprobiert. Hieraus erklärt sich auch der Begriff „Backtracking“, der häufig bei „Trial and Error“-Problemen anzutreffen ist.

Durch das systematische Vorwärts- und Rückwärtsziehen des Springers auf dem Schachbrett ist sichergestellt, dass alle in Frage kommenden Lösungswege betrachtet werden. Bildlich gesprochen kann man die Bewegungen des Springers als „Aufspannen eines Lösungsbaums“ ansehen (Abbildung 12). In diesem Baum gilt es, Ast für Ast zu traversieren, um die Lösungen zu finden. Führt ein Ast nicht zu einer Lösung, so muss man auf diesem Ast ganz zurückgehen und einen anderen Ast überprüfen.

Lösungsbaum eines Backtracking-Verfahrens.

Abbildung 12. Lösungsbaum eines Backtracking-Verfahrens.


In der programmiersprachlichen Umsetzung müssen wir den Lösungsbaum nicht explizit erzeugen. Backtracking-Verfahren lassen sich typischerweise am einfachsten rekursiv beschreiben, die Möglichkeit eines rekursiven Methodenaufrufs nimmt einem diese Arbeit quasi ab, oder noch verwirrender: Der Lösungsbaum wird auf dem Methodenaufrufstapel implizit, quasi versteckt aufgespannt.

In unserem konkreten Beispiel lässt sich nun zusammenfassend das Lösungsverfahren durch die in Abbildung 13 skizzierte, rekursive Methode FindMoves darstellen:

Grobskizze einer rekursiven Methode FindMoves zur Bestimmung aller Zugfolgen.

Abbildung 13. Grobskizze einer rekursiven Methode FindMoves zur Bestimmung aller Zugfolgen.


Wir schließen die theoretischen Vorarbeiten hiermit ab, es folgen Hinweise für eine Umsetzung des Lösungsverfahrens in einer WPF-Anwendung.

1.2 Klasse Coordinate

Für die Koordinaten des Schachbretts verwenden wir eine Klasse Coordinate (Tabelle 1). Im Prinzip kapselt ein Coordinate-Objekt nur zwei ganzzahlige Werte x und y, um eine Position auf dem Schachbrett zu beschreiben.

Eigenschaft

Beschreibung

Eigenschaft X

public int X { get; };

Liefert die Reihe der Koordinate zurück.

Eigenschaft Y

public int Y { get; };

Liefert die Spalte der Koordinate zurück.

Tabelle 1. Eigenschaften der Klasse Coordinate.

1.3 Klasse KnightProblemSolver

Wir kommen auf das Kernstück der Aufgabe zu sprechen. In der Klasse KnightProblemSolver wird auf Basis der Backtracking-Lösungsstrategie die Menge aller Springerproblemlösungen zu einer bestimmten Schachbrettgröße berechnet. Zunächst stellen wir in Tabelle 2 den Konstruktor und die Eigenschaften der KnightProblemSolver-Klasse vor:

Methode

Beschreibung

Konstruktor

public KnightProblemSolver(int rows, int cols);

Legt für ein KnightProblemSolver-Objekt die Größe des zu Grunde liegenden Schachbretts fest. Die Startposition des Springers befindet sich (der Einfachheit halber) immer links unten auf dem Brett.

Eigenschaft Rows

public int Rows { get; };

Liefert die Anzahl der Reihen des Schachbretts zurück.

Eigenschaft Cols

public int Cols { get; };

Liefert die Anzahl der Spalten des Schachbretts zurück.

Eigenschaft Solutions

private List<List<Coordinate>> Solutions { get; };

Liste zur Verwaltung aller ermittelten Lösungen des Springerzug-Problems. Im Falle des Beispiels aus Abbildung 11 sieht die Liste am Ende des Programms so aus:

{
  {
    {2,0}, {1,2}, {0,0}, {2,1}, {1,3}, {0,1},
    {2,2}, {0,3}, {1,1}, {2,3}, {0,2}, {1,0}
  },
  {
    {2,0}, {1,2}, {0,0}, {2,1}, {1,3}, {0,1},
    {2,2}, {1,0}, {0,2}, {2,3}, {1,1}, {0,3}
  }
}

Tabelle 2. Konstruktor und Eigenschaften der Klasse KnightProblemSolver.


Weiter geht es mit den Instanzvariablen eines KnightProblemSolver-Objekts in Tabelle 3. Im Mittelpunkt steht hier offensichtlich eine zweidimensionale n×m Matrix vom Typ int. Ein Wert 0 im Array-Objekt besagt, dass das korrespondierende Feld noch nicht vom Springer besucht wurde. Ganzzahlige Werte größer Null besagen, dass der Springer schon auf dem Feld war. Der Wert selbst gibt an, beim wievielten Zug das Feld betreten wurde.

Zweidimensionale Matrix zur Verwaltung eines 3×4 Schachbretts inklusive Springerzug.

Abbildung 14. Zweidimensionale Matrix zur Verwaltung eines 3×4 Schachbretts inklusive Springerzug.


Die Momentaufnahme des Beispiels aus Abbildung 14 besagt, dass auf dem Schachbrett bereits ein Springerzug der Länge vier statt gefunden hat. Der Algorithmus ist offenbar noch damit beschäftigt, den vorliegenden Springerzug zu einem Zug mit 12 Sprüngen zu vervollständigen. Eine gefundene Lösung spiegelt sich in dem Array-Objekt also dadurch wieder, dass keine Nullen mehr vorhanden sind und jeder Wert zwischen 1 und dem Produkt der Reihen- und Spaltenanzahl genau einmal auftritt. Zwei Beispiele solcher Array-Objekte hatten wir in Abbildung 11 schon gesehen. Weitere, wichtige Instanzvariablen der KnightProblemSolver-Klasse, sofern sie durch die Eigenschaften aus Tabelle 2 nicht schon abgehandelt wurden, entnehmen Sie bitte Tabelle 3:

Instanzvariable

Beschreibung

board

private int[,] board;

Repräsentiert das Schachbrett, das durch ein KnightProblemSolver-Objekt verwaltet wird.

current

private List<Coordinate> current;

Liste von Coordinate-Objekten zur Ablage eines Springerzugs. Zu Beginn der Suche ist das current-Objekt logischerweise leer. Dem Springerzug aus Abbildung 14 entspricht das Listenobjekt

{ {2,0}, {1,2}, {0,0}, {2,1} }

moveNumber

private int moveNumber;

Zähler für den Sprung im aktuellen Springerzug. Die Variable nimmt Werte zwischen 1 (Ausgangsposition) und Zeilenanzahl × Spaltenanzahl (letzter Zug eines Lösungszugs) an.

Tabelle 3. Zentrale Instanzvariablen der Klasse KnightProblemSolver.


Wie findet man nun eine Folge von Springerzügen auf dem Schachbrett? Die Grobskizze der Methode FindMoves aus Abbildung 13 gilt es nun zu verfeinern. Hierzu betrachten wir in Tabelle 4 zuerst alle Hilfemethoden der Klasse KnightProblemSolver, die zur Realisierung der FindMoves-Methode beitragen:

Methode

Beschreibung

Methode SetKnightMoveAt

private void SetKnightMoveAt (Coordinate coord);

Setzt den Springer auf dem Schachbrett auf die Position coord. Im korrespondierenden Array-Objekt sollte die Nummer des Zugs eingetragen werden.

Methode UnsetKnightMoveAt

private void UnsetKnightMoveAt (Coordinate coord);

Macht einen Springerzug auf dem Schachbrett an der Position coord rückgängig. Im korrespondierenden Array-Objekt sollte der Wert 0 eingetragen werden.

Methode InRange

private bool InRange (int x, int y);

Liefert true oder false in Abhängigkeit davon zurück, ob die beiden Parameter x (Reihe) und y (Spalte) ein gültiges Feld auf dem Schachbrett spezifizieren oder nicht.

Methode CanMoveTo

private bool CanMoveTo (int x, int y);

Liefert true zurück, wenn der Springer von der aktuellen Position auf das Feld mit den Koordinaten x (Reihe) und y (Spalte) springen kann. Die Koordinaten müssen gültig sein und das Feld darf von dem Springer noch nicht durch einen vorangegangenen Zug betreten worden sein.

Methode NextKnightMoves

public List<Coordinate> NextKnightMoves (Coordinate coord);

Erstellt eine Liste mit allen möglichen Folgezügen, ausgehend von der Position coord. Ein Springer, der auf einem Schachbrett auf dem Feld mit den Koordinaten (x,y) steht, kann im nächsten Zug die Felder mit folgenden Koordinaten erreichen (siehe auch Abbildung 3):

(x-1, y+2) und (x-1, y-2),

(x-2 , y+1) und (x-2, y-1),

(x+1, y-2) und (x+1, y+2),

(x+2, y+1) und (x+2, y-1)

Hierbei ist natürlich jeweils zu überprüfen, ob der Zielzug überhaupt auf dem Schachbrett liegt, siehe dazu die Methoden InRange bzw. CanMoveTo. Folglich kann die Resultatliste bis zu acht Coordinate-Elemente enthalten.

Methode HasSolution

private bool HasSolution();

Liefert true zurück, wenn aktuell auf dem Schachbrett eine Lösung des Springerproblems vorliegt, andernfalls false.

Tabelle 4. Hilfsmethoden der Klasse KnightProblemSolver.


Wir sind so gut wie am Ziel angekommen. Die einzige noch fehlende Methode FindMoves ist gemäß Tabelle 5 zu definieren:

Methode

Beschreibung

Methode FindMovesSequential

public void FindMovesSequential (Coordinate coord);

Bestimmt alle Lösungen des Springerproblems, falls vorhanden. Aktuell ist der Springer auf der Position coord gesetzt. Die Lösungen sind über die Eigenschaft Solutions verfügbar.

Methode FindMovesParallel

public void FindMovesParallel (Coordinate coord);

Bestimmt, wie FindMovesSequential, alle Lösungen des Springerproblems, nur mit einem parallelen Lösungsansatz.

Tabelle 5. Methoden FindMovesSequential und FindMovesParallel der Klasse KnightProblemSolver.


Einen Pseudocode der FindMoves-Methode finden Sie in Abbildung 15 vor. Beachten Sie, wie die Hilfsmethoden der Klasse KnightProblemSolver aus Tabelle 4 zum Einsatz gelangen:

Verfeinerung der rekursiven Methode FindMoves zur Bestimmung aller Zugfolgen.

Abbildung 15. Verfeinerung der rekursiven Methode FindMoves zur Bestimmung aller Zugfolgen.

1.4 Visualisierung des Algorithmus

Zur Visualisierung eines Springerzugs bietet sich ein Grid-Steuerelement an, dessen Zellen die Nummern des Zugs darstellen. An Stelle des universellen Grid-Steuerelement können Sie auch das einfachere UniformGrid-Steuerelement verwenden, siehe Abbildung 16:

Darstellung eines Springerzugs mit einem UniformGrid-Steuerelement.

Abbildung 16. Darstellung eines Springerzugs mit einem UniformGrid-Steuerelement.


Etwas anspruchsvoller verläuft die animierte Darstellung eines Springerzugs. Hier werden die einzelnen Sprünge der Reihe nach in dem UniformGrid-Steuerelement aufgeblendet (Abbildung 17):

Animierte Darstellung eines Springerzugs mit einem UniformGrid-Steuerelement.

Abbildung 17. Animierte Darstellung eines Springerzugs mit einem UniformGrid-Steuerelement.

1.5 Parallelisierung des Algorithmus

Wie kann man die Suche nach Lösungen des Springerproblems parallelisieren? Ist der Springer erst einmal auf seinem Startfeld positioniert, können die versuchsweisen Bestimmungen der Zugfolgen von jeweils einem separaten Thread durchgeführt werden. Da jeder Versuch zur Lösung des Springerproblems sich Notizen auf dem Schachbrett macht (Eintragung der Zugnummer), benötigt jede Task ein eigenes Schachbrett. Im Vergleich zu dem zeitlichen Gewinn, der bei der Parallelisierung des Algorithmus entsteht, ist diese Anforderung an die Implementierung jedoch als äußerst marginal einzustufen.

Sie haben soeben das Master-Slave-Modell als eine Organisationsform zur Parallelisierung von Algorithmen kennen gelernt (Abbildung 18). Ein Master-Thread ist bei diesem Modell für die grundlegenden Aufgaben wie Organisation des Schachbretts, seine Visualisierung oder den Empfang und die Verwaltung asynchron eintreffender Lösungen zuständig. Die eigentliche Aufgabe, das Suchen nach Zugfolgen auf dem Schachbrett, wird an einen oder mehrere Slave-Threads delegiert. In Abhängigkeit von den zur Verfügung stehenden Ressourcen des unterlagerten Rechners entscheidet der Master-Thread, wie viele Slave-Threads zu erzeugen sind – oder auch zu einem späteren Zeitpunkt noch zusätzlich nachgestartet werden können. Alle Daten, die vom Master- und seinen Slave-Threads gemeinsam benutzt werden, dürfen natürlich nur nach der Strategie des „gegenseitigen Ausschlusses“ benutzt werden.

Master-Slave-Modell als eine Organisationsform paralleler Algorithmen.

Abbildung 18. Master-Slave-Modell als eine Organisationsform paralleler Algorithmen.


Erstellen Sie eine zweite Klasse KnightProblemParallelSolver, deren FindMoves-Methode parallel arbeitet. Die Startposition des Springers bleibt dabei zunächst in der linken unteren Ecke des Schachbretts. Nun berechnen Sie alle möglichen Züge, die der Springer von dieser Startposition aus tätigen kann. Damit haben Sie gleichzeitig die Anzahl der Slave-Threads gefunden, die Sie mit der parallelen Lösung des Problems beauftragen können. Pro Thread ist nun eine Kopie des Schachbretts anzulegen. Auf allen Kopien wird die Startposition des Springers vermerkt. Die nun folgenden Aufrufe der FindMoves-Methode werden jeweils in den Kontext eines Slave-Threads ausgelagert. Die jeweils zweite Zugposition des Springers ist dem Thread als Parameter zu übergeben. Alle nachfolgend rekursiv stattfindenden Aufrufe der FindMoves-Methode belassen wir – der Einfachheit halber – im jeweils gestarteten Slave-Thread. In einer Verfeinerung Ihrer Implementierung wären an dieser Stelle Optimierungen der Strategie vorstellbar. Jeder Slave-Thread kann auch selbst sein eigener Master werden und so weitere Slave-Threads ins Leben rufen. Es ist also eine Hierarchiebildung im Master-Slave-Modell möglich!

Hinweis: Wenn wir die Startposition des Springers in der linken unteren Ecke belassen, können wir, unabhängig von der Größe des Schachbretts, immer nur zwei Slave-Threads ins Leben rufen, da es nur zwei unmittelbare Folgezüge bei dieser Startposition gibt. Bei hinreichend großem Schachbrett sollten Sie die Startposition des Springers in die Mitte des Schachbretts verlagern (siehe dazu auch Abbildung 3). Dann gibt es acht Folgezüge und Sie können acht Slave-Threads mit der parallelen Lösung des Springerproblems beauftragen!

Vergleichen Sie die Laufzeiten Ihres Programms bei sequentieller und paralleler Suche. Wie groß sind die Unterschiede, die Sie beobachten? Gelingt es Ihnen, die Informationen in Abbildung 2 zu erweitern?

2. Lösung

In der Realisierung legen wir das Entwurfsmuster MVC (Model-View-Controller) zu Grunde. Dieses findet, speziell in der WPF, noch seine Verfeinerung im Rahmen des MVVM-Entwurfsmusters (Model-View-ViewModel). Um den Aufwand für die Implementierung dieser Fallstudie jedoch in Grenzen zu halten, begnügen wir uns mit dem etwas einfacheren Ansatz des MVC-Paradigmas.

Für das Modell der Anwendung legen wir zunächst in Listing 1 eine abstrahierende Beschreibung in Form einer Schnittstelle zu Grunde:

01: public interface IKnightProblem
02: {
03:     // properties
04:     int Rows { get; set; }
05:     int Cols { get; set; }
06: 
07:     List<List<Coordinate>> Solutions { get; }
08: 
09:     // events
10:     event CalculationCompletedHandler CalculationCompleted;
11: 
12:     // methods
13:     void FindMovesSequential();
14:     void FindMovesParallel();
15: }

Beispiel 1. Schnittstelle IKnightProblem.


Aus der IKnightProblem-Schnittstelle können wir ablesen, dass zur Beschreibung der öffentlichen Daten eines Springer-Problems die Dimension des Schachbretts und die Lösungen gefragt sind. Das Schachbrett selbst wie auch der Springer werden bei der Umsetzung des Algorithmus sicherlich eine Rolle spielen, beide Objekte sollten aber nicht öffentlich zugänglich sein. Zur Berechnung der Lösungen werden zwei Methoden FindMovesSequential und FindMovesParallel vorgegeben. Dies ist dem Umstand geschuldet, dass wir ein spezielles Augenmerk auf sequentielle und parallele Lösungsansätze werfen wollen. Da die Berechnung der Lösungen einige Zeit in Anspruch nehmen kann, benötigen wir ein Ereignis CalculationCompleted, um das Ende einer aktiven Berechnung in Erfahrung zu bringen. Die gefundenen Lösungen selbst stehen dann in der Eigenschaft Solutions des Typs List<List<Coordinate>> zur Verfügung.

In Listing 1 stoßen wir in Zeile 7 auf den benutzerdefinierten Datentyp Coordinate. Mit Variablen seines Typs wird auf dem Schachbrett eine Springerposition beschrieben (Listing 2):

01: public struct Coordinate
02: {
03:     private int x;  // row number
04:     private int y;  // column number
05: 
06:     public Coordinate(int x, int y)
07:     {
08:         this.x = x;
09:         this.y = y;
10:     }
11: 
12:     // properties
13:     public int X
14:     {
15:         get { return this.x; }
16:     }
17: 
18:     public int Y
19:     {
20:         get { return this.y; }
21:     }
22: 
23:     // overrides
24:     public override String ToString()
25:     {
26:         return String.Format("({0},{1})", this.x, this.y);
27:     }
28: }

Beispiel 2. Struktur Coordinate.


Damit kommen wir auf den Solver des Springerproblems zu sprechen, oder um im Sprachgebrauch des MVC-Entwurfsmusters zu bleiben: Der Implementierung des Modells in der Klasse KnightProblemSolverImpl. Etliche Methoden dieser Klasse wie etwa SetKnightMoveAt, UnsetKnightMoveAt, InRange, CanMoveTo und NextKnightMoves wurden bereits in Tabelle 4 sehr ausführlich spezifiziert. Die beiden öffentlichen Methoden FindMovesSequential und FindMovesParallel (Zeilen 109 ff. bzw. 132 ff. in Listing 3) besitzen beide eine private Überladung, in der die eigentliche Hauptarbeit erledigt wird (Zeilen 155 ff. und 186 ff.). Alle betrachteten Methoden arbeiten blockierend! Im Umfeld einer Oberflächenanwendung müssen ihre Aufrufe deshalb in einen Sekundärthread ausgelagert werden. Am Ende der Berechnungen wird das CalculationCompleted-Ereignis ausgelöst. Damit erfahren Benutzer des Modells, zu welchem Zeitpunkt langwierige Berechungen des Modells zu Ende gegangen sind.

Für die parallele Variante des Springer-Problems finden Sie in Zeile 6 von Listing 3 die Konstante MaxRecursionDepth vor. Sie legt fest, wieviele rekursive Aufrufe von FindMovesParallel ihre Tätigkeit an unterlagerte Threads aufteilen. Für die parallelen Aktivitäten eignet sich sehr schön die Parallel.For-Methode. Zum einen startet sie eine auf den aktuellen Rechner abgestimmte Menge von Threads des zur Verfügung stehenden Thread-Pools. Zum anderen sind alle von ihr initiierten parallelen Aktionen nach der Rückkehr von Parallel.For beendet.

001: namespace KnightProblemSolver
002: {
003:     public class KnightProblemSolverImpl : IKnightProblem
004:     {
005:         // recursion depth for parallel trial-and-error
006:         private const int MaxRecursionDepth = 2;
007: 
008:         // chess board
009:         private int[,] board;
010: 
011:         // numbers of rows and columns of chess board
012:         private int rows;
013:         private int cols;
014: 
015:         // solution being in construction
016:         private List<Coordinate> current;
017: 
018:         // list of found solutions
019:         private List<List<Coordinate>> solutions;
020: 
021:         // number of last knight's move
022:         private int moveNumber;
023: 
024:         // notify end of calculation
025:         public event CalculationCompletedHandler CalculationCompleted;
026: 
027:         // just for testing
028:         private Stopwatch sw;
029: 
030:         // c'tors
031:         public KnightProblemSolverImpl() : this (8, 8) {}
032: 
033:         public KnightProblemSolverImpl (int rows, int cols)
034:         {
035:             this.rows = rows;
036:             this.cols = cols;
037: 
038:             this.current = new List<Coordinate>();
039: 
040:             this.solutions = new List<List<Coordinate>>();
041: 
042:             this.moveNumber = 0;
043: 
044:             this.sw = new Stopwatch();
045:         }
046: 
047:         private KnightProblemSolverImpl (KnightProblemSolverImpl parent)
048:         {
049:             this.rows = parent.rows;
050:             this.cols = parent.cols;
051: 
052:             // need copy of original chess board (!)
053:             this.board = (int[,]) parent.board.Clone();
054: 
055:             // need copy of solution being in construction
056:             this.current = new List<Coordinate> (parent.current);
057: 
058:             // use *same* list of solutions
059:             this.solutions = parent.solutions;
060: 
061:             this.moveNumber = parent.moveNumber;
062:         }
063: 
064:         // properties
065:         public int Rows
066:         {
067:             get
068:             {
069:                 return this.rows;
070:             }
071: 
072:             set
073:             {
074:                 this.rows = value;
075:             }
076:         }
077: 
078:         public int Cols
079:         {
080:             get
081:             {
082:                 return this.cols;
083:             }
084: 
085:             set
086:             {
087:                 this.cols = value;
088:             }
089:         }
090: 
091:         public List<List<Coordinate>> Solutions
092:         {
093:             get
094:             {
095:                 // return a copy
096:                 return new List<List<Coordinate>> (this.solutions);
097:             }
098:         }
099: 
100:         public long CalculationDuration
101:         {
102:             get
103:             {
104:                 return this.sw.ElapsedMilliseconds;
105:             }
106:         }
107: 
108:         // public interface
109:         public void FindMovesSequential()
110:         {
111:             // reset data structures
112:             this.board = new int[rows, cols];
113:             this.current.Clear();
114:             this.moveNumber = 0;
115: 
116:             this.sw.Reset();
117:             this.sw.Start();
118: 
119:             this.solutions.Clear();
120: 
121:             // start at lower left corner            
122:             Coordinate start = new Coordinate(this.Rows - 1, 0);
123:             this.FindMovesSequential(start);
124: 
125:             this.sw.Stop();
126:             if (this.CalculationCompleted != null)
127:                 this.CalculationCompleted (
128:                     this.solutions.Count,
129:                     this.sw.ElapsedMilliseconds);
130:         }
131: 
132:         public void FindMovesParallel()
133:         {
134:             // reset data structures
135:             this.board = new int[rows, cols];
136:             this.current.Clear();
137:             this.moveNumber = 0;
138: 
139:             this.solutions.Clear();
140: 
141:             this.sw.Reset();
142:             this.sw.Start();
143: 
144:             // start at lower left corner            
145:             Coordinate start = new Coordinate(this.Rows - 1, 0);
146:             this.FindMovesParallel(start, MaxRecursionDepth);
147: 
148:             this.sw.Stop();
149:             if (this.CalculationCompleted != null)
150:                 this.CalculationCompleted(
151:                     this.solutions.Count, this.sw.ElapsedMilliseconds);
152:         }
153: 
154:         // private helper - algorithm to solve the Knight's Tour problem
155:         private void FindMovesSequential(Coordinate coord)
156:         {
157:             this.SetKnightMoveAt(coord);
158:             this.current.Add(coord);
159: 
160:             if (this.HasSolution())
161:             {
162:                 // need a copy of the current solution
163:                 List<Coordinate> copy = new List<Coordinate>(this.current);
164: 
165:                 // add found solution to the list of all solutions
166:                 Monitor.Enter(this.solutions);
167:                 this.solutions.Add(copy);
168:                 Monitor.Exit(this.solutions);
169:             }
170:             else
171:             {
172:                 // determine list of possible next moves
173:                 List<Coordinate> nextMoves = this.NextKnightMoves(coord);
174: 
175:                 // do next moves sequential
176:                 for (int i = 0; i < nextMoves.Count; i++)
177:                     this.FindMovesSequential(nextMoves[i]);
178:             }
179: 
180:             this.UnsetKnightMoveAt(coord);
181:             this.current.RemoveAt(current.Count - 1);
182:         }
183: 
184:         // private helper - algorithm to solve the Knight's Tour problem
185:         // using an parallel approach
186:         private void FindMovesParallel(Coordinate coord, int maxDepth)
187:         {
188:             this.SetKnightMoveAt(coord);
189:             this.current.Add(coord);
190: 
191:             if (this.HasSolution())
192:             {
193:                 // need a copy of the current solution
194:                 List<Coordinate> copy = new List<Coordinate>(this.current);
195: 
196:                 // add found solution *thread safe* to the list of all solutions
197:                 Monitor.Enter(this.solutions);
198:                 this.solutions.Add(copy);
199:                 Monitor.Exit(this.solutions);
200:             }
201:             else
202:             {
203:                 // determine list of possible next moves
204:                 List<Coordinate> nextMoves = this.NextKnightMoves(coord);
205: 
206:                 Parallel.For(0, nextMoves.Count, i =>
207:                 {
208:                     KnightProblemSolverImpl slaveSolver = new KnightProblemSolverImpl(this);
209:                     if (maxDepth > 1)
210:                     {
211:                         // do next moves parallel or ...
212:                         slaveSolver.FindMovesParallel(nextMoves[i], maxDepth - 1);
213:                     }
214:                     else
215:                     {
216:                         // ... do next moves sequential
217:                         slaveSolver.FindMovesSequential(nextMoves[i]);
218:                     }
219:                 });
220:             }
221: 
222:             this.UnsetKnightMoveAt(coord);
223:             this.current.RemoveAt(current.Count - 1);
224:         }
225: 
226:         // occupy square on the chess board
227:         private void SetKnightMoveAt(Coordinate coord)
228:         {
229:             this.moveNumber++;
230:             this.board[coord.X, coord.Y] = this.moveNumber;
231:         }
232: 
233:         // release square on the chess board
234:         private void UnsetKnightMoveAt(Coordinate coord)
235:         {
236:             this.moveNumber--;
237:             this.board[coord.X, coord.Y] = 0;
238:         }
239: 
240:         // checks, whether coordinate does exist on the chess board
241:         private bool InRange(int x, int y)
242:         {
243:             return (x >= 0) && (x < this.Rows) && (y >= 0) && (y < this.Cols);
244:         }
245: 
246:         // checks, whether coordinate is valid and is still not taken
247:         private bool CanMoveTo(int x, int y)
248:         {
249:             return this.InRange(x, y) && (this.board[x, y] <= 0);
250:         }
251: 
252:         // verify, whether current list of moves is a solution
253:         private bool HasSolution()
254:         {
255:             return this.moveNumber >= this.Rows * this.Cols;
256:         }
257: 
258:         // determine list of next possible moves
259:         private List<Coordinate> NextKnightMoves(Coordinate coord)
260:         {
261:             List<Coordinate> result = new List<Coordinate>();
262: 
263:             if (this.CanMoveTo(coord.X + 2, coord.Y + 1))
264:             {
265:                 result.Add(new Coordinate(coord.X + 2, coord.Y + 1));
266:             }
267:             if (this.CanMoveTo(coord.X + 1, coord.Y + 2))
268:             {
269:                 result.Add(new Coordinate(coord.X + 1, coord.Y + 2));
270:             }
271:             if (this.CanMoveTo(coord.X - 2, coord.Y + 1))
272:             {
273:                 result.Add(new Coordinate(coord.X - 2, coord.Y + 1));
274:             }
275:             if (this.CanMoveTo(coord.X - 1, coord.Y + 2))
276:             {
277:                 result.Add(new Coordinate(coord.X - 1, coord.Y + 2));
278:             }
279:             if (this.CanMoveTo(coord.X + 2, coord.Y - 1))
280:             {
281:                 result.Add(new Coordinate(coord.X + 2, coord.Y - 1));
282:             }
283:             if (this.CanMoveTo(coord.X + 1, coord.Y - 2))
284:             {
285:                 result.Add(new Coordinate(coord.X + 1, coord.Y - 2));
286:             }
287:             if (this.CanMoveTo(coord.X - 2, coord.Y - 1))
288:             {
289:                 result.Add(new Coordinate(coord.X - 2, coord.Y - 1));
290:             }
291:             if (this.CanMoveTo(coord.X - 1, coord.Y - 2))
292:             {
293:                 result.Add(new Coordinate(coord.X - 1, coord.Y - 2));
294:             }
295: 
296:             return result;
297:         }
298:     }
299: }

Beispiel 3. Klasse KnightProblemSolverImpl.


In der FindMovesParallel-Methode ab Zeile 186 ist zu beachten, wie über den Parameter maxDepth der rekursive Abstieg gesteuert wird. Ist maxDepth größer als 1, dann wird, wiederum mit einem Aufruf von FindMovesParallel, eine Aufteilung der unterschiedlichen Berechnungen auf Threads vorgenommen. Andernfalls geht es in Zeile 217 mit FindMovesSequential sequentiell weiter.

Es spielt keine Rolle, auf wie vielen Ebenen wir uns mit FindMovesParallel-Aufrufen in unterschiedlichen Threads bewegen: All diese Aufrufe greifen in Zeile 167 (oder sehr selten: 198) auf ein gemeinsames List<Coordinate>-Objekt zur Ablage der Lösungen zu. Deshalb müssen die Schutzmechanismen eines Monitors zum Einsatz kommen, wie wir im unmittelbaren Umfeld der Zeilen 167 und 198 erkennen können. Nicht ganz trivial ist die Suche nach einem singulären .NET-Objekt, dem das für alle rekursiven FindMovesParallel-Aufrufe – die sich in unterschiedlichen KnightProblemSolverImpl-Objekten abspielen – eindeutige Monitor-Objekt zuzuordnen ist. Lassen Sie sich nicht verwirren: Ausgerechnet das List<Coordinate>-Objekt mit dem Bezeichner solutions selbst stellt die Lösung des Problems dar!

Ab dem .NET-Framework 4.0 ginge es sogar noch etwas einfacher: Im Namensraum System.Collections.Concurrent gibt es für den konkurrierenden Zugriff auf Listenstrukturen unter anderem die thread-sichere Klasse ConcurrentStack. Bei Verwendung eines ConcurrentStack-Objekts können alle Monitor.Enter- und Monitor.Exit-Aufrufe in Listing 3 ersatzlos wegfallen.

Die Gestaltung einer Sicht für das Springer-Problem ist mit Hilfe eines UniformGrid-Steuerelements nicht übermäßig kompliziert, wie wir in Listing 4 entnehmen können:

01: <UserControl x:Class="KnightProblemView.KnightProblemViewControl"
02:              xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
03:              xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
04:              xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006" 
05:              xmlns:d="http://schemas.microsoft.com/expression/blend/2008" 
06:              mc:Ignorable="d" 
07:              d:DesignHeight="300" d:DesignWidth="300">
08:     <UniformGrid Name="BoardViewGrid">
09:     </UniformGrid>
10: </UserControl>

Beispiel 4. Klasse KnightProblemViewControl: XAML.


Um die einzelnen Felder des Schachbretts zur Laufzeit ansprechen zu können, werden diese ausschließlich im Codebehind-Anteil der Sicht auf der Basis von Label-Steuerelementen organisiert (Listing 5):

001: namespace KnightProblemView
002: {
003:     internal delegate void UpdateSquareHandler (int index, int number);
004: 
005:     public partial class KnightProblemViewControl : UserControl
006:     {
007:         private int rows;
008:         private int cols;
009: 
010:         // c'tor
011:         public KnightProblemViewControl ()
012:         {
013:             this.InitializeComponent();
014:             this.Loaded += new RoutedEventHandler
015:                 (this.KnightProblemViewControl_Loaded);
016:         }
017: 
018:         // properties
019:         public int Rows
020:         {
021:             get
022:             {
023:                 return this.rows;
024:             }
025: 
026:             set
027:             {
028:                 this.rows = value;
029:                 this.InitUniformGrid();
030:             }
031:         }
032: 
033:         public int Cols
034:         {
035:             get
036:             {
037:                 return this.cols;
038:             }
039: 
040:             set
041:             {
042:                 this.cols = value;
043:                 this.InitUniformGrid();
044:             }
045:         }
046: 
047:         private void KnightProblemViewControl_Loaded (Object sender, RoutedEventArgs e)
048:         {
049:             this.InitUniformGrid();
050:         }
051: 
052:         private void InitUniformGrid ()
053:         {
054:             this.BoardViewGrid.Children.Clear();
055:             this.BoardViewGrid.Columns = this.Cols;
056:             this.BoardViewGrid.Rows = this.Rows;
057: 
058:             for (int i = 0; i < this.rows; i++)
059:             {
060:                 for (int j = 0; j < this.cols; j++)
061:                 {
062:                     Label l = new Label();
063: 
064:                     l.BorderBrush = new SolidColorBrush(Colors.Black);
065:                     l.BorderThickness = new Thickness(5);
066:                     l.Margin = new Thickness(3);
067: 
068:                     l.FontFamily = new FontFamily("Consolas");
069:                     l.FontSize = 32;
070:                     l.FontWeight = FontWeights.Bold;
071: 
072:                     l.VerticalContentAlignment = VerticalAlignment.Center;
073:                     l.HorizontalContentAlignment = HorizontalAlignment.Center;
074:                     l.HorizontalAlignment = HorizontalAlignment.Stretch;
075:                     l.VerticalAlignment = VerticalAlignment.Stretch;
076: 
077:                     this.BoardViewGrid.Children.Add(l);
078:                 }
079:             }
080:         }
081: 
082:         public void Clear ()
083:         {
084:             if (this.Dispatcher.CheckAccess())
085:             {
086:                 for (int i = 0; i < this.BoardViewGrid.Children.Count; i++)
087:                 {
088:                     Label l = (Label) this.BoardViewGrid.Children[i];
089:                     l.Background = new SolidColorBrush(Colors.White);
090:                     l.Content = "";
091:                 }
092:             }
093:             else
094:             {
095:                 this.Dispatcher.BeginInvoke ((Action)(() => { this.Clear(); }) );
096:             }
097:         }
098: 
099:         public void ShowSolution(List<Coordinate> solution, bool pause)
100:         {
101:             this.Clear();
102: 
103:             for (int i = 0; i < solution.Count; i++)
104:             {
105:                 Coordinate coord = solution[i];
106:                 int index = (int) coord.X * this.cols + (int) coord.Y;
107:                 this.UpdateSquare(index, i);
108: 
109:                 if (pause)
110:                     Thread.Sleep(200);
111:             }
112:         }
113: 
114:         private void UpdateSquare(int index, int number)
115:         {
116:             if (this.Dispatcher.CheckAccess())
117:             {
118:                 // running on UI thread
119:                 Label l = (Label)this.BoardViewGrid.Children[index];
120:                 l.Content = (number + 1).ToString();
121:                 l.Background = new SolidColorBrush(Colors.LightGray);
122:             }
123:             else
124:             {
125:                 // running on a different, non-UI thread
126:                 UpdateSquareHandler h = new UpdateSquareHandler(this.UpdateSquare);
127:                 Object[] args = { index, number };
128:                 this.Dispatcher.BeginInvoke(h, args);
129:             }
130:         }
131:     }
132: }

Beispiel 5. Klasse KnightProblemViewControl: Codebehind.


Wesentlich für das MVC-Entwurfsmodell ist die Verschaltung aller beteiligten Komponenten im Hauptprogramm. Dort ist zunächst eine Instanz des Modells anzulegen, auf die alle Steuerelemente des Hauptfensters Zugriff haben: Dies wären zum einen eine Reihe von Schaltflächen, die den Controller-Anteil der Anwendung ausmachen. Controller im Sinne des MVC-Paradigmas sind Steuerelemente, die Daten im Modell ablegen oder Aktionen im Modell anstoßen. Die Views wiederum müssen das Modell kennen, um beim Eintreten von Zustandsänderungen im Modell die Ansicht bei Bedarf zu aktualisieren. Diese Art der Kommunikation erfolgt ereignisgesteuert. Beim Springerproblem könnte eine Zustandsänderung „Alle Lösungen berechnet“ lauten.

01: <Window x:Class="KnightProblem.MainWindow"
02:         xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
03:         xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
04:         xmlns:local="clr-namespace:KnightProblemView;assembly=KnightProblemView"
05:         Title="Knight's Problem: Version 1.03"
06:         Height="350" Width="700">
07:     <DockPanel LastChildFill="True">
08: 
09:         <UniformGrid Rows="2" Columns="4" DockPanel.Dock="Top">
10:             <Button DockPanel.Dock="Top" Name="ButtonDoCalculationSequential"
11:                     Click="Button_Click" Margin="3,3,0,0">Do Calculation: Sequential</Button>
12:             <Button DockPanel.Dock="Top" Name="ButtonShowSolutions"
13:                     Click="Button_Click" Margin="3,3,0,0">Show Solutions</Button>
14:             <Button DockPanel.Dock="Top" Name="ButtonStopAnimation"
15:                     Click="Button_Click" Margin="3,3,0,0">Stop</Button>
16:             <DockPanel LastChildFill="True" Margin="3,3,3,0">
17:                 <ComboBox Name="ComboBoxColums" Width="40"  DockPanel.Dock="Right"
18:                           SelectionChanged="ComboBox_SelectionChanged"></ComboBox>
19:                 <Label  DockPanel.Dock="Right">x</Label>
20:                 <ComboBox Name="ComboBoxRows" Width="40" DockPanel.Dock="Right"
21:                           SelectionChanged="ComboBox_SelectionChanged"></ComboBox>
22:                 <Label>Chessboard:</Label>
23:             </DockPanel>
24: 
25:             <Button DockPanel.Dock="Top" Name="ButtonDoCalculationParallel"
26:                     Click="Button_Click" Margin="3,3,0,3">Do Calculation: Parallel</Button>
27:             <Button DockPanel.Dock="Top" Name="ButtonShowSolutionsAnimated"
28:                     Click="Button_Click" Margin="3,3,0,3">Show Solutions Animated</Button>
29:             <Button DockPanel.Dock="Top" Name="ButtonClear"
30:                     Click="Button_Click" Margin="3,3,0,3">Clear</Button>
31:             <TextBox DockPanel.Dock="Top" Name="CalculationStatus"
32:                      Margin="3,3,3,3"></TextBox>
33:         </UniformGrid>
34:         
35:         <local:KnightProblemViewControl Name="ViewControl">            
36:         </local:KnightProblemViewControl>
37:     </DockPanel>
38: </Window>

Beispiel 6. Klasse MainWindow: XAML.


Weiter geht es in Listing 7 mit den Codebehind-Anweisungen des Hauptfensters. Dort kommen in den Zeilen 27 und 28 zwei Konstanten KnightProblemDimensions.Rows und KnightProblemDimensions.Cols zum Einsatz:

public static class KnightProblemDimensions
{
    public const int Rows = 4;
    public const int Cols = 5;
}

Sie dienen dem Zweck einer Vorbelegung des Hauptfensters nach dem unmittelbaren Start der Anwendung:

001: namespace KnightProblem
002: {
003:     public partial class MainWindow : Window
004:     {
005:         private IKnightProblem solver;  // model of knight's problem
006:         private Task task;              // helper task to prevent UI freezing
007:         private bool isActive;
008: 
009:         // c'tor
010:         public MainWindow()
011:         {
012:             this.InitializeComponent();
013: 
014:             // create model
015:             this.solver = new KnightProblemSolverImpl();
016:             this.solver.CalculationCompleted +=
017:                 new CalculationCompletedHandler
018:                     (this.KnightProblemSolver_CalculationCompleted);
019: 
020:             // setup controls
021:             for (int i = 0; i < 8; i++)
022:             {
023:                 this.ComboBoxRows.Items.Add(i + 1);
024:                 this.ComboBoxColums.Items.Add(i + 1);
025:             }
026: 
027:             this.ComboBoxRows.SelectedItem = KnightProblemDimensions.Rows;
028:             this.ComboBoxColums.SelectedItem = KnightProblemDimensions.Cols;
029:         }
030: 
031:         // event handler
032:         private void Button_Click (Object sender, RoutedEventArgs e)
033:         {
034:             if (sender == this.ButtonStopAnimation)
035:             {
036:                 this.isActive = false;
037:                 return;
038:             }
039: 
040:             if (this.task != null)
041:             {
042:                 this.CalculationStatus.Text = "Calculator is busy !";
043:                 return;
044:             }
045: 
046:             if (sender == this.ButtonClear)
047:             {
048:                 this.CalculationStatus.Text = "";
049:                 this.ViewControl.Clear();
050:             }
051:             else if (sender == this.ButtonDoCalculationSequential ||
052:                 sender == this.ButtonDoCalculationParallel)
053:             {
054:                 this.CalculationStatus.Text = "Calculating ...";
055:                 if (sender == this.ButtonDoCalculationSequential)
056:                 {
057:                     this.task = Task.Factory.StartNew (
058:                         () =>
059:                         {
060:                             this.solver.FindMovesSequential();
061:                             this.task = null;
062:                         }
063:                     );
064:                 }
065:                 else
066:                 {
067:                     this.task = Task.Factory.StartNew (
068:                         () =>
069:                         {
070:                             this.solver.FindMovesParallel();
071:                             this.task = null;
072:                         }
073:                     );
074:                 }
075:             }
076:             else if (sender == this.ButtonShowSolutions)
077:             {
078:                 this.CalculationStatus.Text = "Showing Solutions ...";
079:                 this.isActive = true;
080:                 this.task = Task.Factory.StartNew (
081:                     () => {
082:                         this.ShowSolutions(false);
083:                         this.task = null;
084:                     }
085:                 );
086:             }
087:             else if (sender == this.ButtonShowSolutionsAnimated)
088:             {
089:                 this.CalculationStatus.Text = "Showing Solutions Animated...";
090:                 this.isActive = true;
091:                 this.task = Task.Factory.StartNew (
092:                     () => {
093:                         this.ShowSolutions(true);
094:                         this.task = null;
095:                     }
096:                 );
097:             }
098:         }
099: 
100:         private void ComboBox_SelectionChanged
101:             (Object sender, SelectionChangedEventArgs e)
102:         {
103:             if (this.task != null)
104:             {
105:                 this.CalculationStatus.Text = "Calculator is busy !";
106:                 return;
107:             }
108: 
109:             if (sender == this.ComboBoxColums)
110:             {
111:                 int cols = (int) this.ComboBoxColums.SelectedValue;
112:                 this.solver.Cols = cols;
113:                 this.ViewControl.Cols = cols;
114:             }
115:             else if (sender == this.ComboBoxRows)
116:             {
117:                 int rows = (int) this.ComboBoxRows.SelectedValue;
118:                 this.solver.Rows = rows;
119:                 this.ViewControl.Rows = rows;
120:             }
121:         }
122: 
123:         private void KnightProblemSolver_CalculationCompleted
124:             (int numSolutions, long duration)
125:         {
126:             String status = String.Format("{0} solutions [{1} msecs]",
127:                 numSolutions, duration);
128: 
129:             Console.WriteLine(status);
130: 
131:             this.ShowStatus(status);
132:             this.task = null;
133:         }
134: 
135:         // private helper methods
136:         private void ShowSolutions (bool animated)
137:         {
138:             List<List<Coordinate>> solutions = this.solver.Solutions;
139: 
140:             for (int i = 0; i < solutions.Count; i++)
141:             {
142:                 if (!this.isActive)
143:                     break;
144: 
145:                 String s = String.Format("Solution: {0}", i + 1);
146:                 this.ShowStatus(s);
147: 
148:                 List<Coordinate> solution = solutions[i];
149:                 this.ViewControl.ShowSolution(solution, animated);
150:                 Thread.Sleep(500);
151:             }
152:         }
153: 
154:         private void ShowStatus (String s)
155:         {
156:             this.Dispatcher.BeginInvoke (
157:                 (Action)(() =>
158:                 {
159:                     this.CalculationStatus.Text = s;
160:                 })
161:             );
162:         }
163:     }
164: }

Beispiel 7. Klasse MainWindow: Codebehind.


Beachten Sie in Listing 7 die Zeilen 60 und 70: Die Aufrufe der Methoden FindMovesSequential und FindMovesParallel blockieren! Um ein Einfrieren der Anwendung zu verhindern, müssen diese Aufrufe in Sekundärthreads ausgelagert werden, siehe die Zeilen 57 bis 63 und 67 bis 73. Die Methode KnightProblemSolver_CalculationCompleted des Hauptfensters wird aufgerufen, wenn Berechnungen im Modell zu Ende gegangen sind. Auch hier gilt: Der Rückruf der Ereignishandlermethode gelangt aus dem Modell in einem Workerthread zum Hauptfenster. Folglich ist der direkte Zugriff auf Steuerelemente in dieser Methode nicht möglich und das Dispatcher-Objekt muss zu Rate gezogen werden.

Zum Vergleichen der Laufzeiten der Realisierung ziehen wir ein Schachbrett der Größe 4×7 zu Rate. Auf meinem Intel-Rechner mit einem Intel® Core™2 Duo Prozessor E6320 mit ca. 1.86 GHz, also einer – vornehm formuliert – „klassischen“ 2-Kern CPU, erhalte ich das Ergebnis

FindMovesSequential: 1682 solutions [12006 msecs]
FindMovesParallel:   1682 solutions [7433 msecs]

Man sieht, dass sich die Mühen der Parallelisierung des Algorithmus gelohnt haben.