Schiffe versenken Algorithmus Backtracking

This site uses cookies. By continuing to browse this site, you are agreeing to our Cookie Policy.

  • Schiffe versenken Algorithmus Backtracking

    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!
  • du weist was Backtracking ist, oder?

    Du setzt deine Schiffzelle an erste Position und prüfst danach ob du es nach deinem Regelwerk möglich ist mit dieser Teillösung weitere Schiffzellen zu setzen.
    Wenn es nicht möglich ist, dann gehst du wieder einen Schritt zurück und probierst die nächste Schiffzelle. Ansonsten nimmst du die Teillösung und versuchst es damit weiter.

    Zum Aufbauen kannst du einen Algorithmus für das n-Damen-Problem verwenden: Schachbrett: 8 Damen Problem
  • 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?

    Ich schreib also erstmal eine Methode 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.? Die Methode soll sich rekursiv selbst aufruft, um alle Schiffe zu positionieren.
  • nouse1211 wrote:

    - dann sind doch alle Schiffe nur horizontal gesetzt! Aber es sollten doch einige auch vertikal platziert werden!
    bist du denn schon soweit dass alle Schiffe unter Beibehaltung der Regeln horizontal gesetzt werden? Das Spielfeld sieht natürlich immer gleich aus und enthält die simpelste Lösung.
    Wenn du mehrere Lösungen haben willst, dann musst du dir wiederum merken, was zu einer erfolgreichen Konstellation führte und das erste dann jeweils als "belegt" annehmen. Aber erstmal solltest du zu einer Lösung kommen.

    nouse1211 wrote:

    - 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."

    auch das würde ich erst hinten einreihen... wenn dein Backtracking funktioniert kannst du so einen Zähler recht einfach nachrüsten.

    nouse1211 wrote:

    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?

    Geht es denn jetzt ums setzen oder ums feuern? Du sollst deine Schiffe bestimmt nicht da positionieren, wo Backtracking sie am häufigsten belegt hätte. Beim feuern brauchst du die Vorberechnung nur einmal zu machen. Und kannst dann die wahrscheinlichsten Punkte schrittweise runterzählen bis du den ersten Treffer machst.

    Aber step by step...