Diskussion:15-Puzzle

Dieser Artikel war am 17. November 2008 der Artikel des Tages.

Erfinder

Unter diesem Link wird Noyes Chapman als Erfinder genannt.(Der vorstehende, nicht signierte Beitrag stammt von 84.165.93.95 (Diskussion • Beiträge) 22:26, 15. Dez. 2006 (CET))

Unlösbare Aufgabenstellung

Der Abschnitt ==Aufgabenstellung== ist verwirrend. Er erweckt den Eindruck, als ob die Aufgabe unlösbar wäre; zumal die Bilder wohl vertauscht sind. --Ohauahauaha 07:18, 22. Apr. 2008 (CEST)

Das ist richtig. Das ursprüngliche 15-Puzzle ist unlösbar. Ich werde den Artikel aber umordnen, da ohne „Geschichte“ wohl die ursprüngliche Aufgabenstellung mit heutigen Spielen nicht ganz offensichtlich ist. --micha Frage/Antwort 07:44, 22. Apr. 2008 (CEST)

Irgendwie erachte ich mich nicht als dumm, aber aufgrund des Artikels (Stand heute) kann ich nicht erkennen, was an der ursprünglichen Aufgabenstellung denn so unmöglich sein soll, da die beiden Bilder des Abschnittes identisch sind. Somit sind Ausgangs- und Zielanordung identisch und damit lösbar. Kann mich hier jemand aufklären...? --84.227.3.242 00:30, 17. Nov. 2008 (CET)

In der ursprünglichen Aufgabenstellung (oberes Bild) sind die 14 und die 15 vertauscht. Die sollen in die richtige Reihenfolge (unteres Bild) gebracht werden, was unmöglich ist. --Lukas Grossmann 09:18, 17. Nov. 2008 (CET)

Versucht man das unlösbare Puzzle durch Schieben zu lösen, so baut man sich die oberen beiden Zeilen, sowie die linken beiden Spalten erst ein mal auf. Dann kommt (und erkennt die Unlösbarkeit) man zu dieser unlösbaren Stellung: 01-02-03-04|05-06-07-08|09-10-12-11|13-14-15-.. und nicht der, wo 14 & 15 vertauscht sind. Vielleicht könnte man da Bilder & Text anpassen. BTW: Interessanterweise lässt sich mit Hilfe des unlösbaren Puzzles ein pandiagonal magisches Quadrat schieben: ..-13-10-07|11-06-01-12|05-08-15-02|14-03-04-09 --79.199.68.71 15:33, 8. Jan. 2009 (CET)

Nachtrag: Es lässt sich lösen, indem man das Leerfeld links oben (quasi als "0")platziert und dann von da durchzählt. --79.199.68.71 15:42, 8. Jan. 2009 (CET)

Lesenswert?

Hallo. Ich bin über die Auskunft zufällig hier gelandet, hätte nie gedacht, dass man über ein einfaches Schiebepuzzle soviel schreiben kann, und finde den Artikel klasse. Meiner Meinung nach ein Paradebeispiel dafür, dass auch relativ kurze Artikel die Kriterien eines Lesenswerten erfüllen können. Vor allem hat's mir angetan, dass die Beweisskizze so laientauglich wie möglich geschrieben ist und der gute Einsatz der Bilder das ganze nochmal veranschaulicht. Die Geschichte ist nicht lang, aber ausreichend geschrieben, in der Einleitung steht imho genau das, was reinsoll, und Belege sind auch da, wo sie nötig sind.
Kurz und gut: Ich würde den Artikel gerne als Lesenswerten nominieren. Da ich aber zumn Punkt "Inhaltliche Vollständigkeit" nur sagen kann, dass der Artikel für mich dieses Kriterium zu erfüllen scheint, würden mich vorher die Meinungen der Autoren und Diskutanten dazu interessieren, nicht dass ich den nominiere, und zig Contras kommen wegen irgendwas, das mir als "Mathelaien" nicht auffällt. LG, ArtWorker 16:05, 5. Okt. 2008 (CEST)

Ich habe nichts dagegen. --Micha 16:06, 5. Okt. 2008 (CEST)

Das ging ja fix... Ok, da der Großteil der jüngeren großen Ergänzungen von Dir und Zarek stammt, und letzterer außer dem (sehr guten!) Beweis-Edit hier seit Oktober nicht mehr tätig war, werte ich das mal als Zustimmung der Hauptautoren und nominiere einfach mal ;-) LG, ArtWorker 16:34, 5. Okt. 2008 (CEST)

Erfolgreiche Lesenswert-Kandidatur vom 5. bis zum 12. Oktober 2008

Das 15-Puzzle (auch 14-15-Puzzle genannt) ist ein unlösbares Geduldsspiel, welches zwischen 1870 und 1880 in den Vereinigten Staaten entstanden ist und von einem Postangestellten mit Namen Noyes Palmer Chapman erfunden wurde. Heutige Ausgaben sind abgewandelte Formen des ursprünglichen Spiels und beschränken sich auf die Aufgabe, die Steine richtig zu sortieren.

Ein Paradebeispiel dafür, dass auch recht kurze Artikel die Kriterien eines Lesenswerten erfüllen können. Die Einleitung gibt den nötigen Überblick in der erwünschten Kürze, die Geschichte ist ausreichend auf den Punkt gebracht, insgesamt wirkt der Artikel vollständig. Hervorzuheben ist die äußerst laienverständliche Skizze des Beweises und der sinnvolle Einsatz von Bildern abseits von bloßem Beiwerk. Belege sind immer dort, wo sie nötig sind. Kurz und gut: Ein Artikel, der m.E. die Lesenswert-Auszeichung verdient hat. LG, ArtWorker 16:47, 5. Okt. 2008 (CEST)... Nachtrag: Als nicht am Artikel beteiligter natürlich  Pro ArtWorker

Hab mir den eben durchgelesen und find den ganz in Ordnung. Ich würde das Buch, das in den Einzelnachweisen genannt ist, gerne noch in einem Literaturabschnitt sehen, einfach um darzustellen, dass dieses Werk auch als Grundlage gedient hat. Außerdem steig ich durch einen Satz nicht ganz durch. Zum einen, dachte ich verstanden zu haben, dass das Puzzle nicht lösbar ist, also die gewünschte Darstellung der Steine nicht erreicht werden kann. Ich erfahre, dass höchtens die Hälfte aller denkbaren Konstellationen aus der Grundkonstellation heraus erreicht werden können. Allerdings steht direkt dahinter, dass in der Tat auch alle erreichbar sind, was aber durch den hier vorgestellten Beweis nicht nachgewiesen werden kann. Was stimmt denn jetzt? Geht das doch nur durch den Beweis im Text kann man es nicht beweisen, wie sähe dann ein Beweis aus, mit dem man das könnte? Oder geht das doch nicht und ich hab irgendwas nicht verstanden? Gruß--Ticketautomat 19:42, 5. Okt. 2008 (CEST)

So wie ich's verstehe, kann nach dem, was im Artikel steht, höchstens die Hälfte erreicht werden. Der "lässt sich hier nicht beweisen"- Teil bezieht sich meinem Verständnis nach eindeutig auf die Zusatzinformation, dass genau die Hälfte erreicht wird. Das kann aber gerne noch jemand umformulieren, falls mein Sprachverständnis da zu einem falschen Schluss führt. LG, ArtWorker 20:36, 5. Okt. 2008 (CEST)

Dem Autoren hatteste ja auf der Disk wegen der Kandidatur informiert, vielleicht beobachtet der die auch und spendiert uns ein paar Erklärungen.--Ticketautomat 14:39, 6. Okt. 2008 (CEST)

Entschuldigt, dass ich die Gepflogenheiten hier noch nicht so gut kenne, das mit der Disk habe ich nicht verstanden... steht das für Scheibe oder Diskussion? Na, egal, im Artikel ist es genauso gemeint, wie ArtWorker es verstanden hat: jeweils die Hälfte aller Konstellationen kann unter Garantie NICHT erreicht werden, das wird durch die hier veröffentlichten Erklärungen bewiesen, deshalb ist das Puzzle nicht lösbar. Ob die Konstellationen, die innerhalb der erreichbaren Hälfte liegen, tatsächlich erreicht werden können, darüber sagt dieser Beweis nichts aus. Um das zu ermitteln (und dann zu beweisen), braucht man eine Methode, die leider umständlicher ist; vielleicht schreibe ich auch 'mal darüber, das wird aber wohl in einem anderen Artikel sein, da das mit der ursprünglichen Problemstellung - ist das Puzzle lösbar, und wenn nein, warum nicht? - nichts zu tun hat. Gruß, --Zarek 22:50, 7. Okt. 2008 (CEST)

Hallo Zarek. Erstmal ist's an mir, um Entschuldigung zu bitten, dass ich Dich nicht über diese Kandidatur informiert habe, ich dachte, Du wärst nichtmehr aktiv, weil Du außer der einen Einfügung nichts gemacht hast. "Disk" bezieht sich auf die Artikeldiskussionsseite, wo ich kurz angefragt hatte, bevor ich den Artikel hier einstellte. Dann zur Sache: Ich habe den von Ticketautomat bemängelten Satz jetzt - wo Du mein Verständnis bestätigt hast - ein klein wenig umformuliert, dass er sich stärker auf die Hälfte bezieht. Damit dürfte das Problem erledigt sein. Mit dem ausführlichen Beweis hast Du Recht, der muss nicht in diesen Artikel, gerade dass die Beweisskizze so schön anschaulich und knapp gehalten ist, macht den Artikel ja (meiner Meinung nach) so lesenswert. LG, ArtWorker 11:28, 9. Okt. 2008 (CEST)

•  Pro Für mich ein klassischer Lesenswerter. Kriterien sehe ich erfüllt. Schöner Artikel. --norro 10:53, 9. Okt. 2008 (CEST)
• vorläufig mal  Pro, obwohl noch einiges getan werden kann (und ich am Wochenende wohl auch vornehmen werde). --Micha 14:31, 9. Okt. 2008 (CEST)
•  Pro Der Artikel ist gut illustriert und die Länge trägt der Unwichtigkeit dieses Themas Rechnung. Dennoch wird für Mathe- und Puzzlefreaks ein nicht verbreitet bekannter Sachverhalt mitgeteilt und verständlich bewiesen. Der Leser ist nicht dümmer geworden und wurde nicht gelangweilt. Deswegen lesenswert.--Hgn-p 21:21, 9. Okt. 2008 (CEST)
• wunderbar verständlich für mathelaien.  Pro --dvdb 01:41, 10. Okt. 2008 (CEST)
•  Pro Ich gebe dem Artikel auch gerne ein Pro, habe aber noch einen Verbesserungsvorschlag: In der Einleitung wird das Puzzle als unlösbar bezeichnet. Das führte bei mir zu Verwirrung, vor allem da das Bild daneben ein offensichtlich lösbares Puzzle zeigt. Auch da heutzutage nur die lösbaren Varianten in Umlauf sind, würde ich den Begriff dort entweder weglassen oder die Unterscheidung lösbar↔unlösbar gleich in der Einleitung definieren. Man muss sonst eine ganze Weile warten bis das klar wird. -- Dr. Schorsch*?*! 13:32, 10. Okt. 2008 (CEST)
•  Kontra - Ich finde den Artikel eigentlich sehr hübsch und interessant, allerdings habe ich ein grundsätzliches Problem: Meiner Meinung nach steht die ursprüngliche Aufgabenstellung und der Beweis der Unlösbarkeit dieser viel zu sehr im Vordergrund, schon in der Einleitung. Auch sollte man in der Einleitung das Spiel noch grob erklären, also dass es ein freies Feld gibt und die Steine nur verschoben und nicht herausgenommen werden können. Ich würde einen wesentlich größeren Schwerpunkt auf die heutige Spielart legen, auch eine Lösungsstrategie für diese wäre nicht schlecht (z.B. wie hier). Was mir sonst noch aufgefallen ist:

Das Spiel wurde vom Postangestellten Noyes Palmer Chapman erfunden, der seinen Freunden im Jahr 1874 ein ähnliches Puzzle zeigte. Bei diesem ging es darum, sechzehn nummerierte Blöcke in die Form eines magischen Quadrates zu bringen. Die ersten Kopien des 15-Puzzles machten den Weg nach Syracuse...

Hier ist mir nich klar, was das Magische Quadrat mit dem 14-15 Puzzle zu tun hat. Vielleicht wird hier auch zu wenig über dieses "Vorläuferspiel" erklärt, so dass ich den Zusammenhang nicht verstehe.

--Cactus26 15:05, 11. Okt. 2008 (CEST)

Die Literaturangaben sind unvollständig. In dem deutschsprachigen Buch von Bruno Kerst über mathematische Spiele von 1933 (Reprint bei Sändig 1968) werden die Lösbarkeits- bzw. Unlösbarkeitskriterien durch Betrachtung eines zum Spiel äquivalenten Graphen abgeleitet (habe das Buch mal in grauer Vorzeit gelesen).--Claude J 16:00, 11. Okt. 2008 (CEST)

Der Artikel ist mit 6 Pro- und 1 Contra-Stimme seit dieser Version lesenswert. --ADK _Probleme? ^{Bewerte mich!} 08:24, 12. Okt. 2008 (CEST)

Geschichte

Im Abschnitt "Geschichte" sind mir zwei Punkte aufgefallen, vielleicht schaut sichs mal jemand an... 1. Bei diesem ging es darum, sechzehn nummerierte Blöcke in die Form eines magischen Quadrates zu bringen. Müssten es nicht fünfzehn Blöcke (und ein freies Feld) sein? Oder war das ursprüngliche Spiel anders aufgebaut? 2. Weiter unten wird von einem Megatrend gesprochen. Bei "Megatrend" denke ich eher an Globalisierung, demographischen Wandel und ähnliches - und nicht unbedingt an ein und nicht unbedingt an den schnellen Siegeszug eines Geduldsspiels. Megatrends grenzen sich von (einfachen) Trends gerade dadurch ab, dass sie sich über Jahrzehnte erstrecken. Was ja dem folgenden Satz entnehmbar auf das 15-Puzzle nicht direkt zutraf. Oder um es mit Bruno Labbadia zu sagen: "Das wird doch alles von den Medien hochsterilisiert." ;o) --Nihil Baxter 00:49, 17. Nov. 2008 (CET)

Wie es genau funktionierte, ist mir nicht bekannt. Jedenfalls muss es sich um 16 Felder gehandelt haben, da sonst ein magisches Quadrat nicht möglich ist. Zum Gebrauch des Wortes „Megatrends“ gibt es vermutlich mehrere Konnotationen. --Micha 08:41, 17. Nov. 2008 (CET)

Verschiedene Beweisideen?

Die Beweise mit der Parität und dem Signum der Permutation sind IMHO im Kern das gleiche in verschiedener mathematischer Formulierung, weshalb ich den Vorschlag in den Raum stelle, den Ausdruck "eine andere Beweisidee" durch "ein anders formulierter Beweis" zu ersetzen. --KnightMove 14:51, 17. Nov. 2008 (CET)

wenn vs. genau dann wenn

Da die Änderung beim letzten Mal zurückgesetzt wurde, diesmal mit Erleuterung:

Aus dem Artikel (15-Puzzle#Allgemeine Überlegungen):

Des Weiteren zeigen diese Überlegungen, dass genau die Hälfte aller denkbaren Konstellationen aus der Grundkonstellation heraus erreicht werden kann, weil nur Konstellationen von geraden in geraden oder ungeraden in ungeraden Paritäten überführt werden können.

Diese Folgerung stimmt so nicht. Es könnte zum Beispiel unter den genannten Voraussetzungen sein, dass es vier nicht ineinander überführbare Konfigurationen gibt, so dass von jeder ein Viertel des Suchraums erreichbar ist. Dass dies in der Realität nicht möglich ist, wird später erklärt, ist für die obige Aussage nicht relevant. Daher die Änderung in die folgende, korrekte Schlussfolgerung:

Des Weiteren zeigen diese Überlegungen, dass höchstens die Hälfte aller denkbaren Konstellationen aus der Grundkonstellation heraus erreicht werden kann, weil nur Konstellationen von geraden in geraden oder ungeraden in ungeraden Paritäten überführt werden können.

--Matzu 16:40, 17. Nov. 2008 (CET)

Ok, es ist aber beweisbar, dass alle geraden in gerade Paritäten überführbar sind und alle ungeraden ind ungerade. Vielleicht müssen wir diesen Beweis ja auch noch aufführen ;-). Aber insofern hast du natürlich Recht. Der Beweis sagt noch nicht aus, dass alle gerade in gerade überführt werden, sondern nur, dass gerade nicht in ungerade und umgekehrt überführt werden können. --Micha 17:17, 17. Nov. 2008 (CET)

Über diesen Punkt ging es schon mehrfach hin und her... falls immer noch nicht alle zufrieden sind, könnte man das Ganze auch ex negativo formulieren (die Hälfte der Konstellationen kann nicht usw.) - schließlich ging es ursprünglich ja um den Beweis der Unlösbarkeit ;-) --Zarek 21:51, 17. Nov. 2008 (CET)

Alternativer Text zu den Bildern

wäre nett, wenn den jemand hinzufügen könnte. (nicht signierter Beitrag von 84.44.178.50 (Diskussion) 18:11, 17. Nov. 2008 (CET))

Erledigt... --Micha 18:11, 17. Nov. 2008 (CET)

Mein Revert

Ich fand diese Einfügung keine Verbesserung, denn da ist schon ein Beweisteil (der imho besser ist, weil mit generelller Argumentation), da das Neue auch sehr nach eigenen Überlegungen klang, keine Quellen hatte und einfach redundant war, hab es wieder entfernt. Einwände? --χario 17:16, 11. Jun. 2009 (CEST)

Unterscheidung

Im Artikel sollte genauer zwischen dem 15-Puzzle von Chapman (zufällige Platzierung der Zahlen, 50 % der Fälle lösbar) und dem 14-15-Puzzle von Loyd (aufsteigende Platzierung der Zahlen mit 14 und 15 vertauscht, unlösbar) unterschieden werden. Viele Grüße, --Quartl (Diskussion) 07:20, 15. Okt. 2013 (CEST)

Ich schließe mich an. Insbesondere verstehe ich nicht, warum diese eine (historisch begründete) Ausgangsstellung unter den vielen Milliarden möglicher Start-Stellungen so hervorgehoben wird. Wenn man diesen Artikel liest, könnte man meinen, nur ein 15-Puzzle in dieser einen bestimmten Ausgangsstellung wäre das 15-Puzzle. Erst im Abschnitt "Heutige Spiele" wird die allgemeine Version "Bringe es wieder in die richtige Reihenfolge" kurz erwähnt.

Kann jemand bitte mit Quelle belegen, dass die unlösbare Variante von Loyd tatsächlich das "ursprüngliche" 15-Puzzle war und dass heutige Ausgaben (...) abgewandelte Formen des ursprünglichen Spiels mit geänderter Anfangsanordnung [sind], durch die sie lösbar sind. [So steht es im Artikel!] Ist das wirklich belegt durch Slocum & Sonneveld? Bei den meisten Spielen heute kann man die Puzzleteile (mit etwas Gewalt) herausnehmen und in einer beliebigen Stellung wieder einsetzen. Mich würde es wundern, wenn das damals nicht auch schon so war. (Wenn das Spiel damals aus Holz gefertigt wurde, lagen die Teil womöglich sogar mehr oder weniger lose im Rahmen.) Ich vermute daher, dass Loyd nur eine bestimmte Aufgabe für das Puzzle als Rätsel definierte.

Spricht nicht folgendes für meine Vermutung?

• Loyd kam - wenn der englische Wikpedia-Artikel die Historie korrekt wiedergibt - erst später auf das Spiel, seine erste Veröffentlichung stammt aus 1886. Die eigentlich "ursprüngliche" Version ist dann die von Chapman (spätestens 1879). Bloß: wie genau sah die aus???
• «When it appeared in 1879 as The Gem Puzzle, the 15 Puzzle was accompanied by a cryptic instruction: Place the blocks in the box irregularly, then move until in regular order.» [Quelle: Cut the Knot]
• «This puzzle consisted of 15 numbered square pieces that could be slided around in a square box that was big enough to contain 16 pieces. The pieces should be placed at random in the box and you should sort the pieces in ascending order without taking the pieces out of the box (so the only thing that is allowed is to slide the pieces).» [Quelle: The history of the 15 puzzle]

Gruß Welt-der-Form (Diskussion) 01:02, 18. Okt. 2013 (CEST)

Dazu müsste man bei im Zweifelsfall bei Slocum nachschlagen, denn er ist derjenige der tatsächlich die historischen Hintergründe und Originaldokumente genau recherchiert hat und bei dem letztlich die meisten neueren (Online-)Quellen (wie cut-the-knot) abgeschrieben haben. Die erste mathematische Publikation zum dem Puzzle ist übrigens auch schon 1879 erschienene (Johnson & Story: Notes on the 15-puzzle, American Journal of Mathematics). Aus der dortigen Beschreibung folgt eigentlich wie bei cut-the-knot das es keine feste ursprüngliche Ausgangsstellung gibt, sondern dass es ein Puzzle war dessen Ausgangsstellung man selbst zusammensetzte. Die unlösbare 14-15 Variante wird dort (noch) nicht (gesondert) erwähnt. Ansonsten stimme ich den dir bzw. Quartl zu, dass der Artikel beide Varianten klar unterscheiden sollte, vor allem kann man nicht von "dem" 15-Puzzle in Bezug auf eine bestimmte Ausgangstellung reden, stattdessen besitzt es 16! Ausgangstellungen.--Kmhkmh (Diskussion) 01:36, 18. Okt. 2013 (CEST)

Das Buch von Slocum und Sonneveld habe ich zwar nicht zur Hand, aber man findet hier eine Zusammenfassung zur Rolle von Loyd. Einen Teil der Geschichte findet man online auch im zweiten Kapitel des Buchs Sliding Piece Puzzles von Edward Hordern (1986). Man muss einerseits zwischen dem physikalischen 15-Puzzle und dem logischen 14-15-Puzzle unterscheiden (vergleiche Schachspiel und Schachaufgabe). Letzteres stammt offenbar noch nicht mal von Loyd, auch wenn er später zur weiteren Popularisierung begetragen hat. Viele Grüße, --Quartl (Diskussion) 08:48, 18. Okt. 2013 (CEST)

Die Analogie von Schach und Schachaufgabe beschreibt es zwar einerseits treffend, aber anderseits nicht ganz. Zum einen spricht die von dir genannte Quelle selbst von zwei unterschiedlichen Puzzle, nämlich den 15- und den 14-15 Puzzle (auf S. 25-26 wird das 14-15-Puzzle dort üpbrigens dich Lloyd zugeschrieben) zum Anderen spiegelt sich in der physischen Produktionen wieder. In den frühen 15-Puzzle hat man im Prinzip einen Holzrahmen, indem man Holzplättchen platziert und dann verschiebt, aus dieser Sicht ist dann das 14-15-Puzzle eine von 16! Puzzle-Aufgaben, die man mit dem 15-Puzzle bilden kann. Allerdings kommen später 14-15-Puzzle auf den Markt, bei denen die Zahlenplättchen miteinander verzahnt sind und nicht mehr beliebig zusammengesetzt werden können. Man damit einen physisches Puzzle mit dem nur die 14-15-Variante gespielt werden kann.--Kmhkmh (Diskussion) 12:26, 18. Okt. 2013 (CEST)

Ja, die Schach-Analogie war auf die historische Entwicklung im 19. Jhdt. bezogen (wobei ich jetzt nicht sagen kann, wann das erste physikalisch nicht auftrennbare 14-15-Puzzle auf den Markt kam). Die Zuschreibung des 14-15-Puzzles an Loyd ist heute so nicht mehr haltbar, siehe die erste Quelle (das Slocum-Buch), daher habe ich sie im Artikel wieder relativiert. Viele Grüße, --Quartl (Diskussion) 13:27, 18. Okt. 2013 (CEST)

Lösungs-Algorithmen

Werden nur ganz kurz erwähnt (zum Beispiel Parberry).--Claude J (Diskussion) 09:28, 15. Okt. 2013 (CEST)

Das ist insgesamt ein sehr aufwändiges Thema. Hier gibt es - ähnlich wie beim Zauberwürfel - Unterschiede zwischen systematischen ("gehirnfreundlichen") Methoden und Computermethoden, welche einfach alle Möglichkeiten ausprobieren. ÅñŧóñŜûŝî (Ð) 14:16, 15. Okt. 2013 (CEST)

Hallo Claude, der Link auf die Seite Fifteen Puzzle Optimal Solver von Herbert Kociemba ist aber dabei. Dort finden sich etliche Infos zur mathematischen Analyse. @Antonsusi: einfach ausprobieren? "Einfach" geht leider nicht wirklich, da die Anzahl der Möglichkeitenzu zu schnell wächst. Es braucht in jedem Fall Gehirnschmalz. Und in jedem Fall auch Systematik...  ;-) Welt-der-Form (Diskussion) 13:45, 16. Okt. 2013 (CEST)

Ein typischer (Standard-)Algorithmus für das 15-Puzzle ist der A*-Algorithmus mit Manhattan oder Hamming-Abstand als Heuristik. Sedgwicks Algorithmen-Vorlesung in Princeton hat das 15-Puzzle übrigens als Hausaufgabe (siehe dazu [1], [2]). Kociemba scheint eine verbesserte Version der "Standardvariante" (u.a. IDA* statt A*) implementiert zu haben.--Kmhkmh (Diskussion) 15:49, 16. Okt. 2013 (CEST)

"Begrüßungsbild" (ganz oben)

Antonsusi hat am 19. Oktober 2013 das Bild eines 15-Puzzles in Ausgangsstellung (ganz oben rechts) eingetauscht gegen ein ungeordnetes ([3]). Ich finde:

• Wenn der Leser den Artikel öffnet, muss ich erst einmal das wiederfinden, was er bereits kennt: das 15-Puzzle in geordneter Ausgangsstellung, z.B. [4]. Ein Puzzle in geordneter Ausgangsstellung hat dabei einen höheren Wiedererkennungswert. Dann weiß er: das ist der Artikel, den ich suche.
• Zu Beginn ist es zudem m.E. wichtiger, das Ziel des Spiels zu veranschaulichen als irgendeine beliebige der 10.461.394.944.000 Ausgangsstellungen.

Welt-der-Form (Diskussion) 09:57, 19. Okt. 2013 (CEST)

Strukturierung des Artikels - Formulierung der Überschriften

Antonsusi hat am 19. Oktober 2013 die neue Struktur, insbesondere die Überschrift Die Aufgabenstellung „Mische und bringe wieder in die richtige Reihenfolge“ und ihre Varianten wieder rückgängig gemacht. Die Überschrift lautet nun nur noch (so wie zuvor) schlicht Andere Aufgabenstellungen (mit den Unterabschnitten 'Andere Zahlenaufgaben', 'Text-Versionen', 'Bilder' und 'Ausführungsformen'. Ich finde:

• Die vielen Unterüberschriften sind eine Überbetonung von kleinen Details.
• Das Große geht verloren: Es gibt lösbare (die geraden Permutationen) und unlösbare (die ungeraden Permutationen) Puzzle. Das Kapitel 'Geschichte' führt das 'Gem Puzzle' ein, das lösbare und unlösbare Anfangsstellungen erlaubt. Das Kapitel 'Aufgabenstellung beim 14-15-Puzzle' beschäftigt sich mit den unlösbaren Fall. Das Kapitel 'Die Aufgabenstellung „Mische und bringe wieder in die richtige Reihenfolge“ und ihre Varianten' beschäftigt sich mit den lösbaren Fällen. Das Kapitel 'Zur Theorie des 15-Puzzles' nimmt den Bogen vom Anfang wieder auf und erklärt, was das für den Spieler Verstörende am „Gem Puzzle“ war: nämlich, dass es manchmal lösbar, manchmal nicht lösbar war.
• Die Überschrift 'Die Aufgabenstellung „Mische und bringe wieder in die richtige Reihenfolge“ und ihre Varianten' erklärt, was das Gemeinsame der vielen Varianten ist. Dieser Hintergrund geht bei der von Antonsusi bevorzugten Überschrift 'Andere Aufgabenstellungen' verloren. Es muss einen einleitenden Text geben, der das Gemeinsame erklärt.
• Unter den "Varianten" sollte die mit Zahlen die erste sein, denn sie knüpft an die bisherigen Ausführungen im Artikel an. Die Varianten 'Bild-Puzzle', 'Text-Puzzle' und 'magisches Quadrat' würde ich daher erst weiter unten erwähnen.

Daher Revert. Welt-der-Form (Diskussion) 10:25, 19. Okt. 2013 (CEST)

Der ganze Artikel ist, weder in deiner und - zugegeben - auch in meiner Version gut strukturiert. Es wäre ganz gut, wenn wir erst mal klären, wie er aussehen soll. Es gibt folgende Sachverhalte:

• Versionen: Zahlen, Buchstaben, Bilder
• Bauformen: Material und die wichtige Frage: "Steine entfernbar oder nicht?"
• Bei Zahlen: Aufgabenstellungen, Lösbarkeit und die Mathematik dahinter.
• Sonstiges: "Schlüsselanhänger", Erwähnung anderer Größen (3x3 etc.)

Abhängigkeiten:

• "Steine entfernbar oder nicht?" hat Auswirkungen auf die Lösbarkeit, auch bei Text. Damit also auch auf die Mathematik.

Deshalb schlage ich folgende Reihenfolge vor:

1. Das Spiel wird allgemein erklärt und die drei Versionen werden erwähnt.
2. "Steine entfernbar oder nicht?" wird erwähnt mit dem Hinweis, dass bei nicht entfernbaren Steinen nur die Hälfte aller Positionen erreichbar ist, insbesondere nicht die Vertauschung nur der beiden letzten Steine.
3. Etwaiger Buchstabentausch bei Text (damit das Thema abgeschlossen ist.)
4. Zahlenversion mit Mathematik. Das ist der größte Teil und geht ins Detail. Das sollte daher nicht so weit nach vorne kommen.
5. Sonstiges
6. Geschichte

ÅñŧóñŜûŝî (Ð) 15:51, 19. Okt. 2013 (CEST)

Ich finde den Artikel in seiner jetzigen Form "rund" und lesenswert, auch im Vergleich zur englischen, spanischen oder französischen Fassung. Er betont die dem Problem zugrundeliegende Struktur. Zahlen / Buchstaben / Bilder oder Bauformen sind für mich lediglich Phänomenologie. Leider gehst Du auf meine Argumente von oben nicht ein. Warum konkret findest Du denn die aktuelle Variante eigentlich "nicht gut strukturiert"?

Ad 1 und 2: Kann man machen. "Steine entfernbar oder nicht?" deckt sich allerdings mit dem aktuellen Abschnitt "Zur Theorie des 15-Puzzles". Wenn man also das Vorzeichen von Permutationen und dgl. für denjenigen Leser aufsparen will, der es "genau wissen will" (also eher gegen Ende), so wird es, fürchte ich, auf Dopplungen hinauslaufen...

Ad 3: "Etwaiger Buchstabentausch bei Text": Erklärt sich ja dadurch, dass (in Deinem Beispiel) das eine „e“ die 4 ist und das andere die 10. Ein Tausch ändert die Parität. Vielleicht genügt ja der entsprechende klärende Hinweis (vergleiche Abschnitt „Zur Theorie des 15-Puzzles“), den ich nun eingefügt habe?

Ad 4: Ist die Zahlenversion nicht diejenige, die die meisten kennen? Zudem ist sie auch historisch die erste. Sollte, meine ich, schon am Anfang kommen. Man könnte aber in der Tat den Abschnitt Die Aufgabenstellung „Mische und bringe wieder in die richtige Reihenfolge“ und ihre Varianten vorziehen: er ist ja kurz.

Ad 6: Geschichte an den Schluss geht für mich gar nicht, denn das 15-Puzzle hat eine ganz besondere und zudem spannende Geschichte. Das sehen auch etliche Quellen, die mir bislang unter kamen, wortwörtlich ebenso.

Ich denke, wir sollten zunächst die Meinung anderer Wikipedianer hören.

Welt-der-Form (Diskussion) 00:44, 29. Okt. 2013 (CET)

Man sollte Geschichte, Aufgabenstellungen und Mathematik zusammenhalten. Mein Vorschlag für eine Strukturierung wäre der folgende:

1. Geschichte
2. Aufgabenstellungen
   1. Ursprüngliches 15-Puzzle (Gem-Puzzle und Varianten, mechanisches Puzzle, zufällige Ausgangsposition, in 50% der Fälle lösbar)
   2. 14-15-Puzzle (von Loyd und anderen vorgeschlagen, primär logisches Puzzle, geordnete Ausgangsposition mit 14 und 15 vertauscht, unlösbar)
   3. Modernes 15-Puzzle (moderne Varianten, mechanisch oder computergeneriert, aus der Zielstellung umgeordnete Ausgangsposition, vgl. Zauberwürfel, immer lösbar)
   4. Weitere Aufgabenstellungen (magisches Quadrat etc.)
3. Mathematischer Hintergrund
   1. Permutationen und Invarianten
   2. Beispiele
   3. Komplexitätsüberlegungen

Der Magisches-Quadrat-Variante würde ich keine eigene Überschrift einräumen, da sie, was die Bedeutung und Rezeption betrifft, weit hinter die anderen zurückfällt. Über die genauen Formulierungen der Überschriften lässt sich diskutieren, ich bin ein Fan prägnanter Überschriften. Zu den Bauformen als solches habe ich bislang nur wenig gelesen, bei genügend belastbaren Informationen könnte man hier einen eigenen Abschnitt mit Informationen zu Materialien und Ausführungen (z.B. wie man verhindert, dass die Teile rausfallen) ergänzen. Viele Grüße, --Quartl (Diskussion) 07:28, 29. Okt. 2013 (CET)

Mit dieser Reihenfolge kann ich mich auch anfreunden. Ich halte es aber für wesentlich, die Text- und Bildversionen zu erwähnen. Besonders die Tatsache, dass es dabei oft mind. zwei gleiche Steine gibt, deren Tausch die Lösbarkeit ermöglicht, ist wesentlich. Das sollte irgndwo nach der Stelle mit der Erklärung am Zahlenpuzzle in den Artikel. ÅñŧóñŜûŝî (Ð) 12:16, 29. Okt. 2013 (CET)

Was es die Mathematik angeht: Ich besaß in meiner Kindheit eine Version, bei der die Zahlen diagonal aufgedruckt waren. Um die Steine zu sortieren musste man die richtige der beiden um 90° verdrehten Möglichkeiten wählen. Dieser Wechsel der Lösbarkeit bei Drehung ist also auch ein Aspekt. ÅñŧóñŜûŝî (Ð) 12:21, 29. Okt. 2013 (CET)

Quartl, Dein Gliederungsvorschlag gefällt mir gut. Die Text- und Bildversionen fallen ja unter „2.3 Modernes 15-Puzzle / aus der Zielstellung umgeordnete Ausgangsposition“. Gottes Zahl wohl am besten bei Komplexitätsüberlegungen. Gruß --Welt-der-Form (Diskussion) 12:53, 29. Okt. 2013 (CET)

Ok, ich habe das so in etwa mal umgesetzt. Über den Text muss man aber stellenweise nochmal drübergehen. Viele Grüße, --Quartl (Diskussion) 13:27, 29. Okt. 2013 (CET)

So funktioniert Teamwork. Deine Stärke ist die mathem. Seite, Andere werden den Text pediküren. ÅñŧóñŜûŝî (Ð) 14:00, 29. Okt. 2013 (CET)

"14-15-Puzzle" vs. "15-14-Puzzle"

Hallo Antonsusi, Du hast am 23. Oktober aus der Überschrift "Die Aufgabenstellung beim 14-15-Puzzle" nun "Die Aufgabenstellung beim 15-14-Puzzle" gemacht. Aus welchem Grund? In welcher Quelle hast Du das denn so gefunden? In "Sam Loyd; Martin Gardner: Mathematical puzzles of Sam Loyd. Dover Pubs., New York, 1959, S. 19" heißt es jedenfalls noch "14-15-Puzzle"... Im Moment findet man übrigens im Artikel beide Varianten: in der Einleitung "14-15-Puzzle" und im 2. Abschnitt dann "15-14-Puzzle"...? Gruß Welt-der-Form (Diskussion) 16:32, 28. Okt. 2013 (CET)

Ich halte es für logisch, die Startanordnung "1 bis 13, 14, 15" als "14-15-Puzzle" und die Startanordnung 1 bis 13, 15, 14 als "15-14-Puzzle" zu bezeichnen. Bei nicht entfernbaren Steinen ist das ja ein Unterschied. Es sind logisch verschiedene Spiele. P.S.: Was hältst du vom o.g. Gestaltungsvorschlag? ÅñŧóñŜûŝî (Ð) 18:58, 28. Okt. 2013 (CET)

Die Literatur sagt 14-15-Puzzle, deswegen sollten wir keine Begriffsbildung betreiben und es genauso nennen. Grüße, --Quartl (Diskussion) 22:22, 28. Okt. 2013 (CET)

Mach es, wie du willst, das ist mir nicht so wichtig. Wichtiger ist ein besseres Gesamtkonzept für den Artikel (eins oberhalb). ÅñŧóñŜûŝî (Ð) 22:31, 28. Okt. 2013 (CET)

Also ich finde die aktuelle Überarbeitung auf alle Fälle besser als die vorhergehende, das jetzt thematisch zusammengehörende Dinge besser zusammengefasst sind als vorher. Bei deiner jetzt oben vorgeschlagenen Umstrukturiering bin ich auf den ersten Blick eher skeptisch. Wo finde ich übrigens die Regelvariante zum Entfernen von Steinen?--Kmhkmh (Diskussion) 22:38, 28. Okt. 2013 (CET)

Es geht darum, ob das (technich) möglich ist. Ist es nicht möglich, dann ist permanent festgelegt, welche Zielanordnungen erreichbar sind und welche nicht. Fängt man aber an, indem man zu Beginn die 15 Steine zufällig einsetzt und dann schiebt, dann beträgt für jede Zielanordnung die Wahrscheinlichkeit, die Aufgabe lösen zu können, 50%. ÅñŧóñŜûŝî (Ð) 22:49, 28. Okt. 2013 (CET)

Es sist mir schon klar, worum es geht. Ich wollte wissen in welcher Quelle diese Regelvariante steht.--Kmhkmh (Diskussion) 23:31, 28. Okt. 2013 (CET)

Bevor es Bauformen ohne Entnahme ("mit Nut und Feder") gab, gab es Bauformen mit einfachen Holzstücken. Ist doch logisch, dass man da beim (erneuten) Mischen zuerst einfach entnommen und dann zufällig einsetzt hat. ÅñŧóñŜûŝî (Ð) 12:26, 29. Okt. 2013 (CET)

Harte Nuss

Was es Bilderpuzzles angeht: Harte Nuss zum Knacken... ÅñŧóñŜûŝî (Ð) 00:17, 29. Okt. 2013 (CET)

Offensichtlich falsche Charakterisierung unlösbarer Puzzles

Im Artikel steht:

Die ungeraden Permutationen des Puzzles (wie z.B. die Start-Anordnung des 14-15-Puzzles) sind, wie Johnson 1879 zeigte, nicht lösbar, d.h. diese Start-Anordnungen können durch Verschiebung der Kacheln nicht wieder in aufsteigende Reihenfolge mit dem leeren Feld unten rechts gebracht werden.

So einfach ist es nun aber nicht, da wurde Johnson sicherlich falsch zitiert. Wie aus den Sätzen unmittelbar vor dem von mir zitierten Satz hervorgeht, ist hier von Permutationen aus $S_{16}$ die Rede. Betrachten wir die Permutation, die nur die letzten beiden Zahlen vertauscht, also die 15 mit der 16. Den Rest lässt sie fix. Dann hat diese Permutation zwar ein ungerades Vorzeichen, jedoch lässt sich das entsprechende Rätsel spielend leicht lösen: Nur ein Zug ist von Nöten. --Jobu0101 (Diskussion) 19:21, 10. Dez. 2013 (CET)

Man muss bei der mathematischen Betrachtung über Permutationen mit der Lücke aufpassen, siehe Portal Diskussion:Mathematik/Archiv/2013/4#15-Puzzle. Man sollte an dieser Stelle besser von Parität sprechen, genaueres dazu steht im Abschnitt zum mathematischen Hintergrund. Viele Grüße, --Quartl (Diskussion) 19:30, 10. Dez. 2013 (CET)

Ja aber so kann es doch nicht im Artikel bleiben. --Jobu0101 (Diskussion) 22:48, 10. Dez. 2013 (CET)

Ich habe den Abschnitt entsprechend umformuliert. Viele Grüße, --Quartl (Diskussion) 06:24, 11. Dez. 2013 (CET)

RAID System irrelevant

Der Satz "Zur Vermeidung von Speicherfehlern - immerhin waren 8 \cdot 1014 Bit ≈ 100 Terabyte zu schreiben und zu lesen - verwendeten Korf und Schultze ein RAID-System." hat doch überhaupt nichts mit dem Puzzle, dem Algorithmus und dem mathematischen Hintergrund zu tun. Er ist meiner Meinung nach völlig überflüssig. --Danghor (Diskussion) 21:52, 11. Apr. 2016 (CEST)

N_2 die Nummer der Reihe?

Im Abschnitt "Permutationen und Invarianten" steht: "Dabei ist N_1 die Anzahl der Zahlenpaare, die sich in falscher Reihenfolge befinden und N_2 die Nummer der Reihe, in der sich das leere Feld befindet." Was ist die "Reihe"? Spalte oder Zeile? Aber das wäre sowieso unlogisch, weil Spalten und Zeilen gleichberechtigt sein müssen. Eher etwas mit der City-Block-Metrik relativ zu einer festen Position. (nicht signierter Beitrag von 5.10.42.88 (Diskussion) 10:48, 14. Apr. 2016 (CEST))

Reihe ist Zeile.--Kmhkmh (Diskussion) 13:10, 14. Apr. 2016 (CEST)