SameGame Lösbarkeitsanalyse

[angelnc]

Hallo an alle,
ich hoffe ich bin im richtigen Unterforum gelandet.

Ich programmiere gerade mit ein paar Kommilitonen eine Variante von SameGame.
Wir möchten zufällige Level generieren und dann eine Lösbarkeitsanalyse durchführen.
Leider habe ich zu der Lösbarkeitsanalyse über Google keine brauchbaren Ergebnisse gefunden und hatte gehofft, dass mir hier jemand helfen kann.

Gruß
angelnc

 

[XHelp]

Spontan fällt mir da nur ein den Baum aufzubauen und Backtracking zu machen.
[EDIT]Jo, das ist NP-Vollständig, du wirst da keine effizienten Algos finden/bauen können[/EDIT]

 

[angelnc]

Spontan fällt mir da nur ein den Baum aufzubauen und Backtracking zu machen.

Mit Backtracking habe ich es auch probiert.
Leider liefert mein Algorithmus falsche Ergebnisse.

Hier ist mein Ansatz:

public boolean isSolvable() {
		// speichert eine Kopie des aktuellen Spielfelds zur spaeteren
		// Wiederherstellung
		Token[][] gb = this.gameboard.clone();
		// geht das Spielfeld durch und ruft für jeden Stein
		// isSolvableForSingleToken auf
		for (int row = 0; row < gb.length; row++)
			for (int col = 0; col < gb[0].length; col++)
				// wenn ein Aufruf true zurück gibt, gib true zurueck
				if (isSolvableForSingleToken(row, col, gameboard))
					return true;
		// Spielfeld wieder zuruecksetzen
		this.gameboard = gb;
		// wenn man hier ankommt ist das Spielfeld nicht loesbar -> false
		return false;
	}

	private boolean isSolvableForSingleToken(int rows, int cols,
			Token[][] gameboard) {
		// speichert eine Kopie des aktuellen Spielfelds zur spaeteren
		// Wiederherstellung
		Token[][] gb = gameboard.clone();
		this.gameboard = gb;
		// wenn das Spiel gewonnen ist, ist es loesbar
		if (gameIsWon())
			return true;
		// wenn das Spiel verloren ist, ist es auf diesem Weg nicht loesbar
		if (gameIsLost())
			return false;
		// wenn du ein leeres Feld gewaehlt hast, hoere auf
		if (gb[rows][cols].getTokenType() == 0)
			return false;
		// wenn der gewaehlte Stein entfernbar ist, entferne ihn und ueberpruefe
		// jeden Stein des neuen Spielfelds auf Loesbarkeit
		if (countNeighboursOfSameColour(rows, cols, new Vector<String>())
				.size() >= minTokenNumberToRemove) {
			removeToken(rows, cols);
			for (int row = 0; row < gameboard.length; row++)
				for (int col = 0; col < gameboard[0].length; col++)
					if (isSolvableForSingleToken(row, col, gb))
						return true;
			// das Spielfeld zuruecksetzen
			this.gameboard = gb;
		}
		// wenn man hier ankommt ist das Spielfeld von diesem Stein aus nicht
		// loesbar
		return false;
	}

 

[XHelp]

Sieht ein wenig komisch aus. Wozu schlippst du rows, cols rum?
es sollte eigentlich so ablaufen:

public static boolean isSolvable(Token[][] gameboard) {
  if (isEmtpyBoard(gameboard)==true) {
    return true;
  }
  if (noMoreMoves(gameboard)==true) {
    return false;
  }
  for (Zug curZug: listeDerZuege) {
    if (isSolvable(makeMove(gameboard,curZug))==true) {
      return true;
    }
  }
  return false;
}

Sprich du musst nicht auf irgendeinem gemeinsamen Spielbrett alle Züge durchgehen, sondern das Brett mitgeben

 

[angelnc]

Sieht ein wenig komisch aus. Wozu schlippst du rows, cols rum?
es sollte eigentlich so ablaufen:

public static boolean isSolvable(Token[][] gameboard) {
  if (isEmtpyBoard(gameboard)==true) {
    return true;
  }
  if (noMoreMoves(gameboard)==true) {
    return false;
  }
  for (Zug curZug: listeDerZuege) {
    if (isSolvable(makeMove(gameboard,curZug))==true) {
      return true;
    }
  }
  return false;
}

Sprich du musst nicht auf irgendeinem gemeinsamen Spielbrett alle Züge durchgehen, sondern das Brett mitgeben

Die ersten beiden if-Klauseln verstehe ich noch, die for-Schleife aber nicht.
Könntest du mir erläutern, was die tun soll?

 

[XHelp]

Du simulierst damit jeden möglichen Zug. Machst quasi eine Tiefensuche im Baum.
Die Schleife sollte also heißen "für jeden Möglichen Zug, tue..."
Und sobald du einen Weg gefunden hast das Spiel zu gewinnen, kannst du ja schon abbrechen.
Wenn der aktuelle Zug aber nicht zum erfolg führt, dann musst du die anderen dennoch untersuchen.

 

[angelnc]

Ich dachte eigentlich das hätte ich gemacht , aber vielleicht bin ich einfach zu müde, um den Unterschied zu sehen. Ich schaue es mir morgen noch mal an, wenn ich wacher bin.

Auf jeden Fall schon mal vielen Dank für deine Hilfe. :toll:

 

[XHelp]

Was mir jetzt so einfällt: du könntest dir nicht nur "true" und "false" zurückgeben lassen, sondern den Zug (bzw. null). So kannst du nicht nur bestimmen ob es Lösbar ist oder nicht, sondern hast gleich eine optimale Spielstrategie (ist ja kein Zusätzlicher Rechenaufwand)