NumberPuzzle

Ein bekanntes Puzzle-Spiel:
Die 15 zu Beginn zufällig gelegte Steine können mit dem Finger bewegt werden.
Ziel: Die Steine in der richtigen Reihenfolge platzieren. Erlaubt sind nur solche Züge, bei denen ein Stein, der horizontal oder vertikal direkt neben dem freien Feld liegt, dorthin verschoben wird.

Das Problem ist nicht für alle zufällig gewählte Start-Anordnungen lösbar. Das ist natürlich für den Benutzer frustrierend, wenn er nach einem langen Probieren keine Lösung finden kann. In unserer Implementierung werden die Steine zu Beginn immer so gesetzt, dass eine Lösung existiert. Die Lösbarkeit wird mit der Methode isSolvable() wie folgt überprüft. Es wird die so genannte Parität der Ausgangsstellung betrachtet. Sie bleibt bei einem Zug immer erhalten. Die Parität ergibt sich aus der Anzahl der ungeordneten Zahlenpaare. Dabei ist n1 die Anzahl der Zahlenpaare, die sich in falscher Reihenfolge befinden und n2 die Nummer der Reihe, in der sich das leere Feld befindet. Die Summe n = n1 + n2 ist entweder gerade oder ungerade. Ist die Parität ungerade ist, kann die Anordnung auf richtige Reihenfolge umgestellt werden. Ist die Parität gerade ist, so können die Steine nicht in die richtige Reihenfolge gebracht werden
(siehe http://de.wikipedia.org/wiki/15-Puzzle).

Beispiel im Online-Editor bearbeiten

App installieren auf Smartphone oder Tablet

QR-Code

Sources downloaden (NumberPuzzle.zip)

Programmcode:

// NumbrerPuzzle.java

package app.numberpuzzle;

import android.graphics.Point;
import ch.aplu.android.*;

public class NumberPuzzle extends GameGrid implements GGActorTouchListener
{
  private Location initialLoc;
  private Actor dragActor;

  public NumberPuzzle()
  {
    super(4, 4, cellZoom(60));
  }

  public void main()
  {
    getBg().clear(DKGRAY);
    setSimulationPeriod(30);
    NumberStone[] stones = new NumberStone[15];
    for (int i = 0; i < 15; i++)
    {
      stones[i] = new NumberStone(i);
      stones[i].addActorTouchListener(this, GGTouch.drag
        | GGTouch.release | GGTouch.press, true);
      //addActorNoRefresh(stones[i], new Location(i % 4, i / 4)); //for sorted arrangement
      addActorNoRefresh(stones[i], getRandomEmptyLocation()); //for random arrangement
    }
    while (!isSolvable())
    {
      L.d("Game is not solvable, doing some random shuffling...");
      NumberStone randomStone = stones[(int) (Math.random() * stones.length)];
      randomStone.setLocation(getRandomEmptyLocation());
    }
    doRun();
  }

  /**
   * Only empty locations in a 4-neighborhood of the initial location are valid
   * move locations.
   *
   * @param loc, the location checked for validity
   * @return
   */
  private boolean isMoveValid(Location loc)
  {
    if (!isInGrid(loc))
      return false;
    else if (getNumberOfActorsAt(loc) > 1)
      return false;
    else
      return initialLoc.getNeighbourLocations(0.5).contains(loc);
  }

  public void actorTouched(Actor actor, GGTouch touch, Point spot)
  {
    switch (touch.getEvent())
    {
      case GGTouch.press:
        initialLoc = actor.getLocation();
        dragActor = actor;
        dragActor.setOnTop();
        break;
      case GGTouch.drag:
        dragActor.setPixelLocation(new Point(touch.getX(), touch.getY()));
        break;
      case GGTouch.release:
        if (!isMoveValid(dragActor.getLocation()))
          dragActor.setLocation(initialLoc);
        dragActor.setLocationOffset(new Point(0, 0));
        if (isSolved())
        {
          cleanupGame();
        }
        break;
    }
  }

  private void cleanupGame()
  {
    Actor win = new Actor("youwin");
    addActorNoRefresh(win, new Location(0, 0));
    win.setPixelLocation(new Point(getNbHorzPix() / 2, getNbVertPix() / 2));
    refresh();
    setTouchEnabled(false);
    doPause();
  }

  private boolean isSolved()
  {
    int expectedId = 1;
    for (int y = 0; y < getNbVertCells(); y++)
    {
      for (int x = 0; x < getNbHorzCells(); x++)
      {
        NumberStone stone = (NumberStone) getOneActorAt(new Location(x, y));
        // gap has to be bottom right
        if (stone == null)
          if (expectedId == 16)
            return true;
          else
            return false;
        if (stone.getId() != expectedId)
          return false;
        expectedId++;
      }
    }
    return true; //should never be reached
  }

  private boolean isSolvable()
  {
    int parity = 0;
    for (int y = 0; y < getNbVertCells(); y++)
    {
      for (int x = 0; x < getNbHorzCells(); x++)
      {
        NumberStone check = (NumberStone) getOneActorAt(new Location(x, y));
        if (check == null) //don't do this for gap
          continue;
        NumberStone next = check.getNextStone();
        while (next != null)
        {
          if (next.getId() < check.getId())
            parity++;
          next = next.getNextStone();
        }
      }
    }
    // add row of gap to parity
    parity += getEmptyLocations().get(0).getY();
    return parity % 2 != 0;
  }
}

class NumberStone extends Actor
{
  public NumberStone(int id)
  {
    super("stone", 15);
    show(id);
  }

  public int getId()
  {
    return this.getIdVisible() + 1;
  }

   public NumberStone getNextStone()
  {
    NumberStone nextStone = null;
    int nextX = getX();
    int nextY = getY();
    // loop is necessary to handle gap (iterates twice if at gap)
    while (nextStone == null)
    {
      nextX++;
      // switch to next row this stone is last of row
      if (nextX >= gameGrid.getNbHorzCells())
      {
        nextX = 0;
        nextY += 1;
      }
      // return null if we were at last position
      if (nextY >= gameGrid.getNbHorzCells())
        return null;
      nextStone = (NumberStone) gameGrid.getOneActorAt(new Location(nextX, nextY));
    }
    return nextStone;
  }

  public String toString()
  {
    return "NS " + getId() + " at: " + getLocation();
  }
}

Erklärungen zum Programmcode:

setScreenOrientation(ScreenOrientation.FIXED)	Das GameGrid-Fenster bleibt währen des ganzen Spieles im Hoch- bzw. Querformat, je nach dem in welcher Stellung es war, als das Spiel gestartet wurde. Das Bild dreht sich also nicht, wenn Smartphone gedreht wird (standardmässig ist es der Fall)
Monitor.putSleep()	Haltet den Main-Thread an, bis die Karten zurückgedreht sind
Monitor.wakeUp()	Der Main-Thread wird fortgesetzt
setTouchEnabled(false)	Deaktiviert die Tauch-Events

Game-Apps für Smartphones und Tablets	English
Bern University oh Teacher Education

Game-Apps für Smartphones und Tablets

NumberPuzzle