Springerproblem

KnightMove · 13.02.2006, 18:36

Ich glaube mich zu erinnern gelesen zu haben, dass es für das Problem der Springerwanderung über das Schachbrett ca. 43 Billionen Lösungen gibt. Aber ich finde keine Quelle mehr dazu. Kann jemand weiterhelfen?

nikolajewitsch · 20.02.2006, 17:53

Für die Springerwanderung gibt es eine klare Anleitung: Der Springer muß immer auf das Feld mit der geringsten Zahl von dort aus erreichbarer weiterer noch nicht betretener Felder springen; gibt es mehrere, auf eines von ihnen. Daraus ergeben sich die möglichen Verzweigungen; wieviele es genau sind, weiß ich leider nicht.

Hermann · 17.08.2006, 21:30

Zitat:

Zitat von KnightMove

Ich glaube mich zu erinnern gelesen zu haben, dass es für das Problem der Springerwanderung über das Schachbrett ca. 43 Billionen Lösungen gibt. Aber ich finde keine Quelle mehr dazu. Kann jemand weiterhelfen?

Sorry, muß ich auch erst suchen ...

Das war aber letztes Jahr schon einmal ein Thema hier.

Vielleicht ist ja auch das folgende Springerproblem aus dem letzten Jahr für Dich interessant ...

Hermann · 17.08.2006, 21:44

http://de.wikipedia.org/wiki/Springerproblem

Unter http://www.axel-conrad.de/springer/springer.html:

Zitat:

Nebenbei sprang so noch ein Verfahren dabei heraus, das erlaubt, z.B. ein 100.000x100.000 oder ein 100.000.000x123.456.789-Brett innerhalb einer Sekunde zu berechnen - vorausgesetzt, sie haben einen langsamen Rechner.

Hermann · 24.08.2006, 12:05

Zitat:

Zitat von KnightMove

Ich glaube mich zu erinnern gelesen zu haben, dass es für das Problem der Springerwanderung über das Schachbrett ca. 43 Billionen Lösungen gibt.

Sind nur 13 Billionen, siehe unten ...

Zitat:

Aber ich finde keine Quelle mehr dazu. Kann jemand weiterhelfen?

Hier ist die Quelle, welche Du im Sinn hattest:
http://www.combinatorics.org/Volume_...ts/v3i1r5.html
(Diese Publikation beinhaltet den richtigen Weg, aber die falsche Anzahl)

Und hier ist die richtige Anzahl zu finden:
http://www.combinatorics.org/Volume_...ts/v3i1r5.html

Zitat:

Comments on: Martin Loebbing and Ingo Wegener, The Number of Knight's Tours Equals 33,439,123,484,294 --- Counting with Binary Decision Diagrams
Comment by the authors, May 15, 1996: The number of knight's tours given in the paper is incorrect, since the correct number must be divisible by 4. The method and the running time are correct. We will re-run the computations, which involves the use of many computers, and announce the results here when they are available.
--------------------------------------------------------------------------------

Comment from Brendan McKay, Feb 18, 1997: I have recomputed the number of knight's tours using another method, and obtained the answer 13,267,364,410,532. A description is available in PostScript. [Technical Report TR-CS-97-03, Department of Computer Science, Australian National University (1997).]

Gepard · 27.08.2006, 12:59

Hallo Hermann,
irgendwie funktionieren Deine Links nicht. Ich bekomme die Fehlermeldung 557 DNS vorübergehender Fehler bzw. "Die Seite kann nicht angezeigt werden".

Hermann · 28.08.2006, 10:47

Hallo Gepard,

Zitat:

Zitat von Gepard

Hallo Hermann,
irgendwie funktionieren Deine Links nicht. Ich bekomme die Fehlermeldung 557 DNS vorübergehender Fehler bzw. "Die Seite kann nicht angezeigt werden".

jetzt komme ich auch gerade nicht dran

, aber die Links sind korrekt

.
Ich habe ja auch das 3. Zitat aus Beitrag #5 dieses Threads über diese Links bekommen ...
Einfach später nochmal versuchen!

Hermann · 30.08.2006, 22:05

Hallo Gepard,

ich bin hier im Urlaub (in dem Hotel mit Internetzugang) ein wenig gehandicapped, aber es gibt anscheinend nichts, was man online nicht irgendwie hinkriegt.

Die beiden Artikel (Original von Löbbing&Wegener und der von McKay) sind als .pdf files angehängt.

Da die Originalfiles PostScript files sind (.ps), mußten die irgendwie in .pdf konvertiert werden.
Das konnte ich mittels
http://www.ps2pdf.com
online erledigen

Ich wollte aber nichts hochstellen, daß ich mir nicht angesehen habe, und der Adobe Reader ist hier nicht installiert

, und ich darf hier auch nichts installieren ...

Aber mit ein bißchen googlen fand ich
http://www.foxitsoftware.com/pdf/rd_intro.php
und für diesen Reader braucht man nichts zu installieren ...

dk180473 · 12.12.2007, 00:38

Hallo, ich bin neu hier weil ich bzgl. des Springerproblems(Tour de Gaul)
etwas interessantes festgestellt habe. Wenn man es schafft, eine gewisse Symmetrie während der ersten Sprünge zu bilden, ist der Rest einer Kinderspiel. Hier ist ein Beispiel. Wenn man soweit ist, hat man es fast geschafft. Die Restlösung gebe ich gern nachträglich bekannt.
Eine Stufe höher anzusiedeln, ist die Herausforderung, daß sich der Hund in den Schwanz beißt. Das heißt, das letzte Feld ist einen Springerzug von der Startposition entfernt.

Springerproblem

Du kennst ein gutes Schachrätsel? Hier kannst Du damit die Hirne anderer zum rauchen bringen. :)

Springerproblem