Backtracking Problem Box Filler

[Max246Sch]

Hallo!
Folgende Aufgabe:
Dirk hat zum Geburtstag ein kniffliges Rätsel geschenkt bekommen. Das Rätsel besteht aus einer würfelförmigen Kiste mit einer inneren Kantenlänge von 5 cm und einer Menge von Würfeln und weiteren Quadern. Darunter ist ein goldener Würfel mit Kantenlänge 1 cm. Die Würfel und Quader sollen im Inneren der Kiste so platziert werden, dass sie diese komplett füllen. Dabei muss der goldene Würfel genau in der Mitte platziert werden. Zur Verfügung stehen neben dem goldenen Würfel weitere vier Würfel der Kantenlänge 1 cm, sechs Quader mit den Maßen 1 cm × 2 cm × 4 cm und noch einmal sechs Quader mit den Kantenlängen 2 cm × 2 cm × 3cm.

Es gibt keine Ausgabe. Sieht wer den Fehler?

public enum Main {
;

public static void main(final String[] args) {
final int boxsize = 3;
final int anzahlshapes = 6;
final int rotation = 1;

final String[][][] box = new String[boxsize][boxsize][boxsize]; // 3D-Array für die Box

box[boxsize / 2][boxsize / 2][boxsize / 2] = "G";

final Form[] formes = new Form[anzahlshapes];

formes[0] = new Form(1, 3, 3);
formes[1] = new Form(1, 3, 3);
formes[2] = new Form(1, 1, 3);
formes[3] = new Form(1, 1, 2);
formes[4] = new Form(1, 1, 2);
formes[5] = new Form(1, 1, 1);

Main.solve(box, formes, 0);


}

public static void solve(final String[][][] box, final Form[] formes, final int currentIndex) {
// Basisfall: Wenn alle Formen platziert wurden, drucken Sie die Lösung oder tun Sie etwas damit
if (boxisfull(box)) {
Main.print(box);
return;
}

// Versuchen Sie, die aktuelle Form an verschiedenen Positionen und Rotationen zu platzieren
for (int x = 0; x < box.length; x++) {
for (int y = 0; y < box[0].length; y++) {
for (int z = 0; z < box[0][0].length; z++) {
for (int rotation = 1; rotation <= 6; rotation++) {
if (formes[currentIndex].canbeplaced(x, y, z, box)) {
formes[currentIndex].place(x, y, z, box, currentIndex + 1);
solve(box, formes, currentIndex + 1);
formes[currentIndex].remove(x, y, z, box);
}
}
}
}
}
}


private static void print(final String[][][] box) {

for (int z = 0; z < box[0][0].length; z++) {
for (int y = 0; y < box[0].length; y++) {
for (int x = 0; x < box.length; x++) {
System.out.print(box[x][y][z] + "\t");
}
System.out.println();
}
System.out.println();
}
System.out.println("----------");
}



public static boolean boxisfull(String[][][] box) {

for (int x = 0; x < box.length; x++) {
for (int y = 0; y < box[0].length; y++) {
for (int z = 0; z < box[0][0].length; z++) {
if (box[x][y][z] == null) {
return false; // Es gibt mindestens eine leere Stelle
}
}
}
}
return true;
}
}

class Form {

int xpos, ypos, zpos;
int xlength, ylength, zlength;
int ix, iy, iz;
char type;
int rotation = 1;

public Form(final int xlength, final int ylength, final int zlength) {
this.xlength = xlength;
this.ylength = ylength;
this.zlength = zlength;
ix = xlength;
iy = ylength;
iz = zlength;

if (xlength == ylength && ylength == zlength)
type = 'w';
else
type = 'q';
}



public void place(final int x, final int y, final int z, final String[][][] box, final int index) {
// Platzieren Sie die Form basierend auf den aktuellen Abmessungen
for (int i = 0; i < this.xlength; i++) {
for (int j = 0; j < this.ylength; j++) {
for (int k = 0; k < this.zlength; k++) {
// box[x + i][y + j][z + k] = Integer.toString(index);
box[x + i][y + j][z + k] = Integer.toString(index);
}
}
}
}

public void remove(final int x, final int y, final int z, final String[][][] box) {
for (int i = 0; i < this.xlength; i++) {
for (int j = 0; j < this.ylength; j++) {
for (int k = 0; k < this.zlength; k++) {
box[x + i][y + j][z + k] = null;
}
}
}
}

public void rotate() {
if (7 > this.rotation && 0 < this.rotation) {
switch (rotation) {
case 1:
xlength = this.ix;
ylength = this.iy;
zlength = this.iz;
break;
case 2:
xlength = this.iy;
ylength = this.iz;
zlength = this.ix;
break;
case 3:
xlength = this.iz;
ylength = this.ix;
zlength = this.iy;
break;
case 4:
xlength = this.ix;
ylength = this.iz;
zlength = this.iy;
break;
case 5:
xlength = this.iy;
ylength = this.ix;
zlength = this.iz;
break;
case 6:
xlength = this.iz;
ylength = this.iy;
zlength = this.ix;
break;
}
rotation++;
} else {
rotation = 1; // Zurücksetzen auf den Anfang, wenn rotation 6 erreicht.
this.rotate();
}
}

public boolean canbeplaced(final int x, final int y, final int z, final String[][][] box) {
for (int i = 0; i < this.xlength; i++) {
if (i + x >= box.length) {
return false;
}

for (int j = 0; j < this.ylength; j++) {
if (j + y >= box[0].length) {
return false;
}

for (int k = 0; k < this.zlength; k++) {
if (z + k >= box[0][0].length || null != box[x + i][y + j][z + k]) {
return false;
}
}
}
}
return true;
}
}

 

[Barista]

Ich habe nur grob auf den Code geschaut (wegen der nicht vorhandenen Formatierung in Code-Tags).

Mir fällt auf, dass es keinen Stack gibt(explizit als Objekt oder implizit durch rekursiven Unterprogrammaufruf).

Vielleicht habe ich den auch übersehen.

Ich würde die Box und den vorhandenen Vorrat an Quadern immutable machen, dann sind die vorherigen Werte beim Zurückfallen (backtracking) einfach wieder da.

Änderungsoperationen erzeugen dann eine Kopie (fast, natürlich mit den gewünschten Änderungen).

 

[mihe7]

Es gibt keine Ausgabe. Sieht wer den Fehler?

Was hältst Du davon, die Form zu rotieren? Abgesehen davon, ist canbeplaced falsch: wenn Du eine Box mit der Ausdehnung x in einer Achse hast, dann passt bzgl. dieser Achse natürlich auch eine Form mit einer Ausdehnung von x rein.

 

[Marinek]

Ich hab bestimmt was wegen der Richtungen/Ausdehnungen falsch...^^

In wie viele Richtungen kann man einen Karton der Form 1x2x4 denn eigentlich drehen? Hab in Geometrie nicht aufgepasst. 😅

Man hat dir schon mehrfach nahegelegt etwas mehr zu überlegen, bevor man was postet.

Siehe hier: https://forum.byte-welt.net/t/deeskalationsfrage/25035/9

Hilft dem TO null.

 

[mihe7]

Btw... Warum wurde der Code des Eingangsposting immer noch nicht formatiert? Das ist eine Zumutung.

Hast Du es den Mods gemeldet? Wenn ja, werden die halt noch nicht dazugekommen sein.

 

[KonradN]

Das erwarte ich vom TE, nicht von den Mods. Andernfalls sollte diese Frage gelöscht werden.

Der TE kann seinen Beitrag nur 30 Minuten lang editieren und da ihm niemand gesagt hat, wie es richtig geht, wird er vermutlich es auch nicht können.

 

[httpdigest]

Jo, stattdessen schreibt er die exakt selbe Aufgabe mit exakt derselben Formatierung nochmal: https://www.java-forum.org/thema/3d-box-filler-backtracking.203272/