Gruppentheorie (kleines Spiel)

Computer: Software & Programmierung Programmierung allgemein
#1

Es gibt ein kleines Denkspiel (kein Computerspiel)
Man hat eine Matrix von 3x3 also 9 Felder
Auf 8 von diesen 9 Feldern sind Teile eines Bildes.
Ein einziges Feld ist frei.
Man muss nun probieren durch verschieben der
einzelnen Bildteilen auf das jeweils leere Feld
alle Bildteile in die Richtige Reihenfolge zu bringen
und somit das Bild wieder vollständig zu haben.
Ich denke ihr alle kennt dieses Spiel. Das bekommt man
meistens als Werbegeschenk in Form eines kleinen Plastivierecks nachgeschmissen.

Nun suche ich einen Quellcode oder eine Anleitung
wie ich es mathematisch auf dem kürzesten oder überhaupt
einen Weg finde Das Bild komplett zu bekommen.
Diese Art des Rechnens wird wohl Gruppentheorie genannt.
Wenn ihr nicht wisst was ich meine sagt bescheid.

MfG Roman

#2

Hi,

das Ding hat normalerweise 4x4 Felder, kam Anfang des (20.) Jahrhunderts unter dem Namen Boss-Puzzle raus und soll damals schon ganze B"uros lahmgelegt haben wie sp"ater Rubic’s Cube, Gameboy und Moorhuhnjagd.

Die L"osbarkeit h"angt davon ab, dass die Permutation gerade ist, und ein Hau-drauf-Algorithmus ist, mittels systematischer Vertauschung in 3x2 oder 2x3 Bereichen von oben beginnend die Felder zu ordnen.

Ciao Lutz

#3

Danke
Ich habe mir Heute mal so ein ding ausgeliehen, du hast recht es hat 4x4 Felder, wenn ich dafür was geschrieben hab müsste es ja dann aber auch auf beliebig*beliebig vielen Felder laufen.
Dafür einen FindeKürzestenWeg Algorithmus zu schreiben
geht wohl nahezu in die unmöglichkeit (aber alles geht)
für mich dürfte es heraúsforderung genug sein einen
Quelltext dafür zu verstehen oder sogar selber zu schreiben.
Vielen Dank für die Antwort, ich denke sie wird mir schon
alleine weil ich den Namen des Spieles jetzt weiss sehr weiterhelfen.

MfG Roman

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

#4

hmm, wenn ich richtig aufgepasst habe, ist das ein Problem, welches in NP liegt, Probleme, die man nur nicht-deterministisch löseb kann. Und da wirst du wahrscheinlich keinen Algorithmus finden, der dir den kürzesten Weg bei *beliebig* vielen Feldern angibt.

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

#5

hmm, wenn ich richtig aufgepasst habe, ist das ein Problem,
welches in NP liegt, Probleme, die man nur
nicht-deterministisch löseb kann. Und da wirst du
wahrscheinlich keinen Algorithmus finden, der dir den
kürzesten Weg bei *beliebig* vielen Feldern angibt.

Jepp, du liegst richtig, ich hab gar keinen gefunden.
Naja ist auch nicht so wichtig.
Danke euch nochmal