# Hauptteil

Dieses Wikibook beschäftigt sich mit der softwaretechnischen Erstellung von Campingplatzrätseln mit der Hilfe eines strukturierten Java-Programms. Hierbei werden iterative Algorithmen eingesetzt, mit denen die Zeilen und Spalten des rechteckigen Campingplatzes abgearbeitet werden.

## Campingplatzrätsel

Das Ziel des Spieles besteht darin, anhand von Zeilen- und Spaltensummern von Zelten sowie der Lage von dargestellten Bäumen die Lage aller verborgenen Zelte herauszufinden.
Dieses Logikspiel wurde wurde Ende der 1980er Jahre vom Niederländer Leon Balmaekers erfunden. Der niederländische Spieleentwickler Peter Ritmeester veröffentlichte es zunächst unter der Bezeichnung "Alle ballen verzamelen" (zu Deutsch: "Alle Bälle einsammeln")in der seit 1993 herausgegebenen Zeitschrift Eureka (altgriechisch εὕρηκα = „Ich habe es gefunden“), dem Vorgänger der Zeitschrift Breinbrekers (wörtlich übersetzt: "Hirnbrecher").
Beim Campingplatzraetsel müssen Zelte auf einem rechteckigen Campingplatz mit quadratischen Feldern so verteilt werden, dass rechts, links, oben oder unten neben jedem auf dem Campingplatz vorhandenen Baum genau ein diesem Baum zugeordnetes Zelt gesetzt wird.
In den acht direkten Nachbarfeldern eines Zeltes darf kein weiteres Zelt aufgebaut sein.
Am Spielfeldrand wird angezeigt, wie viele Zelte sich in den betreffenden Spalten und Zeilen befinden. Die Gesamtzahl aller Zelte beziehungsweise auch aller Bäume steht in der unteren rechten Ecke.
* Beispiel eines Campingplatzrätsels
* Campingplatzrätsel mit den Zeilen- und Spaltensummen aller 23 Zelte sowie mit den Lagen der 23 den Zelten zugeordneten Bäume.
* Dasselbe Campingplatzrätsel mit der Lage der 23 Zelte.

## Programmbestandteile

Das hier vorgestellte Java-Programm berechnet ein rechteckiges Campingplatzfeld. Hierzu wird die Java-Klasse CampingplatzGraphs verwendet, die im Folgenden beschrieben wird.

### CampingplatzGraphs

In der Java-Klasse CampingplatzGraphs werden Instanzen der zu lösenden Campingplatzrätsel implementiert. Die Klasse CampingplatzGraphs dient ferner zur graphischen Darstellung der Campingplatzrätsel. Hierzu wird die Methode campingplatzZeichnen aufgerufen.
Das Campingplatzrätsel hat die Breite sizeX und die Höhe sizeY. Jedes Campingplatzrätsel hat für eine Pseudozufallszahlenfolge genau einen Startwert seed, mit dessen Hilfe ein definiertes Campingplatzrätsel generiert werden kann.
Alle Campingplatzfelder sind quadratisch und haben die gleichen Breiten und Höhen fieldSize.
Bei der hier vorgestellten Implementierung befindet sich das Campingplatzfeld mit dem kleinsten Rechtswert und dem kleinsten Hochwert (0 | 0) oben links, die positiven Rechtswerte laufen nach rechts und die positiven Hochwerte laufen nach unten. Die Eigenschaften des Campingplatzrätsels bleiben bei einer Achsenspiegelung um die horizontale oder vertikale Achse oder bei einer Punktspiegelung erhalten.

#### Konstruktor

Der Konstruktor ist in Java eine spezielle öffentliche Methode, die namensgleich mit der Klasse zur Initialisierung von Instanzen verwendet wird.
Ein Campingplatzrätsel muss mit seiner Breite width und seiner Höhe height in Campingplatzfeldern sowie einer ersten Pseudozufallszahl seed' initialisiert werden. Der weitere Parameter showTents gibt an, ob die Lösung des Rätsels angezeigt werden soll (Wert CampingplatzGraphs.PUZZLE) oder nicht (Wert CampingplatzGraphs.SOLUTION):

#### Bestimmung der zufälligen Lage von Zelten

In den acht direkt an ein Zelt angrenzenden Campingplatzfeldern darf kein weiteres Zelt liegen, was mit der typengebundenen Methode tentIsPossible (int ix, int iy) überprüft werden kann.
Die kleinste mögliche Anzahl von Zelten ist insbesondere dann möglich, wenn sich an den Kanten des Campingplatzes wenige Zelte befinden. Jedes Zelt innerhalb der äußeren Parzellen hat einen zugeordneten Baum und sieben weitere direkte Nachbarfelder, die blockiert werden.
Die größte mögliche Anzahl von Zelten ist insbesondere dann möglich, wenn sich in jeder Ecke des Campingplatzes ein Zelt befindet, da jedes Zelt dort einen zugeordneten Baum hat und nur ein weiteres direktes Nachbarfeld blockiert wird.
Unter der Voraussetzung, dass keine potentiell nutzbare Parzelle frei bleiben soll, ergibt sich die maximale Anzahl der zu setzenden Zelte $N_{max}$ je nach Verteilung der Zelte aus der Anzahl Parzellen des Campingplatzes $N_{Camp}$mit $n_{x}$ Spalten und $n_{y}$ Zeilen:
    $n_{Camp}=n_{x}\cdot n_{y}$
Bei 'ungeradzahligen Kantenlängen ergibt sich für die Anzahl der Spalten $n_{x}\geq 3$ und die Anzahl der Reihen $n_{y}\geq 3$:
    $N_{max}\leq {\frac {n_{x}\cdot n_{y}+n_{x}+n_{y}+1}{4}}$
Bei geradzahligen Kantenlängen ergibt sich für die Anzahl der Spalten $n_{x}\geq 2$ und die Anzahl der Reihen $n_{y}\geq 2$:
    $N_{max}\leq {\frac {n_{x}\cdot n_{y}}{4}}={\frac {N_{Camp}}{4}}$
In diesem Fall kann also maximal je ein Viertel der Parzellen des Campingplatzes mit Zelten respektive mit Bäumen besetzt sein, und die andere Hälfte der Parzellen ist leer.
Der boolesche Ausdruck ((ix < (this.sizeX - 1)) || (iy < (this.sizeY - 1)) in der ersten Zeile der Blockanweisung der Methode trägt dem Umstand Rechnung, dass einem Zelt in der rechten unteren Ecke des Campingplatzes kein Baum mehr zugeordnet werden kann, falls die beiden Felder direkt darüber und direkt links daneben bereits mit Bäumen anderer Zelte blockiert sind. Dieses Problem ist rechts im Beispiel dargestellt, wo die Bäume direkt links und oberhalb des Zeltes rechts unten in der Ecke bereits durch andere Zelte besetzt sind. Dieses Problem kann nicht auftauchen, wenn in dem rechten unteren Feld kein Zelt positioniert wird.
Mit dem Aufruf der typengebundenen Methoden setTent und setTents werden die Positionen der zu erratenden Zelte bestimmt. Hierbei wird eine pseudozufällige Zahlenfolge genutzt, um die Zeilen und Spalten für potenzielle Zeltfelder zu berechnen. Mit der Methode tentsPossible wird am Kopf der entsprechenden Schleife geprüft, ob es überhaupt noch möglich ist, neue Zelte zu setzen. Wird ein Platz für ein Zelt gefunden, wird die Instanzvariable numberOfTents inkrementiert.

#### Bestimmung der Lage der zugeordneten Bäume

Die typengebundene Methode setTrees dient zur Berechnung der zu den Zelten zugehörigen Bäume, die sich direkt oberhalb, rechts, unterhalb oder links eines jeden Zeltes befinden. Hierzu wird mit einer pseudozufällig bestimmten Himmelsrichtung (OBEN, RECHTS, UNTEN oder LINKS) begonnen, die durch den Methodenaufruf this.ganzePseudozufallszahl (OBEN, LINKS)' ermittelt wird. Nachdem ein Platz für einen Baum gefunden wurde, werden die Instanzvariablen für die Anzahl der Zelte in der betreffenden Zeile tentsInRow [iy] und für die Anzahl der Zelte in der betreffenden Spalte tentsInColumn [ix] inkrementiert, damit sie später angezeigt werden können.
In manchen Fällen mit direkt benachbarten Baumpaaren kann anhand der Angabe der Zelte in den Spalten und Zeilen nicht eindeutig ermittelt werden, in welchen Zellen die Zelte liegen müssen. In diesen Fällen muss dann geraten werden.
* Mehrdeutigkeiten beim Campingplatzrätsel
* Zwei Bäume beziehungsweise zwei Zelte in zwei Spalten und zwei Zeilen. Es kann nicht eindeutig entschieden werden, ob in der oberen und in der unteren Reihe die Zelte links oder in der Mitte liegen.
* Vier Bäume beziehungsweise vier Zelte in drei Spalten und drei Zeilen. Es kann nicht eindeutig entschieden werden, in welchen beiden der vier freien Zellen die Zelte positioniert werden müssen.
* Vier Bäume beziehungsweise vier Zelte in vier Spalten und vier Zeilen. Es kann nicht eindeutig entschieden werden, in welchen vier der acht freien Zellen die Zelte positioniert werden müssen.

#### Graphische Darstellung

Die öffentliche, typengebundene Methode paint muss von der typengebundenen Methode init aufgerufen werden, um ein Labyrinth als Objekt der Java-Klasse java.awt.Graphics in einen Container beziehungsweise in ein Objekt vom Datentyp Component aus dem generischen Java-package awt (Abstract Window Toolkit) zu zeichnen. Sie überschreibt die paint-Methode ihrer Superklasse Window, von der die Java-Klassen javax.swing.JFrame und somit auch CampingplatzGraphs abgeleitet sind:
* java.awt.Component
** java.awt.Container
*** java.awt.Window
**** java.awt.Frame
***** javax.swing.JFrame
****** CampingplatzGraphs

#### Maussteuerung

Die Klasse CampingplatzGraphs implementiert die Klasse java.awt.event.MouseListener. Diese verfügt über fünf typengebundene Methoden, die die Betätigung der Maustasten abfragt. Diese fünf Methoden müssen bei der Implementierung in der Klasse CampingplatzGraphs überschrieben werden.
Die Methode mouseClicked (java.awt.event.MouseEvent event) wird verwendet, um die Position der Maus im Fenster abzufragen, wenn eine Maustaste geklickt wurde. Hierzu werden die typengebundenen Methoden getX und getY der Klasse java.awt.event.MouseEvent des Parameters event aufgerufen. Die betätigen Maustasten können mit der typengebundenen Methode event.getButton ermittelt werden. Die rechte Maustaste wird durch die Konstante java.awt.event.MouseEvent.BUTTON3 repräsentiert.
Mit Hilfe der Methodenaufrufe getColumn (x) und getRow (y) kann aus den Fensterkoordinaten der Mausposition (x, y) das zugehörige Campingplatzfeld (column, row) ermittelt werden. Je nach Status des entsprechenden Campingplatzfelds und der betätigten Maustasten werden entweder mit einem Zelt markierte Felder, an denen ein Zelt vermutet wird (linke Maustaste), oder mit einem schwarzen Quadrat markierte Felder, an denen kein Zelt vermutet wird (rechte Maustaste), angezeigt.
Wenn genauso viele Zelte markiert wie gesucht sind, wird die Lösung des Rätsels eingeblendet.
Am Ende der Methode wird die Methode repaint aufgerufen, um die Änderungen anzuzeigen.

#### Quelltext

Mit dem folgenden Java-Programm mit der Klasse CampingplatzGraphs können graphische Campingplatzrätsel berechnet werden:
→ Java-Programm "CampingplatzGraphs"

### Aufruf des Programms

Mit dem Aufruf der folgenden öffentlichen Hauptmethode main kann ein zufällig erstelltes Campingplatzrätsel mit 7 mal 7 Feldern in der Breite und in der Höhe berechnet und gezeichnet werden: Ferner wird eine entsprechende Instanz mit der Lösung des Rätsels ausgegeben.

## Nachwort

Die hier angegebenen strukturierten Programmbeispiele können ohne große Umstände in jede andere strukturierte Programmiersprache übertragen werden. Durch die Modifikation und Ergänzung der angegebenen Algorithmen können mit Leichtigkeit anders gestaltete Campingplatzrätsel berechnet werden.
Es wäre erfreulich, wenn dieses Wikibook zu einem besseren und tieferen Verständnis der strukturierten Programmierung und als Einstieg in die Technik der iterativen Programmierung beitragen kann.

## Einzelnachweise

* ↑ java.awt.event.MouseListener, docs.oracle
* ↑ java.awt.event.MouseEvent, docs.oracle

## Siehe auch

* Zeltlager (Rätsel)
* Strukturierte Programmierung