| Autor |
Beitrag |
    
Arend Hintze (Ahnt)
| | Veröffentlicht am Dienstag, den 31. Juli, 2001 - 10:53: | 
|
Also:
Es gibt dieses Zahlenspiel mit 4*4 Feldern ein ist frei und man muß die Zahlen (1-15) in die richtige reihenfolge bringen - klar, man darf nur auf das feld schieben, daß frei ist,
1. Wie heißt denn das spiel überhaupt?
2. Ich will das mit einem rekursiven algorithmus lösen, aber scheitere! Wie mach ich das also?
Hilfe Hilfe |
HansMayer
| | Veröffentlicht am Dienstag, den 31. Juli, 2001 - 13:03: |
|
Hättest Du das Buch "Fermats letzter Satz" von Simon Singh gelesen, wüßtest Du, das dieses Spiel unlösbar ist.
Für nähere Begründungen siehe in oben genanntem Buch.
MfG
Hans |
Heinie
| | Veröffentlicht am Dienstag, den 31. Juli, 2001 - 22:06: |
|
Hallo Hans, ich hab nicht viel Ahnung von dem, was in dem Buch stehen soll,
ich versteh jetzt aber nicht, was du meinst.
Es geht doch um solche Zahlenpuzzles:
http://home.teleos-web.de/uschroeder/spiele/zahl.html
http://www.brandl-web.de/Puzzle.htm
Meinst du, das Spiel wäre unlösbar oder die Aufgabe, eine rekursiven algorithmus aufzustellen, wäre unlösbar?
Freundliche Grüße
Heinie |
SpockGeiger (Spockgeiger)
| | Veröffentlicht am Mittwoch, den 01. August, 2001 - 01:05: |
|
Hallo HansMayer
Was heißt denn für Dich unlösbar? Es ist wahr, dass bei beliebigen Anordnungen die Hälfte nicht lösbar ist, aber was meinst Du genau?
viele Grüße
SpockGeiger |
Arend Hintze (Ahnt)
| | Veröffentlicht am Mittwoch, den 01. August, 2001 - 09:20: |
|
Tja erst mal Danke!
Also was ich mache ist:
Wenn Zellen (die in der Biologie) sich sortieren, und das tun diese während der Embryogense, sortieren die sich. In diesem Zahlenpuzzels sortiren sich auch "Zellen" und zwar wirklich ähnlich denen im Embryo.
Wie machen die das? Eine Idee ist anhand der Nachbarschaften. Wenn ich also das Zahlenpuzzel löse, nur mit Hilfe der Nachbarschaft, (die vier Felder um das leere Feld) heißt das
=> man kann ein Feld (Zellhaufen) an Hand der Nachbarn sortieren....
Dazu muß ich jetzt dieses Feld sortieren, ich will aber überhaupt erstmal eine Lösung programieren! ich programmiere also eine Rekursion und da scheitern meine Programmier kenntnisse, ich bekomme diese Rekursion nicht programmier.....
Wie mach ich das? Und außerdem lese ich jetzt nen Letzten satz von Fermatz...
Aber trotzdem muß ich das Feld immernoch lösen, ich kann ja später mal genau erklären was ich da mache die Zeit reicht grade nicht. Danke AHnt |
Aur0n (Aur0n)
| | Veröffentlicht am Mittwoch, den 01. August, 2001 - 22:08: |
|
Also ich kenne nicht den Satz von Fermant, und auch keine höhere Mathematik, aber dieses Problem ist lösbar - das sieht man doch auf den ersten Blick (lol, ein Reim).
Programmierst du auch in C/C++? Ausserdem mag ich rekursiv nicht so. Bin eher für iterativ, ist ausserdem schneller!
Werde mich morgen mal hier mit beschäftigen (stehe spät auf), also erzähl mal was du schon herausgefunden hast, wie man die Felder am besten in verschiedenen Situationen verschiebt.
Wie können uns auch über ICQ unterhalten (14390668).
cu, aur0n |
Arend Hintze (Ahnt)
| | Veröffentlicht am Donnerstag, den 02. August, 2001 - 11:56: |
|
Ja, Also:
Folgendes ist zu machen:
Es gibt einen Array (oben)(rechts)(unten)(links)
(1..16)(1..16)(1..16)(1..16)
Dieser Array beschreibt die nachbarschaft um das leere Feld, da ich ja später dieses Spiel an Hand der Nachbarschaften lösen will, muß in dieses Feld Eingetragen werden welche richtung zu welcher Situation geschoben wird.
Bsp: wir sind einen zug vor der Lösung und unten rechts ist die 15, links daneben ist das leer eFeld und links neben dem leeren Feld ist die 14, über dem Leeren Feld ist logisch die 11, dann muß in den Array (11)(15)(14)(0) nach links schieben eingetragen werden weill das die Situation löst.
Ich brauche also einen Algorithmus der aus einem gegebenen Feld eine Liste von zügen macht die zur Lösung führt, aus der ich zu Züge in das Feld eintragen kann.
so. das ists was ich brauche.
Was ich bisher gemacht hab ist in Delphi - aber nur wegen der Graphik, sonst ist es auch kein problem c/c++ zu nehmen - eine Funktion implementiert die ein vorgegebenes Feld nimmt, überprüft ob einer der vier züge die Lösung ist wen ja zurückgibt was die lösung ist, ansonsten ruft sich die funktion auf und überprüft ob das Feld mit der entsprewchenden veränderung eine lösung hat und gibt diese dann zurück,
da ist ersten irgendwie der Wurm drin und es ist zwar rekursiv aber nicht schön und wegen des Heap überlaufes gibts auch keine Lösung,
das ganze etwas sauberer programmiert muß eine Lösung geben...
möglich ist es auch einen Baum aus möglichen verschiebungen zu machen und den dann zu durchsuchen nach der kürzesten Lösung ... die ausgeben und gut, aber der Bam müßte damit es sinn macht ja auch möglichst rekursiv durchsucht werden.
Tja das ist es... ab Montag kann ich wieder mal was tippen im Moment bin ich mit meiner Diplomarbeit leider dieses Wochenende dran
Arend |
Aur0n (Aur0n)
| | Veröffentlicht am Donnerstag, den 02. August, 2001 - 14:04: |
|
Kannst du mal diese Funktion die noch Bugs hat posten (egal welche Programmiersprache)?
Ruft deine rekursive Funktion sich je Aufruf nochmal viermal (bzw. weniger) auf, da das leere Feld ja pro Zug vier Möglichkeiten hat (ausser an Wand oder Ecke)?
aur0n |
Arend Hintze (Ahnt)
| | Veröffentlicht am Montag, den 06. August, 2001 - 08:50: |
|
Hi,
Also ich hab am Wochenende mal zeit gehabt nachzudenken, folgendes ist rausgekommen:
1. Ich will ja bloß die Bewegungen die bei einer Lösung auftreten in abhängigkeit der Nachbarschaften in eine Tabelle eintragen.
2. Um sicherzugehen, daß ich ein Feld erzäuge das lösbar ist, mach ich mit dem gelösten feld zufällig verschiebungen.
3. Wenn ich diese verschiebungen in einer Liste speicher stellen diese Verschiebungen ja rückwärts die Lösung dar... ;)
4. Achtung: es ist möglich das der zufall es so wollte, daß zwei mal das gleiche feld entsteht, also muß ich bloß die Liste nach gleichen Feldern durchsuchen und um die "schleifen" "kürzen".
Was hälst du davon?
5. das Feld 2*2 (ha ha ha) hat nur 16 (oder 12 ich weiß nicht mehr genau) Zustände die möglich sind, die sich zu einer Schleife anordnen, wenn man da die Bewegungen zu den Nachbarschaften in einer Tabelle aufschreibt kann man dieses Feld über die Nachbarschaften lösen, einziges Problem:
Die Tabelle ist überbestimmt, weil sich eigentlich ja für jedes Feld eine Spalte in de Tabelle befindet. Ich weiß nicht was daraus folgt.
6. Die Tabelle 3*3 ist meiner Meinung nach zu lösen über die Nachbarschaften, da das Problem immer in vier Teil-Felder die lösbar sind, zerfällt:
die linken oberen vier
die rechten oberen vier
die rechten unteren vier
die linken untern vier
wenn also das vierer Feld lösbar ist über die nachbarschaften und die überbestimmung aus 6. kein Problem darstellt, ist das 3*3 Feld lösbar.
8. Kann man diesen "Beweis" auch auf 4*4 übertrgen oder sogar auf 8*8
9. in meinem biologischen Beispiel geht es schließlich um 500 Zellen die dann auch noch 3 Dimensonal gelöst werden müssen
10. => die Frage: gibt es bei der Lösung-über Nachbarschaften ein veralgemeinerungsproblm von 2D auf 3D?
nun ja, ich werde also die Lösung über die vorhandene Lösung ausprobieren, aber vielen Dank, ihr könntet ja mal über die anderen Dinge nachdenken ;)
Arend |
|
