CGI Programmierug mit Haskell

[ Seminarthemen SS 2001] ... [ Inhaltsverzeichnis ] ... [ Fazit ]

Fallbeispiel Damenproblem

 

Das Problem

Wie schon an anderer Stelle besprochen handelt es sich beim sogenannten Damenproblem um die Frage wie sich n Damen auf einem n*n großen Schachbrett anordnen lassen, ohne daß sie sich gegenseitig bedrohen. Das bedeutet, daß pro Zeile und Spalte genau eine Dame stehen muß und daß nicht zwei Damen auf einer Diagonalen stehen dürfen. Das Hauptaugenmerk liegt in diesem Fallbeispiel nicht auf dem Algorithmus, sondern vielmehr in der Darstellung der Lösung.

Die Aufgabe besteht aus zwei Teilen. Zum einen soll der Benutzer über ein Formular folgende Parameter einstellen können:

Das Formular

Für die Eingabe der oben beschrieben Parameter wird ein Formular verwendet, bei dem alle einzutragenen Felder untereinander aufgeführt sind. Die Entscheidung darüber, ab das Formular oder die Lösung angezeigt wird, wird anhand des Parameters Anzahl gefällt. Ist dieser Wert nicht gesetzt, erscheint das Formular. Anderenfalls wird eine Lösung berechnet.

Wie einfach es ist Fomularelemente zu erzeugen, läßt sich am besten anhand zweier Beispiele belegen. Das Textfeld in dem der Benutzer angeben kann für wie viele Damen er eine Lösung berechnet haben möchte wird durch den Aufruf 

 set [("SIZE", "2"), ("VALUE", "4")] (textfield "anzahl")
erzeugt. Hierbei handelt es sich um ein Textfeld namens anzahl und den durch die Funktion set zusätzlich hinzugefügten Attributen und .

Die Listbox für die Auswahl des Zeichens für die Dame läßt sich sehr einfach durch 

 menu "zeichen" ["O", "X", "+", "0"]
bewerkstelligen. Der daraus resultierende HTML Quellcode sieht folgendermaßen aus. 
 <SELECT NAME="zeichen" >
   <OPTION> O </OPTION>
   <OPTION> X </OPTION>
   <OPTION> + </OPTION>
   <OPTION> 0 </OPTION>
 </SELECT>

Formatierung der Lösung

Nachdem durch Auswertung der Parameter eine Lösung der Form [2,4,1,3] ermittelt wurde, ist es nun an der Zeit, diese in einer Tabelle abzubilden. Die Lösung soll wie folgt interpretiert werden. In Zeile 1 steht die Dame in Spalte 2, in den Zeilen 2, 3 und 4 entsprechend in den Spalten 4, 1 und 3.

Die Generierung der Lösungstabelle vollzieht sich in mehreren Schritten. Mit Hilfe von Rekursion bildet die Funktion werte eine Liste von Listen von Listen von Elementen des Typs HTML. Dies ist nötig, da eine Tabelle aus Listen von Zeilen besteht, die ihrerseits eine Liste von Zellen sind, die wiederum eine Liste von HTML Elementen sind. Als Parameter bekommt werte die Anzahl der Damen (also Zeilen und Spalten), das Zeichen für eine Dame und die Lösung selbst. 

 werte :: Int -> String -> [Int] -> [[[HTML]]]
 werte a z (x:[]) = [zeile x a z]
 werte a z (x:xs) = [zeile x a z] ++ (werte a z xs)
Mit Hilfe von Pattern Matching wird überprüft, ob es noch weitere Lösungszeilen zu formatieren gilt. Ist dies der Fall, wird die aktuelle Zeile formatiert und die Funktion mit dem Rest der Lösungsliste erneut aufgerufen. Das Formatieren einer Zeile erfolgt durch die Funktion zeile, die als Parameter die Spalte in der sich die Dame befindet, die Anzahl aller zu erzeugender Spalten und das Zeichen, mit dem die Dame dargestellt werden soll, erhält. Wiederum durch Rekursion ruft sie für jede zu erstellende Spalte die Funktion zeichen auf und generiert somit eine Liste von Zellen (die wie erwähnt eine Liste von HTML Elementen ist). 
 zeile :: Int -> Int -> String -> [[HTML]]
 zeile m 1 dame = [[zeichen m 1 dame]]
 zeile m n dame = (zeile m (n - 1) dame) ++ [[zeichen m n dame]]
Die Funktion zeichen 
 zeichen m n dame
   | m == n    = prose dame
   | otherwise = prose "."

vergleicht lediglich die beiden hereingegebenen Zahlen und liefert bei Gleichheit das gewünschte Zeichen für die Dame, sonst einen ".".

Den vollständigen Quelltext finden Sie unter [ Download ].

 

[ Seminarthemen SS 2001] ... [ Inhaltsverzeichnis ] ... [ Fazit ]