Campingplatzrätsel

Dieses Buch steht im Regal Programmierung.

Dieses Buch hat eine Druckversion.

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.

public final class CampingplatzGraphs extends javax.swing.JFrame implements java.awt.event.MouseListener
{
	// Oeffentliche Klassenkonstanten
	/**
	 * Wert fuer den Parameter "showTents" des Konstruktors ohne Anzeige der Loesung
	 */
	public final static boolean PUZZLE = false;
	/**
	 * Wert fuer den Parameter "showTents" des Konstruktors mit Anzeige der Loesung
	 */
	public final static boolean SOLUTION = true;

	// Klassenkonstanten
	// Fuer den Inhalt der Campingplatzfelder
	private final static long EMPTY = 0;
	private final static long TENT = 1;
	private final static long TREE = 2;
	private final static long CORRECT_GUESS = 3;
	private final static long WRONG_GUESS = 4;
	private final static long CORRECT_BLOCK = 5;
	private final static long WRONG_BLOCK = 6;

	// Fuer die Richtungen zu den Nachbarfeldern
	private final static long TOP = 0;
	private final static long RIGHT = 1;
	private final static long BOTTOM = 2;
	private final static long LEFT = 3;

	// Fuer die Groesse der Darstellung
	private final static int offset = 10; // fuer die umlaufende Breite des Randes
	private final static int offsetTop = 30; // fuer den Titelbanner des graphischen Fensters
	private final static int fieldSize = 64; // fuer die Groesse der Campingplatzfelder

	// Instanzkonstanten
	private final int sizeX; // fuer die Breite in Campingplatzfeldern
	private final int sizeY; // fuer die Hoehe in Campingplatzfeldern
	private final int widthsInPixels; // fuer die Breite in Bildpunkten
	private final int heightInPixels; // fuer die Hoehe in Bildpunkten
	private final long seed; // fuer den Startwert der Pseudozufallszahlenreihe

	// Instanzvariablen
	private long numberOfTents; // fuer die Anzahl der Zelte respektive Baeume
	private boolean showTents; // fuer die Steuerung der Anzeige der Zelte
	private long [][] fields; // fuer die Campingplatzfelder
	private long [] tentsInRow; // fuer die Anzahlen der Zelte in Reihen
	private long [] tentsInColumn; // fuer die Anzahlen der Zelte in Spalten
	private java.awt.image.BufferedImage bufferedImage; // fuer die graphische Anzeige
	private java.util.Random random; // fuer die Pseudozufallszahlenreihe
}

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):

	public CampingplatzGraphs (int width, int height, long seed, boolean showTents)
	{
		this.sizeX = width;
		this.sizeY = height;
		this.random = new java.util.Random (seed);
		this.seed = seed;
		this.setTitle ("Campingplatz " + width + " x " + height + " s " + seed);
		this.numberOfTents = 0;
		this.numberOfGuesses = 0;
		this.fields = new long [height] [width];
		this.tentsInRow = new long [height];
		this.tentsInColumn = new long [width];
		this.initArrays ();
		this.showTents = showTents;
		this.widthsInPixels = fieldSize * (width + 1) + 2 * offset;
		this.heightInPixels = fieldSize * (height + 1) + 2 * offset + 2 * offsetTop;
		this.setDefaultCloseOperation (javax.swing.WindowConstants.EXIT_ON_CLOSE);
		this.bufferedImage = new java.awt.image.BufferedImage (this.widthsInPixels, this.heightInPixels, java.awt.image.BufferedImage.TYPE_INT_RGB);
		this.addMouseListener (this);
	}

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.

	private boolean tentIsPossible (int ix, int iy)
	{
		boolean tentPossible = (this.fields [iy] [ix] == EMPTY) && ((ix < (this.sizeX - 1)) || (iy < (this.sizeY - 1)));

		if (tentPossible)
		{
			if (iy > 0)
			{
				if (ix > 0)
				{
					tentPossible = tentPossible && (this.fields [iy - 1] [ix - 1] == EMPTY);
				}
				tentPossible = tentPossible && (this.fields [iy - 1] [ix] == EMPTY);
				if (ix < (this.sizeX - 1))
				{
					tentPossible = tentPossible && (this.fields [iy - 1] [ix + 1] == EMPTY);
				}
			}

			if (ix > 0)
			{
				tentPossible = tentPossible && (this.fields [iy] [ix - 1] == EMPTY);
			}
			tentPossible = tentPossible && (this.fields [iy] [ix] == EMPTY);
			if (ix < (this.sizeX - 1))
			{
				tentPossible = tentPossible && (this.fields [iy] [ix + 1] == EMPTY);
			}

			if (iy < (this.sizeY - 1))
			{
				if (ix > 0)
				{
					tentPossible = tentPossible && (this.fields [iy + 1] [ix - 1] == EMPTY);
				}
				tentPossible = tentPossible && (this.fields [iy + 1] [ix] == EMPTY);
				if (ix < (this.sizeX - 1))
				{
					tentPossible = tentPossible && (this.fields [iy + 1] [ix + 1] == EMPTY);
				}
			}
		}
		return tentPossible;
	}

Fallgrube bei der Verteilung der Bäume beim Campingplatzrätsel: dem Zelt unten rechts kann kein Baum mehr zugeordnet werden.

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.

	private boolean setTent (int ix, int iy)
	{
		boolean success = this.tentIsPossible (ix, iy);
		if (success)
		{
			this.fields [iy] [ix] = TENT;
		}
		return success;
	}

	private boolean tentsPossible ()
	{
		boolean tentPossible = false;

		int iy = 0; // oben starten
		while (! tentPossible && (iy < this.sizeY))
		{			
			int ix = 0; // links starten
			while (! tentPossible && (ix < this.sizeX))
			{
				tentPossible = this.tentIsPossible (ix, iy);
				ix++;
			}
			iy++;
		}
		return tentPossible;
	}

	private void setTents ()
	{
		boolean successful;
		while (this.tentsPossible ())
		{
			int x = this.pseudoRandomNumber (0, this.sizeX - 1);
			int y = this.pseudoRandomNumber (0, this.sizeY - 1);
			successful = this.setTent (x, y);
			if (successful)
			{
				this.numberOfTents++;
			}
		}
	}

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.

	private void setTrees ()
	{
		int iy = 0; // oben starten
		while (iy < this.sizeY)
		{			
			int ix = 0; // links starten
			while (ix < this.sizeX)
			{
				if (this.fields [iy] [ix] == TENT)
				{
					boolean found = false;
					do
					{
						long randomDirection = this.pseudoRandomNumber (TOP, LEFT);
						if ((randomDirection == TOP) && (iy > 0))
						{
							found = this.fields [iy - 1] [ix] == EMPTY;
							setTree (ix, iy - 1);
						}
						else if ((randomDirection == RIGHT) && (ix < (sizeX - 1)))
						{
							found = this.fields [iy] [ix + 1] == EMPTY;
							setTree (ix + 1, iy);
						}
						else if ((randomDirection == BOTTOM) && (iy < (sizeY - 1)))
						{
							found = this.fields [iy + 1] [ix] == EMPTY;
							setTree (ix, iy + 1);
						}
						else if ((randomDirection == LEFT) && (ix > 1))
						{
							found = this.fields [iy] [ix - 1] == EMPTY;
							setTree (ix - 1, iy);
						}
					} while (! found);

					this.tentsInRow [iy]++;
					this.tentsInColumn [ix]++;
				}
				ix++;
			}
			iy++;
		}
	}

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

	/**
	 *  Fuer die Initialisierung und der graphischen Ausgabe von Instanzen der Klasse
	 */
	public void init ()
	{
		this.setTents ();
		this.setTrees ();
		this.setSize (this.widthsInPixels, this.heightInPixels);
		this.setBackground (java.awt.Color.WHITE);
		java.awt.Graphics2D graphics2D = bufferedImage.createGraphics ();
		this.paint (graphics2D);
		this.setVisible (true);
		this.setAlwaysOnTop (true);
	}

	/**
	 * Ueberschreibt die Methode paint aus der Klasse java.awt.Window und zeichnet die Instanz
	 * @param graphics: graphisches Objekt der Klasse java.awt.Graphics
	 */
	public void paint (java.awt.Graphics graphics)
	{
		drawCampingSite (graphics, this);
	}

Maussteuerung

Die Klasse CampingplatzGraphs implementiert die Klasse java.awt.event.MouseListener.^[1] 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.^[2]

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.

	public void mouseClicked (java.awt.event.MouseEvent event)
	{
		final long right = java.awt.event.MouseEvent.BUTTON3;
		long button = event.getButton ();
		int x = event.getX ();
		int y = event.getY ();
		int column = getColumn (x);
		int row = getRow (y);
		long field = this.fields [row] [column];
		if ((this.showTents == PUZZLE) && (column >= 0) && (column < this.sizeX) && (row >= 0) && (row < this.sizeY))
		{
			if (field != TREE)
			{
				if (button == right)
				{
					if (field == EMPTY)
					{
						this.fields [row] [column] = CORRECT_BLOCK;
					}
					else if (field == TENT)
					{
						this.fields [row] [column] = WRONG_BLOCK;
					}
					else if (field == CORRECT_BLOCK)
					{
						this.fields [row] [column] = EMPTY;
					}
					else if (field == WRONG_BLOCK)
					{
						this.fields [row] [column] = TENT;
					}
				}
				else if (field == TENT)
				{
					this.fields [row] [column] = CORRECT_GUESS;
					this.numberOfGuesses++;
				}
				else if (field == EMPTY)
				{
					this.fields [row] [column] = WRONG_GUESS;
					this.numberOfGuesses++;
				}
				else if (field == CORRECT_GUESS)
				{
					this.fields [row] [column] = TENT;
					this.numberOfGuesses--;
				}
				else if (field == WRONG_GUESS)
				{
					this.fields [row] [column] = EMPTY;
					this.numberOfGuesses--;
				}
				this.repaint (10, x - fieldSize, y - fieldSize, 2 * fieldSize, 2 * fieldSize);
			}
			if (this.numberOfGuesses == this.numberOfTents)
			{
				this.showTents = SOLUTION;
				this.repaint ();
			}
		}
	}

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.

	public static void main (java.lang.String [] arguments)
	{
		int widthOfSite  = 7; // Breite des Campingplatzes
		int heightOfSite = 7; // Hoehe des Campingplatzes
		long seed = java.lang.System.currentTimeMillis (); // aktuelle Systemzeit in Millisekunden als Startwert fuer die Pseudozufallszahlenfolge

		CampingplatzGraphs campingSite = new CampingplatzGraphs (widthOfSite, heightOfSite, seed, CampingplatzGraphs.PUZZLE); // erzeugt und initialisiert die Instanz campingSite ohne Loesung
		campingSite.init (); // oeffnet ein Fenster mit der Anzeige von campingSite

		seed = campingSite.getSeed (); // holt den tatsaechlichen Startwert der Pseudozufallszahlenfolge der Instanz campingSite
		CampingplatzGraphs campingSiteTents = new CampingplatzGraphs (widthOfSite, heightOfSite, seed, CampingplatzGraphs.SOLUTION); // erzeugt und initialisiert die Instanz campingSiteTents mit Loesung
		campingSiteTents.init (); // oeffnet ein Fenster mit der Anzeige von campingSiteTents
		campingSiteTents.setState (java.awt.Frame.ICONIFIED); // minimiert das Fenster als Icon, damit der Inhalt zunaechst nicht angezeigt wird
	}

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

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.

[1] va.awt.event.MouseListener, docs.oracle

[2] va.awt.event.MouseEvent, docs.oracle

[1]

[2]