Schiffe versenken mit Backtracking

[nouse1211]

Hi Leute,
muss folgendes in Java für die Uni programmieren:

Aufgabenstellung:
"Schreiben Sie einen Backtracking-Algorithmus zum Auffinden einer verträglichen Schiffsverteilung. (Die wahrscheinlich einfachste Lösung erweitert die möglichen Einträge im Spielfeld um eine angenommene Schiffskoordinate). Modifizieren Sie den Backtracking-Algorithmus, sodass nacheinander alle möglichen Schiffsverteilungen bestimmt werden. Für jede Koordinate des Spielfeldes soll berechnet werden, wie oft sie durch ein Schiff belegt wurde. Die Koordinate mit der häufigsten Belegung wird als nächstes Ziel gewählt."

Ich habe ein zweidimensionales Spielfeld-Array [10][10], in dem ich die Positionen speichere und mehrere Schiffe mit unterschiedlicher Länge und Anzahl positionieren kann:

Name: battleship, Länge: 5, Breite: 1, Anzahl: 1
Name: cruiser, Länge: 4, Breite: 1, Anzahl: 2
Name: tankship, Länge: 3, Breite: 1, Anzahl: 1
Name: minesweeper, Länge: 2, Breite: 1, Anzahl: 2
Name: speedboat, Länge: 1, Breite: 1, Anzahl: 3

Die Schiffe können sowohl horizonatl als auch vertikal platziert werden und dürfen sich nicht berühren und nicht um die Ecke gehen!

Nun sollen die Schiffe mittels Rekursion und Backtracking auf dem Spielfeld platziert werden wie in der Angabe gefordert.

Kann mir wer einen Denkanstoß geben, wie ich da Anfange soll? Brauche kein fertigen Code, mir reichen Idee, wie man das umsetzten könnte. Pseudocode reicht auch :p
Sitz auf dem Schlauch!

[BLUESCREEN3D]

Das sind ja gleich mehrere Aufgabenteile. Mach erstmal nur das hier:


Schreiben Sie einen Backtracking-Algorithmus zum Auffinden einer verträglichen Schiffsverteilung. (Die wahrscheinlich einfachste Lösung erweitert die möglichen Einträge im Spielfeld um eine angenommene Schiffskoordinate).
Was sind denn die "möglichen Einträge im Spielfeld"?
Gibt es eine Klasse "Schiff"?


Ich habe ein zweidimensionales Spielfeld-Array [10][10], in dem ich die Positionen speichere
War das so vorgegeben, oder hast du dir das Array überlegt?


Kann mir wer einen Denkanstoß geben, wie ich da Anfange soll?
Mit einem der Schiffe musst du ja anfangen und es auf dem noch leeren Feld positionieren.
Schreib also erstmal eine Methode positioniereWeiteresSchiff(), die genau das tut.
Dein Ziel sollte es danach sein, dass die Methode sich rekursiv selbst aufruft, um alle Schiffe zu positionieren.

[nouse1211]

Das sind ja gleich mehrere Aufgabenteile. Mach erstmal nur das hier:

Gibt es eine Klasse "Schiff"?

Ich habe das wie folgt unterteilt:

/**
* Ship: abstract class to create an object of type Ship
*
* @version 2
*
*/
package Shipbattle;

public abstract class Ship {
/**
* Saves the length of this object
*/
public int length;
/**
* Saves the width of this object
*/
public int width;
/**
* Saves the name of this object
*/
public String name;
/**
* Saves the health of this object, if it is not-hit, hit or plunged
*/
public int health;

/**
* Class constructor specifying the length, width, name and health of object
* to create
*
* @param length
* to set the length
* @param width
* to set the width
* @param name
* to set the name
*/
public Ship(int length, int width, String name) {
this.length = length;
this.width = width;
this.name = name;
this.health = this.length * this.width;
}

/**
* Gets the health of the object
*
* @return an number between 0 and length of ship
*/
public int getHealth() {
return this.health;
}

/**
* Gets the length of the object
*
* @return length of object
*/
public int getLength() {
return this.length;
}

/**
* Gets the name of the object
*
* @return name of object
*/
public String getName() {
return this.name;
}

/**
* Gets the width of the object
*
* @return width of object
*/
public int getWidth() {
return this.width;
}

/**
* Sets the health of the object
*
* @param int
* an number between 0 and length of ship
*/
public void setHealth(int health) {
this.health = health;
}

/**
* Sets the length of the object
*
* @param int
* length of object
*/
public void setLength(int length) {
this.length = length;
}

/**
* Sets the name of the object
*
* @param string
* name of object
*/
public void setName(String name) {
this.name = name;
}

/**
* Sets the width of the object
*
* @return int width of object
*/
public void setWidth(int width) {
this.width = width;
}

/**
* Sets the health of the object, after it was hit by subtracting 1 from the
* length of ship
*
* @return an number between 0 and length of ship
*/
public int shipHit() {
return --this.health;
}
}



/**
* ShipPos: class to save a ship position with the ship's direction
*
* @version 2
*
*/
package Shipbattle;

public class ShipPos {

public int x;
public int y;
public Direction direction;
}



/**
* BattleFleet: class to create accumulation of all ships that are available
*
* @version 2
*
*/
package Shipbattle;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class BattleFleet {
/**
* Saves all the ships with the name of ship as key and the availability as
* value
*
* @see#java.util.HashMap
*/
public HashMap<String, Integer> battle;
// Anzahl der verfügbaren Schiffe
private int shipCounter = 0;

/**
* Class constructor of object to create
*/
public BattleFleet() {
this.battle = new HashMap<String, Integer>();

this.battle.put("Aircraftcarrier", new Integer(0));
this.battle.put("Battleship", new Integer(1));
this.battle.put("Cruiser", new Integer(2));
this.battle.put("Tankship", new Integer(1));
this.battle.put("Minesweeper", new Integer(2));
this.battle.put("Speedboat", new Integer(3));

// Anzahl der verfügbaren Schiffe
shipCounter = shipCounter();
}

public int remainingShips() {
return this.shipCounter;
}

public int shipCounter() {
int shipCounter = 0;
Collection<Integer> values = battle.values();
for (int i : values)
shipCounter += i;
return shipCounter;
}

@SuppressWarnings("unchecked")
public ArrayList<String> getShips() {
ArrayList<String> ship = new ArrayList<String>();
Iterator it = battle.entrySet().iterator();
Map.Entry<String, Integer> entry = null;
while (it.hasNext()) {
entry = (Map.Entry<String, Integer>) it.next();
ship.add(entry.getKey());
ship.add(entry.getValue().toString());
}
return ship;
}

public void shipPlunged() {
shipCounter--;
}
}



Was sind denn die "möglichen Einträge im Spielfeld"?

/**
* Status: Enum class to create types of gamefield status
*
* @version 2
*
*/
package Shipbattle;

public enum Status {
// Feld außerhalb des Spielbretts
error,

// Feld ohne Schiff; Feld bereits beschossen und nichts getroffen
miss,

// Feld mit Schiff; Schiffteil auf diesem Feld beschossen und bereits
// getroffen
strike,

// Feld mit Schiff; Schiffteil auf diesem Feld noch nicht beschossen (d.h.
// nicht getroffen)
target,

// Feld mit Schiff, komplettes Schiff versenkt
plunged,

// Feld ohne Schiff
water,

// auf diesem Feld kann kein Schiff gesetzt werden, da dort ein anderes
// angerenzt
blocked
}



War das so vorgegeben, oder hast du dir das Array überlegt?

Das habe ich mir selber überlegt.


/**
* GameField: class to create an object of type GameField
*
* @version 2
*
*/
package Shipbattle;

import java.util.Observable;
import java.util.Observer;

public class GameField extends Observable {
/**
* Saves the length and width of this object
*/
public int yfield;
/**
* Saves the length and width of this object
*/
public int xfield;
/**
* Saves the single fields in this object
*/
public Field[][] Game1;
public Field[][] Game2;
/**
* Creates an instance of a single field
*/
Field field;
/**
* Saves the Counter of fields, that are set on target
*/
public int targetFields = 0;

/**
* Class constructor creates a new game-field with the length and width of
* this object and a extra row at the beginning and the end of field and a
* extra column at the beginning and the end of field. Sets the fields, the
* player can use on status water and the extra fields on status error
*/
public GameField() {
this(10, 10);
}

public GameField(int width, int height) {
super();
this.xfield = width;
this.yfield = height;
this.Game1 = new Field[this.yfield][this.xfield];
this.Game2 = new Field[this.yfield][this.xfield];
for (int i = 0; i < this.yfield; i++) {
for (int j = 0; j < this.xfield; j++) {
this.Game1[i][j] = new Field(i, j);
this.Game2[i][j] = new Field(i, j);
}
}
}

/**
* Sets the ship on fields
*
* @param int
* x-coordinate of the first field
* @param int
* y-coordinate of the first field
* @param char
* direction the ship should be set. value is 'v' for vertical
* and 'h' for horizontal
* @param ship
* type of ship that should be set on this fields
*/
public void setShip(int playerId, ShipPos coor, Ship ship) {
int x = coor.x;
int y = coor.y;

if (coor.direction == Direction.horizontal) {
// Schiff waagerecht setzen
int b = x;
for (int i = ship.getLength(); i > 0; i--) {
setFieldStatus(playerId, y, b, Status.target);
b++;
this.targetFields++;
}
}

// Schiff senkrecht setzten
if (coor.direction == Direction.vertical) {
int b = y;
for (int i = ship.getLength(); i > 0; i--) {
setFieldStatus(playerId, b, x, Status.target);
b++;
this.targetFields++;
}
}
super.setChanged();
super.notifyObservers();
}

public Field[][] getGame(int playerId) {
if (playerId == 1)
return Game1;
else
return Game2;
}

public void setFieldStatus(int playerId, int y, int x, Status status) {
if (x >= 0 && x < xfield && y >= 0 && y <= yfield)
if (playerId == 1)
Game1[y][x].setStatus(status);
else
Game2[y][x].setStatus(status);

super.setChanged();
super.notifyObservers();
}

/*
* (non-Javadoc)
*
* @see java.util.Observable#addObserver(java.util.Observe r)
*/
@Override
public void setChanged() {
super.setChanged();
}

/**
* @param observer
* Adds an Observer to the GameField
*/
public void putObserver(Observer observer) {
this.addObserver(observer);
}

/**
* @return the targetFields
*/
public int getTargetFields() {
return targetFields;
}
}



Mit einem der Schiffe musst du ja anfangen und es auf dem noch leeren Feld positionieren.

Ich habe mir das mit Backtracking und Rekursion bei dem 8-Dame (Queens) angesehen und wollte das ähnlich machen.

Meine Überlegungen:
- ich gehe in die erste Zeile und setzte das Schiff
- ich gehe in die zweite zeile und setzte das Schiff dort so, das es das Schiff aus der ersten Zeile nicht berührt
- usw.

Aber meine Probleme hierbei:
- dann sind doch alle Schiffe nur horizontal gesetzt! Aber es sollten doch einige auch vertikal platziert werden!
- laut Angabe: "Für jede Koordinate des Spielfeldes soll berechnet werden, wie oft sie durch ein Schiff belegt wurde. Die Koordinate mit der häufigsten Belegung wird als nächstes Ziel gewählt." Soll ich mir ALLE möglichen Positionierungen merken (und wie) und dann die beste nehmen? Das dauert doch lange bis dann ein Schiff gesetzt wird, oder?


Schreib also erstmal eine Methode positioniereWeiteresSchiff(), die genau das tut.
Dein Ziel sollte es danach sein, dass die Methode sich rekursiv selbst aufruft, um alle Schiffe zu positionieren.

Vielleicht lieber positioniereWeiteresSchiff(int y), die die vorherige y Koordinate (Spalten in meinem Spielfeld) des Spielfeldes bekommt, auf der ich das letzte Schiff platziert habe? Bei dem ersten Schiff die 0 usw.?

[BLUESCREEN3D]

Meine Überlegungen:
- ich gehe in die erste Zeile und setzte das Schiff
- ich gehe in die zweite zeile und setzte das Schiff dort so, das es das Schiff aus der ersten Zeile nicht berührt

Das ist schonmal zu einfach gedacht - es können doch auch zwei oder mehr Schiffe in einer Zeile sein.


- dann sind doch alle Schiffe nur horizontal gesetzt! Aber es sollten doch einige auch vertikal platziert werden!

Genau deshalb musst du in der Backtracking-Funktion sowohl horizontale als auch vertikale Möglichkeiten durchprobieren.


- laut Angabe: "Für jede Koordinate des Spielfeldes soll berechnet werden, wie oft sie durch ein Schiff belegt wurde. Die Koordinate mit der häufigsten Belegung wird als nächstes Ziel gewählt." Soll ich mir ALLE möglichen Positionierungen merken (und wie) und dann die beste nehmen?

Hat das wirklich was mit der Verteilung der Schiffe zu tun und nicht eher mit einer KI, die sich ein Zielfeld suchen soll?
Speichern kannst du die Anzahlen auf jeden Fall mit einem einfachen int[][]-Array, das für jedes Feld die Anzahl der Verteilungen enthält, bei denen es belegt war. Dieser Teil der Aufgabe ist aber erstmal unwichtig.


Vielleicht lieber positioniereWeiteresSchiff(int y), die die vorherige y Koordinate (Spalten in meinem Spielfeld) des Spielfeldes bekommt, auf der ich das letzte Schiff platziert habe? Bei dem ersten Schiff die 0 usw.?

Welche Parameter du übergeben willst, musst du dir natürlich selbst überlegen :D
Aber die y-Koordinate bringt nichts (Grund siehe oben). Das ist zu sehr vom 8-Damen-Problem abgeguckt, wo niemals zwei Damen in einer Zeile stehen würden. Bei den Schiffen ist das was anderes.
Was du natürlich übergeben musst, ist die bisherige Verteilung, damit die Backtracking-Funktion da weiterarbeiten kann.

Noch ein Tipp: Fang erstmal so an, dass Schiffe sich berühren und überlappen können. Wenn du es hinkriegst, dass überhaupt erstmal für jedes Schiff eine Position und Ausrichtung festgelegt wird, hast du den Anfang schon geschafft.