Fünfzehner-Spiel - Programmieraufgaben.ch

Fünfzehner-Spiel (Datenstrukturen)

Schreiben Sie eine Datenstruktur Fuenfzehner, die die Zustände des berühmten 15-er-Spiels angibt. Das Spiel (auch bekannt unter den Namen Schiebepuzzle oder "Sliding Puzzle") besteht aus 15 verschiebbaren Plättchen, die auf 16 Plätzen
im Quadrat umher geschoben werden können. Dabei ist (nach Adam Ries) immer eine Position frei.

Fünfzehner Spiel

Schreiben Sie dazu in einer separaten (Haupt-)Klasse die folgenden Methoden:

initialisiere   (f: Fuenfzehner)
schiebeVonRechts(f: Fuenfzehner)
schiebeVonLinks (f: Fuenfzehner)
schiebeVonOben  (f: Fuenfzehner)
schiebeVonUnten (f: Fuenfzehner)
print           (f: Fuenfzehner)

Dabei wird beim Initialisieren einfach in Leserichtung eingefüllt (erste Zeile: 1, 2, 3, 4, zweite Zeile: 5, 6, 7, 8, ...). Das letzte Feld bleibt beim Initialisieren leer. Die print()-Methode gibt den aktuellen Zustand auf der Konsole zur Fehlersuche aus. Alternativ darf die Datenstruktur auch grafisch ausgegeben werden. Die Methoden schiebeVonXYZ() schieben aus der Sicht des leeren Feldes von oben, unten, links oder rechts nach. Sollte die Lücke am Rand stehen, können einzelne Aufrufe auch sinnlos sein und sollten deshalb ignoriert werden.

Zusatzaufgabe: Schreiben Sie eine Methode mischen(f: Fuenfzehner), die eine gegebene Position wieder gut"Gut mischen" steht hier im Sinne eines Mischalgorithmus, der als Resultat jede Permutation (also auch jede sortierte Position) mit gleicher Wahrscheinlichkeit zulässt. mischt.

0 Kommentare

Bitte melde dich an um einen Kommentar abzugeben

// Processing
// grafische Loesung mit Tastatursteuerung per Richtungspfeile
// by igo schaller

fuenfzehnSpiel Spiel = new fuenfzehnSpiel();
PFont schrift;

// setup() wird beim Start einmal ausgefuehrt
void setup() {
  background(200,200,200);
  stroke(100,100,100);
  size(400,400);
  smooth();
  schrift = loadFont("AlbaSuper-40.vlw");
  Spiel.mischen(127);
  Spiel.zeichnen();

}

// draw() wird pro Sekunde 10-mal ausgefuehrt
void draw() {
  Spiel.zeichnen();
}

// Tastatursteuerung: wird bei Tastendruck durchlaufen
void keyPressed() {
  if (key == CODED) {
    switch (keyCode) {
    case UP: 
      Spiel.schiebeVonUnten();
      break;
    case LEFT: 
      Spiel.schiebeVonRechts();
      break;
    case RIGHT: 
       Spiel.schiebeVonLinks();
      break;
    case DOWN: 
      Spiel.schiebeVonOben();
      break;
    }
  }
}

// Klasse 15-er-Spiel
class fuenfzehnSpiel {
  int[][] spielfeld = new int[4][4];  // Array mit Dimension 4 x 4
  int posLeerX;
  int posLeerY;
  
  // Konstruktor
  fuenfzehnSpiel() {
    // Spielfeld wird fortlaufend mit den Werten 1 bis 15 gefuellt 
    for (int i = 0; i < 15; i++) {
      spielfeld[i%4][int(i/4)] = i + 1; 
    }
    // Ecke unten rechts mit Position 3,3 ist leer
    spielfeld[3][3] = 0;   
    posLeerX = 3;
    posLeerY = 3;
  }
  
  // 4 Methoden für die Schiebevorgaenge
  void schiebeVonRechts() {
    if (posLeerX < 3) {
      spielfeld[posLeerX][posLeerY] = spielfeld[posLeerX + 1][posLeerY];
      println(spielfeld[posLeerX + 1][posLeerY]);
      spielfeld[posLeerX + 1][posLeerY] = 0;
      posLeerX++;
    }  
  }
  void schiebeVonLinks() {
    if (posLeerX > 0) {
      spielfeld[posLeerX][posLeerY] = spielfeld[posLeerX - 1][posLeerY];
      spielfeld[posLeerX - 1][posLeerY] = 0;
      posLeerX--;
    }      
  }
  void schiebeVonOben() {
    if (posLeerY > 0) {
      spielfeld[posLeerX][posLeerY] = spielfeld[posLeerX][posLeerY-1];
      spielfeld[posLeerX][posLeerY-1] = 0;
      posLeerY--;
    }       
  }
  void schiebeVonUnten() {
    if (posLeerY < 3) {
      spielfeld[posLeerX][posLeerY] = spielfeld[posLeerX][posLeerY+1];
      spielfeld[posLeerX][posLeerY+1] = 0;
      posLeerY++;
    }    
  }  

  // das Spielfeld zeichnet sich
  void zeichnen(){
    int kantenLaenge = int(width/4);
    int spalte, zeile;
    int pxPosX, pxPosY;
    for (int i = 0; i < 16; i++) {
      spalte = i % 4;
      zeile = int(i/4);
      pxPosX = spalte * kantenLaenge;
      pxPosY = zeile * kantenLaenge;
      // falls Feldnummer gerade mit Fuellfarbe gleich Rot setzen, sonst.. 
      if(spielfeld[spalte][zeile] % 2 == 1) {
        fill(255,0,0);
      }
      else
      {
        // falls Feldnummer ungleich 0 Fuellfarbe gleich Weiss setzen, sonst gleich Schwarz
        if (spielfeld[spalte][zeile] != 0) { 
          fill(255,255,255);
        }
        else {
          fill(0,0,0);
        }
      }
      // Feld an berechneter Position als Rechteck zeichnen
      rect(pxPosX, pxPosY, pxPosX + kantenLaenge, pxPosY + kantenLaenge);
      fill(0,0,0);
      // Feld mit Nummer beschriften
      textFont(schrift, int(kantenLaenge*2/3)); 
      textAlign(CENTER, TOP);
      text(spielfeld[spalte][zeile], pxPosX+int(kantenLaenge/2), pxPosY+int(kantenLaenge/6));
    }   
  }

  // das Spielfeld mischt sich
  void mischen(int anzDurchlaeufe) {
    int zufallRichtung;
    int zufallLaenge;
    
    // das leere Feld wird an die Position 1, 1 verschoben
    schiebeVonLinks();
    schiebeVonLinks();
    schiebeVonOben();
    schiebeVonOben();
    schiebeVonOben();
    // bestimmte Anzahl-mal wird in eine zufaellige Richtung zufaellig oft mal geschoben
    for (int i = 0; i < anzDurchlaeufe; i++) {
      zufallRichtung = int(random(1)*3);
      zufallLaenge = int(random(1)*3)+1;
      println(zufallRichtung + " | " + zufallLaenge);
      switch (zufallRichtung) {
      case 0:                       // von unten
        for (int j = 0; j < zufallLaenge; j++) {
          schiebeVonUnten();
        }
        break;
      case 1:                       //von rechts      
        for (int j = 0; j < zufallLaenge; j++) {
          schiebeVonRechts();
        }
        break;
      case 2:                        //von links     
        for (int j = 0; j < zufallLaenge; j++) {
          schiebeVonLinks();
        }
        break;
      case 3:                        //von oben      
        for (int j = 0; j < zufallLaenge; j++) {
          schiebeVonOben();
        }
        break;
      }
    }
  } 

}

package ch.santis.programmierenlernen.kapitel8;

import java.util.Random;
import java.util.Scanner;

//Aufgabe 8.3 Fünfzehner-Spiel (Consolen-Ausgabe vom Object Array mit Integers und einem String für "x")
public class Aufgabe_8_3 {
	
	public static void main(String[] args) {
		new Aufgabe_8_3().top();
	}
	
	void top() {
		Object[][] spielfeld = new Object [4][4];
		int posx = 3; // Anfangsposition-X von "x"
		int posy = 3; // Anfangsposition-Y von "x"
		initialisiere(spielfeld);
		String control = "";
		while(!"end".equalsIgnoreCase(control)) {
			print(spielfeld);
			control = eingabeString("WASD Steuerung - Rechts(d), Links(a), Oben(w) oder Unten(s) eingeben - beenden(end) oder mischen(mix):");
			if("d".equalsIgnoreCase(control)) {
				posx = schiebeVonRechts(spielfeld, posx, posy);
			}
			else if("a".equalsIgnoreCase(control)) {
				posx = schiebeVonLinks(spielfeld, posx, posy);
			}
			else if("s".equalsIgnoreCase(control)) {
				posy = schiebeVonUnten(spielfeld, posx, posy);
			}
			else if("w".equalsIgnoreCase(control)) {
				posy = schiebeVonOben(spielfeld, posx, posy);
			}
			else if("end".equalsIgnoreCase(control)) {
				System.out.println("Spiel beendet.");
			}
			else if("mix".equalsIgnoreCase(control)) {
				arrayMix(spielfeld);
				//Neue Position von "x" ermitteln
				//mit i%4 und i/4 anstatt zwei(2) verschachtelten for-Schleifen sparen wir uns hier bis zu 4 Schleifen-Durchgänge
				for(int i = 0; i <= 15; i++) {
					if(spielfeld[i%4][i/4] instanceof String) {
						posx = i%4;
						posy = i/4;
						break; //Wenn String gefunden - beende die Schleife
					}
				}
			}
		} //End of while loop
	} //End of top
	
	int schiebeVonRechts(Object[][] spielfeld, int posx, int posy) {
		if (posx < 3) {
			spielfeld[posx][posy] = spielfeld[posx + 1][posy];
			spielfeld[posx+ 1][posy] = "x";
			return posx+1;
			}
		return posx;
		}	  

	int schiebeVonLinks(Object[][] spielfeld, int posx, int posy) {
		if (posx > 0) {
			spielfeld[posx][posy] = spielfeld[posx - 1][posy];
			spielfeld[posx- 1][posy] = "x";
			return posx-1;
			}
		return posx;
		}
	  

	int schiebeVonOben(Object[][] spielfeld, int posx, int posy) {
		if (posy > 0) {
			spielfeld[posx][posy] = spielfeld[posx][posy-1];
			spielfeld[posx][posy-1] = "x";
			return posy-1;
			}
		return posy;
		}	  

	int schiebeVonUnten(Object[][] spielfeld, int posx, int posy) {
		if (posy < 3) {
			spielfeld[posx][posy] = spielfeld[posx][posy+1];
			spielfeld[posx][posy+1] = "x";
			return posy+1;
			}
		return posy;
		}	

	void initialisiere(Object[][] spielfeld) {
		//mit i%4 und i/4 anstatt zwei(2) verschachtelten for-Schleifen sparen wir uns hier 5 Schleifen-Durchgänge
		for(int i = 0; i < 15; i++) {
			spielfeld[i%4][i/4] = i + 1;
		}
		spielfeld[3][3] = "x";
	}
	
	void print(Object[][] spielfeld) {
		System.out.println("======");
		// Hier verwenden wird die Option mit zwei(2) for-Schleifen anstatt i%4 und i/4 (was möglich wäre)
		// es dient zur Demostration beider Optionen
		for(int i = 0; i < spielfeld.length; i++) {
			String lz = "";
			for(int i2 = 0; i2 < spielfeld.length; i2++) {
				Object wert = spielfeld[i2][i];
				if(wert instanceof Integer ) {
					if( (int)wert < 10) { lz = "  "; }
					else if( (int)wert >= 10) { lz = " "; }
				}
				else if(wert instanceof String) {
					lz = "  ";
				}
				// Print Zahlen nebeneinander auf der selben Zeile
				System.out.print(lz + spielfeld[i2][i]);
			}
			System.out.println("");
		}
		System.out.println("======");
	}
	
	
    Object[][] arrayMix(Object[][] spielfeld) {
        Object tmp;
        int rnd;
        int rnd2;
        Random r = new Random();
        // Hier verwenden wird die Option mit zwei(2) for-Schleifen anstatt i%4 und i/4 (was möglich wäre)
     	// es dient zur Demostration beider Optionen
        for (int i = 0; i < spielfeld.length; i++) {
            for(int i2 = 0; i2 < spielfeld.length; i2++) {
            	rnd  = r.nextInt(spielfeld.length);
                rnd2 = r.nextInt(spielfeld.length);
                tmp   = spielfeld[i][i];
                spielfeld[i][i] = spielfeld[rnd][rnd2];
                spielfeld[rnd][rnd2] = tmp;
            }
        }
        return spielfeld;
    }

	// Scanner Einlesen
	Scanner sc = new Scanner(System.in);
	public String eingabeString(String text) {
		System.out.println(text);
		return sc.nextLine();
	}	
} //End of Class Aufgabe_8_3

Lösung von: Jan Roth (Santis Training AG)

let puzzle = {
  x: 3, y: 3, // position des loches
  // initialisiere
  init: function() {
    this.field = [
      [ 1,  2,  3,  4],
      [ 5,  6,  7,  8],
      [ 9, 10, 11, 12],
      [13, 14, 15, 'X']
    ];
  },
  swap: function(x, y) {  // ringtausch
    let tmp = this.field[this.x][this.y];
    this.field[this.x][this.y] = this.field[x][y];
    this.field[x][y] = tmp;
  },
  // schiebeVonUnten
  slideN: function() {
    if (this.x != 3) {
      this.swap(this.x + 1, this.y);
      this.x++;
    }
  },
  // schiebeVonRechts
  slideE: function() {
    if (this.y != 0) {
      this.swap(this.x, this.y - 1);
      this.y--;
    }
  },
  // schiebeVonOben
  slideS: function() {
    if (this.x != 0) {
      this.swap(this.x - 1, this.y);
      this.x--;
    }
  },
  // schiebeVonLinks
  slideW: function() {
    if (this.y != 3) {
      this.swap(this.x, this.y + 1);
      this.y++;
    }
  },
  // mischen
  shuffle: function() {
    /* sowas wie der Fisher-Yates-algorithmus hätte sich hier angeboten,
    |  aber jetzt, wo wir das ding schon einmal gebaut haben, lassen wir
    |  es auch ordentlich rattern */
    for (let i = 0; i < 1e6; i++) {
      switch (Math.floor(Math.random() * 4)) {
        case 0: this.slideN(); break;
        case 1: this.slideE(); break;
        case 2: this.slideS(); break;
        case 3: this.slideW(); break;
      }
    }
  },
  // print: ausgabe in der konsole
  plot: function() {
    console.clear();
    console.table(this.field);
  }
}

/* MAIN */
puzzle.init();
puzzle.shuffle();
puzzle.plot();
// spendieren wir dem ganzen noch eine pfeiltasten-steuerung:
document.onkeydown = function(e) {
  switch (e.keyCode) {
    case 37: puzzle.slideW(); break;
    case 38: puzzle.slideN(); break;
    case 39: puzzle.slideE(); break;
    case 40: puzzle.slideS(); break;
  }
  puzzle.plot();
}

Lösung von: Lisa Salander (Heidi-Klum-Gymnasium Bottrop)

// NET 6.x | C# 10.x | VS-2022

var field = new int[4][] {
    new int[] { 01, 02, 03, 04},
    new int[] { 05, 06, 07, 08},
    new int[] { 09, 10, 11, 12},
    new int[] { 13, 14, 15, 00}
};

var xPos = 3;
var yPos = 3;

void Swap(int x, int y) => (field[x][y], field[xPos][yPos]) = (field[xPos][yPos], field[x][y]);

void ShuffleField() {
    var shuffle = Enumerable.Range(0, 16).OrderBy(x => Guid.NewGuid()).ToArray();
    var i = 0;
    for (int x = 0; x < field.GetLength(0); x++)
        for (int y = 0; y < field.Length; y++) {
            var sh = shuffle[i++];
            if (sh == 0) { xPos = x; yPos = y; };
            field[x][y] = sh;
        }
}

void Move(Slide slide) {
    Console.WriteLine($"slide {slide}:");
    switch (slide) {
        case Slide.down: if (xPos != 3) { Swap(xPos + 1, yPos); xPos++; }; break;
        case Slide.up: if (xPos != 0) { Swap(xPos - 1, yPos); xPos--; }; break;
        case Slide.right: if (yPos != 3) { Swap(xPos, yPos + 1); yPos++; }; break;
        default: if (yPos != 0) { Swap(xPos, yPos - 1); yPos--; }; break;
    }
    Print();
}

void Print() {
    for (int x = 0; x < field.GetLength(0); x++) { 
        for (int y = 0; y < field.Length; y++)
            Console.Write($"{field[x][y]:00} ");
        Console.WriteLine();
    }
    Console.WriteLine($"x: {xPos}   y: {yPos}\n");
}

Print();
ShuffleField();
Console.WriteLine("shuffled:");
Print();
Move(Slide.up);
Move(Slide.left);
Move(Slide.right);

enum Slide { up, down, left, right }

Lösung von: Jens Kelm (@JKooP)

Zeit:	2-4
Schwierigkeit:	k.A.
Webcode:	4ksp-tn54
Autor:	Philipp G. Freimann (BBW (Berufsbildungsschule Winterthur) https://www.bbw.ch)

Programmieren lernen

Web-Code:

Fünfzehner-Spiel (Datenstrukturen)

0 Kommentare

4 Lösung(en)

Aktionen

Bewertung

Meta