Backtracking
lima-city → Forum → Programmiersprachen → PHP, MySQL & .htaccess
algorithmus
beitrag
dan
durchaus
grund
jemand
komme
mache
meinst
methode
paar funktionen
prinzip
programmiersprache
rekursion
schaffen
schreiten
sekunde
speicher
tutorial
versuchen
-
Hi
wie kann man Backtracking mit PHP realisieren?
Das script soll sp?ter mal Sudokus l?sen k?nnen!
Edit (djfun):
Aus zwei mach eins^^:
-------------
Kann hier keiner Backtracking?
Beitrag ge?ndert am 29.06.2006 10:10 von djfun -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
-
Hi
wie kann man Backtracking mit PHP realisieren?
[...]
Na ja, so wie in anderen Programmiersprachen halt auch.
Wikipedia gibt wie immer einen guten Einstieg.
http://de.wikipedia.org/wiki/Backtracking
[...]
Das script soll sp?ter mal Sudokus l?sen k?nnen!
Interessant. Ich w?nsche dir viel Spass, aber sowas sollte ich auch mal machen, um mein Wissen zu vertiefen, aber ich bin ehrlich gesagt zu faul dazu. ^^ -
qbuut schrieb:
Ich weis, da komme ich her!!!
Ich hab jetzt jemanden gesucht, der das mit PHP realisieren kann, und mir erkl?rt, wie das geht.
Ich kann es pers?nlich auch nicht, es hat mich aber faziniert.
Weshalb ich mir gerade ein umfangreiches Tutorial in Delphi dazu durchlese.
Hier wirst du glaube ich auch nur sehr wenige wenn ?berhaupt jemanden finden, die/der sowas mit PHP realisieren kann. Meist k?nnen die Leute die es k?nnen kein PHP, sondern nur h?here Programmiersprachen. Das ist jedenfalls meine eigene Erfahrung.
Google am besten mal nach Rekursion bzw. Backtracking. Da solltest du genug finden.
Folgendes sieht noch recht interessant aus :
http://www.matheprisma.uni-wuppertal.de/Module/BackTr/index.htm
MfG Lucas
edit :
Hab doch noch jemanden gefunden. ^^
Im cwcity.de Board scheinen quetschke und pepe recht fit darin zu sein.
Beitrag ge?ndert am 28.06.2006 22:46 von lucas9991 -
Du meinst mit Delphi wird das was?Ich probs ma!
der 1. link ist super ums theoretisch zu verstehen
das mit google mache ich morgen mal
Leider muss man f?r das cwforum seine Adresse angeben, und das mache ich auf Websites grunds?tzlich net!!!
Kannst du sie mal fragen, wie das ginge?
Wenn sie es k?nnen , w?rde ich ?ber meinen Schatten springen und und mich reggen!
Danke f?r die Antworten bei Fragen bez?glich Delphi komme ich auf dich zur?ck
!
-
Warum sollte das nicht mit PHP gehen? Man braucht halt ein paar Funktionen und Variablen. Wenn man das Prinzip verstanden hat, dan sollte es auch gut umsetzbar sein.
Am Beispiel Sudoku kann man es doch so erkl?ren, dass du ein Feld hast und dann ?berpr?fst, ob da die Zahl 1 reinpasst. Ist dies der Fall, dann gehst du ein Feld weiter und wenn dort gar keine Zahl mehr passt, gehst du wieder ein Feld zur?ck. Das ganze musst du halt in ein paar Funktionen unterteilen, die dann immer wieder aufgerufen werden, bis das ganze gel?st ist.
Ich wei?, dass klingt jetzt nicht gerade hilfreich und ich habe es selbst ja auch noch nicht probiert, aber mit ein bisschen T?fteln d?rfte man das doch schon schaffen. -
Gut!
Dann sind wir 1. SChritt weiter
Ich hab leider net so viel Ahnung von PHP
hab zwar schon x tutorials und einige von dieser seite gelesen, aber das kann ich damit nicht.
Ich w?rde jetzt erstma so anfangen:
Jedem der 81 Felder w?rde ich die Namen 1-81 geben.
Das w?rde ich noch schaffen.
|------------------------------------------|
|01|02|03"04|05|06"07|08|09|
|--------------"------------"--------------|
|10|11|12"13|14|15"16|17|18|
|--------------"------------"--------------|
|19|20|21"22|23|24"25|26|27|
|""""""""""""""""""""""""""""""""""""""""""|
|28|29|30"31|32|33"34|35|36|
|--------------"------------"--------------|
|37|38|39"40|41|42"43|44|45|
|--------------"------------"--------------|
|46|47|48"49|50|51"52|53|54|
|""""""""""""""""""""""""""""""""""""""""""|
|55|56|57"58|59|60"61|62|63|
|--------------"------------"--------------|
|64|65|66"67|68|69"70|71|72|
|--------------"------------"--------------|
|73|74|75"76|77|78"79|80|81|
-------------------------------------------|
Dann w?rde ich die Regeln aufstellen.
in einem 9er Block und horizontal und vertikal darf nicht dieselbe Zahl stehen. <--kann man das vereinfachen, als f?r jedes Feld eine neue regel mit genauen Feldangaben aufzustellen?
So dann w?rde ich die Zahlen einsetzen lassen,
aber wie?
Mit welchem PHP Befehl setzt der server eine Zahl zwischen 1 und 9 ein?
Beitrag ge?ndert am 29.06.2006 00:33 von qbuut -
ich w?rde ein doppelt indiziertes array nehmen, ev. ein dreifaches
$sudoku[0][0]=7
$sudoku[0][1]=4
... -
Du meinst mit Delphi wird das was?Ich probs ma!
[...]
Nein, ich meinte damit, dass diese Tutorial daf?r ganz gut ist und dieses Tutorial behandelt die Problematik halt speziell in Delphi.
[...]
Leider muss man f?r das cwforum seine Adresse angeben, und das mache ich auf Websites grunds?tzlich net!!!
[...]
Zwingt dich irgendwer deine richtigen Daten einzugeben?
Nein, also ...
[...]
Danke f?r die Antworten bei Fragen bez?glich Delphi komme ich auf dich zur?ck!
Du kannst bei mir nachfragen, aber ich werde dich bei tiefergehenden Fragen schnell an ttobsen weiterleiten. ^^
MfG Lucas -
i-spacke schrieb:
Warum sollte das nicht mit PHP gehen? Man braucht halt ein paar Funktionen und Variablen. Wenn man das Prinzip verstanden hat, dan sollte es auch gut umsetzbar sein.
Den Algorithmus in PHP umzusetzen sollte (wie auch in C, Pascal, Fortran etc. pp.) m?glich sein. Allerdings sehe ich zwei m?gliche technische H?rden an der Lauff?higkeit einer PHP-Implementation:
1. Laufzeit: PHP-Skripte werden interpretativ (von einem gut ausgelasteten Webserver) abgearbeitet und sind in ihrer Geschwindigkeit demzufolge kaum mit nativen Programmen, welche auf einem Rechner mit vielen freien Kapazit?ten laufen, zu vergleichen. Dazu kommt die Tatsache, dass PHP-Skripte im Regelfall nach einer vom Administrator festgelegten Zeitspanne (Standard 30 Sekunden) abgebrochen werden (damit Endlosschleifen nicht den Server lahm legen). Von dieser Seite k?nnte es also Probleme geben, weil der Algorithmus es bestimmt nicht immer schafft, in 30 Sekunden eine L?sung zu finden.
2. PHP-Skripte werden auf Serverseite meist aus Sicherheitsgr?nden eher restriktiv ausgef?hrt. Sie haben z.B. keine M?glichkeit, direkt auf Speicherbereiche zuzugreifen oder bei Bedarf mehr Speicher anzufordern. Wieviel Hauptspeicher ein einzelnes Skript maximal zugeteilt bekommt, bestimmt AFAIK wiederum der Serveradministrator. Es kann also durchaus passieren, dass nach der n-ten Rekursion einfach mal ein Stack ?berl?uft und das Skript abbricht, obwohl theoretisch noch jede Menge Speicher frei w?re.
Deshalb halte ich PHP eher f?r ungeeignet, ich w?rde Fortran oder C empfehlen. Wenn du's allerdings in PHP hinkriegst, w?rde mich das Resultat durchaus auch mal interessieren (du kannst ja deinen lokalen Webserver zu Hause so umkonfigurieren, dass o.g. Probleme aus dem Weg ger?umt werden). Wenn ich nur mehr Zeit h?tte, w?rd ich's ja mal in C versuchen ...
Frohes Programmieren noch,
thw -
Hmm... scheint sehr interessant zu sein.
Vielleicht programmiere ich sowas mal.
Also ich w?rde auf jeden Fall eine rekursive Methode benutzen.
Das ganze "Backtracking" Verfahren sieht in Wikipedia aus wie ein "Bin?rer Baum" und damit habe ich ein bisschen Erfahrung (in Java).
Man m?sste einfach f?r jedes K?stchen 9 M?glichkeiten definieren - f?r jede Zahl eine.
Beginnend bei 1 (oder 9, oder sonstwo ;) ) w?rde man dann gucken: Darf ich diese Zahl reinsetzen? Wenn ja, dann mach beim n?chsten K?stchen weiter, versuche ebenfalls die 1. Geht das nicht, versuche eine andere Zahl. Man m?sste dann nach einer korrekten L?sung immer pr?fen, ob man am Ende des Feldes ist.
Kommt man irgendwann bei 9 (oder wo auch immer) an und es geht nicht, muss etwas vorher falsch sein. Die rekursive Methode geht also wieder einen Schritt zur?ck, sagt, dass die aktuelle Zahl falsch ist und z?hlt weiter nach oben (oder wohin auch immer ;) ).
Scheint f?r mich recht einfach zu sein.
Diese Methode ist vielleicht nicht die kl?gste, aber sie wird die L?sung irgendwann herausbekommen. Auch wenn ein Mensch vielleicht strategisch besser vorgehen k?nnte.
Morgen setze ich mich wohl mal dran und programmiere das in PHP oder Java... -
Kannste das dann hier posten?
-
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
