# Campingplatzrätsel

Dieses Buch steht im Regal Programmierung.
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.
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, ergeben sich die minimal und die maximal erreichbare Anzahl der zu setzenden Zelte $N_{min}$ und $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}$
Um das Minimum abschätzen zu können, muss davon ausgegangen werden, dass sich in den Randfeldern des Campingplatzes gar keine Zelte befinden, damit die Zelte möglichst viele Felder blockieren. Wenn die Kantenlängen ein ganzzahliges Vielfaches von Drei sind, dann kann zur Abschätzung des Minimums der Anzahl von Zelten angenommen werden, dass jedes Zelt genau neun benachbarte Felder blockiert, das Feld des Zeltes selbst zuzüglich der acht angrenzenden Felder.
    $N_{min}={\frac {n_{x}\cdot n_{y}}{9}}={\frac {N_{Camp}}{9}}$ mit $n_{x}=3\cdot n_{x0},n_{y}=3\cdot n_{y0}$ und $n_{x0},n_{y0}\in \mathbb {N}$
Unter Berücksichtigung von beliebigen Kantenlängen ergibt sich mit der Modulo-Funktion:
    $N_{min}=((n_{x}+2){\bmod {3}})\cdot ((n_{y}+2){\bmod {3}})$
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.
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}}={\frac {N_{Camp}}{4}}+{\frac {n_{x}+n_{y}+1}{4}}$
Die folgenden beiden Beispiele zeigen, wie auf einem Campingplatz mit 11 mal 13 Feldern (insgesamt 143 Felder) sowohl nur 22 als auch sogar 38 Zelte versteckt sein können. Nach der obigen Gleichung für das Minimum könnten es sogar nur 20 Zelte sein, und nach der obigen Ungleichung für das Maximum könnten es bei vollkommen regelmäßiger Verteilung der Zelte sogar maximal 41 Zelte sein.
* Zwei Beispiele mit ungewöhnlich wenigen und ungewöhnlich vielen Zelten
* Beispiel eines Campingplatzrätsels mit 13 x 11 Feldern und 22 Zelten.
* Beispiel eines Campingplatzrätsels mit 13 x 11 Feldern und 38 Zelten.
Mit der typengebundenen Methode tentIsPossible (int ix, int iy) kann überprüft werden, ob in einem bestimmten Feld (ix, iy) noch ein Zelt platziert werden kann:
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.

#### Mehrdeutigkeiten

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. Bei Doppeldeutigkeiten liegt die Wahrscheinlichkeit, richtig zu raten, bei 50 Prozent.
Im folgenden sind einige Beispiele mit Doppeldeutigkeiten aufgeführt:
* 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.
* Fünf Bäume beziehungsweise fünf Zelte in fünf Spalten und vier Zeilen. Es kann nicht eindeutig entschieden werden, ob das obere rechte oder obere linke Campingplatzfeld mit einem Zelt besetzt sein muss.
* Vier Bäume und vier Zelte in vier Spalten und fünf Zeilen. Es kann nicht eindeutig entschieden werden, in welchen Spalten beziehungsweise Zeilen die vier Zelte liegen 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.

## Schwieriges Beispiel

Das folgende Beispiel zeigt das Campingplatzrätsel mit 13 Feldern Breite, 11 Feldern Höhe und dem Startwert 91334 für die Pseudozufallszahlenfolge. Die Lage der insgesamt 28 Zelte ist eindeutig, es gehört aber zu den schwierigeren Rätseln seiner Art:

## 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

## Zusammenfassung des Projekts

„Campingplatzrätsel“ ist nach Einschätzung seiner Autoren zu 100 % fertig
* Zielgruppe: Informatiker, Mathematiker
* Lernziele: Erstellung eines iterativ berechneten geometrischen Rätsels mit einem Java-Programm.
* Buchpatenschaft/Ansprechperson: Benutzer:Bautsch
* Sind Co-Autoren gegenwärtig erwünscht? Ja, sehr gerne. Korrekturen von offensichtlichen Fehlern direkt im Text; Inhaltliches bitte per Diskussion.
* Richtlinien für Co-Autoren: Wikimedia-like.