ALL EN FR ES IT

Logo

Menü Main

Battleships

Beispiel mit ausgearbeiteter Lösung

     
    Wir wollen nun nebenstehendes Beispiel gemeinsam lösen. Dieses ist sicher nicht das schwierigste Rätsel. Es geht hier nur darum, zu zeigen, wir man überhaupt an das Lösen eines Battleships-Rätsels herangeht.
     
  a b c d e f g h i j    
0                   3  
1                     2  
2                     1  
3                     1  
4                     0  
5                     4  
6                     0
7                   5
8                     2
9                     2
  5 1 2 2 0 2 2 1 2 3    

Beginnen wir damit, alle Felder auszuschließen, die keine Schiffssegmente enthalten können. Das sind alle Zeilen/Spalten mit 0 und die Umgebung der bereits bekannten Schiffssegmente:

  a b c d e f g h i j    
0   x   x           3  
1 x x x   x           2  
2         x           1  
3         x           1  
4 x x x x x x x x x x 0  
5         x           4  
6 x x x x x x x x x x 0
7   x   x           5
8   x x x x           2
9         x           2
  5 1 2 2 0 2 2 1 2 3    

Man sieht sofort, dass (a0, b0) sowie (c7, d7) ein aus zwei Segmenten bestehendes Schiff beherbergen müssen. Die restlichen Felder von Spalte b können kein weiteres Schiffssegment beinhalten.

  a b c d e f g h i j    
0 x   x           3  
1 x x x   x           2  
2   x     x           1  
3   x     x           1  
4 x x x x x x x x x x 0  
5   x     x           4  
6 x x x x x x x x x x 0
7   x x           5
8   x x x x           2
9   x     x           2
  5 1 2 2 0 2 2 1 2 3    

Das 4er-Schlachtschiff muss sich in Zeile 5 befinden und vier der fünf Felder f5, g5, h5, i5 und j5 belegen. Die Felder a5, c5 und d5 müssen leer sein; ebenso die restlichen Felder in Spalte h.

  a b c d e f g h i j    
0 x   x     x     3  
1 x x x   x     x     2  
2   x     x     x     1  
3   x     x     x     1  
4 x x x x x x x x x x 0  
5 x x x x x + ? ? + 4  
6 x x x x x x x x x x 0
7   x x     x     5
8   x x x x     x     2
9   x     x     x     2
  5 1 2 2 0 2 2 1 2 3    

Versuchen wir nun, die beiden 3er-Kreuzer zu finden. Dafür scheint es zunächst einmal vier Möglichkeiten zu geben: (a7, a8, a9), (j0, j1, j2), (j1, j2, j3) und (j7, j8, j9).

Wir können (j1, j2, j3) sofort ausschließen, da in diesem Fall a2 und a3 leer sein müssten und es dann nicht mehr möglich wäre, in Spalte a fünf Schiffssegmente unterzubringen.

Die Schlachtschiffe auf (j0, j1, j2) und (j7, j8, j9) schließen sich gegenseitig aus. Das bedeutet, dass sich auf (a7, a8, a9) ein Kreuzer befinden muss:

  a b c d e f g h i j    
0 x   x     x     3  
1 x x x   x     x     2  
2   x     x     x     1  
3   x     x     x     1  
4 x x x x x x x x x x 0  
5 x x x x x ? + + ? 4  
6 x x x x x x x x x x 0
7 x x     x     5
8 x x x x     x     2
9 x     x     x     2
  5 1 2 2 0 2 2 1 2 3    

Es gibt nur zwei mögliche Positionen für den verbleibenden Kreuzer: (j0, j1, j2) und (j7, j8, j9). Welche der Möglichkeiten auch immer zutrifft, j5 muss leer sein. Damit ist das Schlachtschiff in der 5. Zeile vollständig definiert:

  a b c d e f g h i j    
0 x   x     x     3  
1 x x x   x     x     2  
2   x     x     x     1  
3   x     x     x     1  
4 x x x x x x x x x x 0  
5 x x x x x x 4  
6 x x x x x x x x x x 0
7 x x     x     5
8 x x x x     x     2
9 x     x     x     2
  5 1 2 2 0 2 2 1 2 3    

Wir zeigen nun, dass der zweite Kreuzer nicht die Felder (j7, j8, j9) belegen kann. Platzieren wir probeweise einmal den zweiten Kreuzer auf diesen Feldern und markieren wir alle Felder, die daraus folgend leer sein müssen:

  a b c d e f g h i j    
0 x   x     x   x 3  
1 x x x   x     x   x 2  
2   x     x     x   x 1  
3   x     x     x   x 1  
4 x x x x x x x x x x 0  
5 x x x x x x 4  
6 x x x x x x x x x x 0
7 x x     x x 5
8 x x x x x x x x 2
9 x x x x x x x x 2
  5 1 2 2 0 2 2 1 2 3    

Jetzt können wir folgenden Meta-Schluss ziehen: Entweder f7 oder g7 muss mit einem U-Boot belegt sein. Da die Situation bezüglich der Spalten f und g aber völlig symmetrisch ist in dem Sinn, dass sich die restliche Lösung nicht ändert, wären beide Felder möglich. Das steht aber ein Widerspruch zur Behauptung, dass die Lösung eindeutig ist!

Was aber, wenn die Aufgabe fehlerhaft ist? Puzzle-Designer können auch Fehler machen; und Programme können fehlerhaft programmiert sein. Versuchen wir einmal, ohne einen derartigen Meta-Schluss auszukommen.

Wir setzen probeweise U-Boot auf f7:

  a b c d e f g h i j    
0 x   x x   x   x 3  
1 x x x   x x   x   x 2  
2   x     x x   x   x 1  
3   x     x x   x   x 1  
4 x x x x x x x x x x 0  
5 x x x x x x 4  
6 x x x x x x x x x x 0
7 x x x x x 5
8 x x x x x x x x 2
9 x x x x x x x x 2
  5 1 2 2 0 2 2 1 2 3    

Jetzt finden wir für den verbliebenen 2er-Zerstörer keinen Platz mehr. Wenn wie das U-Boot statt auf f7 auf g7 setzen, ändert sich nichts; wieder ist für den Zerstörer kein Platz mehr.

Da der Kreuzer auf (j7, j8, j9) zu keiner Lösung führt, muss er sich auf (j0, j1, j2) befinden!

  a b c d e f g h i j    
0 x x x x x x x 3  
1 x x x   x     x x 2  
2 x x x x x x x x x 1  
3   x     x     x x x 1  
4 x x x x x x x x x x 0  
5 x x x x x x 4  
6 x x x x x x x x x x 0
7 x x     x   x 5
8 x x x x     x   x 2
9 x     x     x   x 2
  5 1 2 2 0 2 2 1 2 3    

Auf a3 muss sich ein U-Boot befinden; die restlichen Felder der 3. Zeile sind leer. Für den verbleibenden 2er-Zerstörer bleibt nur (f7, g7):

  a b c d e f g h i j    
0 x x x x x x x 3  
1 x x x   x x x x x 2  
2 x x x x x x x x x 1  
3 x x x x x x x x x 1  
4 x x x x x x x x x x 0  
5 x x x x x x 4  
6 x x x x x x x x x x 0
7 x x x x x 5
8 x x x x x x x   x 2
9 x     x x x x   x 2
  5 1 2 2 0 2 2 1 2 3    

Die restlichen drei U-Boote lassen sich schnell finden:

  a b c d e f g h i j    
0 x x x x x x x 3  
1 x x x x x x x x 2  
2 x x x x x x x x x 1  
3 x x x x x x x x x 1  
4 x x x x x x x x x x 0  
5 x x x x x x 4  
6 x x x x x x x x x x 0
7 x x x x x 5
8 x x x x x x x x 2
9 x x x x x x x x 2
  5 1 2 2 0 2 2 1 2 3    

Damit ist die Aufgabe gelöst!


Autor: Moshe Rubin
Quelle: Link: http://www.mountainvistasoft.com