Matroids Matheplanet Forum Index
Moderiert von viertel
Matroids Matheplanet Forum Index » Rätsel und Knobeleien (Knobelecke) » ** Komplexe Springertour
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule ** Komplexe Springertour
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1361
Aus: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-07-22


Was Schachliches für die langen Sommerabende. 😄
Aus einem Schachbrett der Größe 10x10 werden fünf 2x2-Blöcke 'ausgesägt' (siehe Bild). Wie beim bekannten Springerproblem ist nun auf den verbleibenden 80 Feldern eine Springertour zu bestimmen:
1. Der Springer zieht wie beim Schach und betritt jedes Feld genau einmal; die entfernten Felder (violett) dürfen nicht betreten werden (wohl aber übersprungen, z.B. mit F4-H5).
2. Die Tour beginnt in der linken unteren Ecke (Feld A1) und endet in der rechten unteren Ecke (Feld J1).



Lösungen sind als Folge der besuchten Felder anzugeben (z.B. A1-C2-E3-...).



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Deine Lösung nicht direkt im Forum posten darfst.
Sende stattdessen Deine Lösung als private Nachricht an den Themensteller. Benutze dazu den Link 'Privat', den Du unter seinem Beitrag findest.
Der Themensteller wird zu gegebener Zeit über eingesandte (richtige) Lösungen informieren
und nach Ablauf einer (von ihm) festgelegten Zeit alle Lösungen veröffentlichen.
Scheystein
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.05.2018
Mitteilungen: 168
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-07-23


Ein schönes Rätsel  😄 Leider noch nicht gelöst ...


Als beste Zugfolge habe ich diese hier, 73 mal konnte ich den Springer ziehen lassen:
\[\left(
\begin{array}{cccccccccc}
 44 & 61 & 46 & 57 & 50 & 59 & 48 & 31 & 0 & 9 \\
 0 & 56 & 43 & 60 & 47 & 32 & 51 & 8 & 0 & 30 \\
 62 & 45 & 0 & 0 & 58 & 49 & 0 & 0 & 10 & 7 \\
 55 & 42 & 0 & 0 & 33 & 52 & 0 & 0 & 29 & 18 \\
 0 & 63 & 40 & 53 & 0 & 0 & 34 & 17 & 6 & 11 \\
 41 & 54 & 3 & 0 & 0 & 0 & 5 & 28 & 19 & 16 \\
 64 & 39 & 0 & 0 & 4 & 35 & 0 & 0 & 12 & 27 \\
 69 & 2 & 0 & 0 & 67 & 24 & 0 & 0 & 15 & 20 \\
 38 & 65 & 68 & 71 & 36 & 0 & 22 & 73 & 26 & 13 \\
 1 & 70 & 37 & 66 & 23 & 72 & 25 & 14 & 21 & 74 \\
\end{array}
\right)\]
Bin noch auf der Suche nach einem schnelleren und genaueren Test, welche Spielfelder (wie oben die Matrix) noch weiter spielbar sind.


Edit:
Interressant wäre die Anzahl der Lösungen.

Es gibt mindestens $300.000$ und eine davon ist

\[\left(
\begin{array}{cccccccccc}
 22 & 43 & 6 & 67 & 20 & 45 & 32 & 27 & 18 & 47 \\
 5 & 68 & 21 & 44 & 7 & 26 & 19 & 46 & 33 & 28 \\
 42 & 23 & 0 & 0 & 66 & 31 & 0 & 0 & 48 & 17 \\
 69 & 4 & 0 & 0 & 25 & 8 & 0 & 0 & 29 & 34 \\
 58 & 41 & 24 & 65 & 0 & 0 & 30 & 9 & 16 & 49 \\
 3 & 70 & 59 & 40 & 0 & 0 & 15 & 50 & 35 & 10 \\
 60 & 57 & 0 & 0 & 64 & 39 & 0 & 0 & 14 & 51 \\
 71 & 2 & 0 & 0 & 77 & 74 & 0 & 0 & 11 & 36 \\
 56 & 61 & 76 & 73 & 54 & 63 & 38 & 79 & 52 & 13 \\
 1 & 72 & 55 & 62 & 75 & 78 & 53 & 12 & 37 & 80 \\
\end{array}
\right)\]
beziehungsweise

A1-B3-A5-B7-A9-C10-E9-F7-H6-J5-I3-H1-J2-I4-G5-I6-J8-I10-G9-E10-C9-\
A10-B8-C6-E7-F9-H10-J9-I7-G6-F8-G10-I9-J7-I5-J3-I1-G2-F4-D5-B6-A8-B10-\
D9-F10-H9-J10-I8-J6-H5-J4-I2-G1-E2-C1-A2-B4-A6-C5-A4-B2-D1-F2-E4-D6-\
E8-D10-B9-A7-B5-A3-B1-D2-F3-E1-C2-E3-F1-H2-J1

Lösungen für größere quadratische Felder findet man übrigens hier.



Gruß
Scheystein



-----------------
"Was hast du hier zu suchen ?"



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2332
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2019-07-23




['36', '13', '42', '17', '34', '15', '64', '57', '32', '29']
['41', '18', '35', '14', '43', '56', '33', '30', '63', '58']
['12', '37', '00', '00', '16', '65', '00', '00', '28', '31']
['19', '40', '00', '00', '55', '44', '00', '00', '59', '62']
['38', '11', '54', '21', '00', '00', '66', '61', '46', '27']
['53', '20', '39', '78', '00', '00', '45', '76', '67', '60']
['10', '79', '00', '00', '22', '77', '00', '00', '26', '47']
['03', '52', '00', '00', '07', '72', '00', '00', '75', '68']
['80', '09', '02', '05', '50', '23', '70', '73', '48', '25']
['01', '04', '51', '08', '71', '06', '49', '24', '69', '74']



Der Standardalgorithmus (Greedy) löst das recht problemlos.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Scheystein
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.05.2018
Mitteilungen: 168
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-07-23


@DerEinfaeltige

Der Endpunkt soll nach Aufgabenstellung unten rechts liegen, das dürfte dein Programm aber nicht viel verändern.

Gruß
Scheystein




-----------------
"Was hast du hier zu suchen ?"



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
querin
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 12.01.2018
Mitteilungen: 327
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2019-07-23


Mein Lösungsvorschlag
56 51  6 61 38 53  8 43 36 41 
 5 62 55 52  7 60 37 40  9 44 
50 57  X  X 54 39  X  X 42 35 
63  4  X  X 59 66  X  X 45 10 
26 49 58 65  X  X 46 67 34 71 
 3 64 25 48  X  X 77 70 11 68 
24 27  X  X 76 47  X  X 72 33 
17  2  X  X 21 78  X  X 69 12 
28 23 16 19 30 75 14 79 32 73 
 1 18 29 22 15 20 31 74 13 80 




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2332
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2019-07-23


Dann hier auch mein geupdateter Vorschlag:


[
['36', '13', '42', '17', '34', '15', '70', '61', '32', '29'],
['41', '18', '35', '14', '43', '60', '33', '30', '69', '62'],
['12', '37', '  ', '  ', '16', '71', '  ', '  ', '28', '31'],
['19', '40', '  ', '  ', '59', '44', '  ', '  ', '63', '68'],
['38', '11', '58', '21', '  ', '  ', '72', '67', '46', '27'],
['57', '20', '39', '52', '  ', '  ', '45', '64', '73', '66'],
['10', '53', '  ', '  ', '22', '51', '  ', '  ', '26', '47'],
[' 3', '56', '  ', '  ', ' 7', '78', '  ', '  ', '65', '74'],
['54', ' 9', ' 2', ' 5', '50', '23', '76', '79', '48', '25'],
[' 1', ' 4', '55', ' 8', '77', ' 6', '49', '24', '75', '80']]




-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1361
Aus: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2019-07-23


Interessante Lösungen. 😄 Die Problemlösung scheint einfacher als gedacht, insbesondere wenn die Greedystrategie (= Warnsdorff-Regel?) hinreicht.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2332
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2019-07-23


2019-07-23 21:42 - Kay_S in Beitrag No. 6 schreibt:
Interessante Lösungen. 😄 Die Problemlösung scheint einfacher als gedacht, insbesondere wenn die Greedystrategie (= Warnsdorff-Regel?) hinreicht.

Ich wusste zwar nicht, dass diese Regel so heißt, aber ja. :)


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Scheystein
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.05.2018
Mitteilungen: 168
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2019-07-24


2019-07-23 21:42 - Kay_S in Beitrag No. 6 schreibt:
Interessante Lösungen. 😄 Die Problemlösung scheint einfacher als gedacht, insbesondere wenn die Greedystrategie (= Warnsdorff-Regel?) hinreicht.

Verwendet man Mathematica und geht vor wie hier, dann wird es durch die eingebauten Funktionen "FindHamiltonianCyle" bzw. "FindHamiltonianPath" zu einem Dreizeiler (und sehr effizient). Man muss lediglich die Start- und Endpunkte beachten und zudem bietet es sich an bei "FindHamiltonianCyle" zwei Dummyfelder zu benutzen, da auf dem obigen Feld im Gegensatz zu 8x8 keine geschlossene Springertour existiert. Aber dann hat man nicht viel selber gemacht ...  😄

Gruß
Scheystein


-----------------
"Was hast du hier zu suchen ?"



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3573
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2019-07-31


Hat eigentlich jemand versucht, das Problem ohne Computerunterstützung, also quasi mit Papier und Bleistift, zu lösen? Ich knabbere mir da seit einigen Tagen die Zähne dran aus ( weil ich im Urlaub genau diese Tools zur Hand hatte) und überlege, ob ich mich da grundsätzlich übernommen habe....



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kay_S hat die Antworten auf ihre/seine Frage gesehen.
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Deine Lösung nicht direkt im Forum posten darfst.
Sende stattdessen Deine Lösung als private Nachricht an den Themensteller. Benutze dazu den Link 'Privat', den Du unter seinem Beitrag findest.
Der Themensteller wird zu gegebener Zeit über eingesandte (richtige) Lösungen informieren
und nach Ablauf einer (von ihm) festgelegten Zeit alle Lösungen veröffentlichen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]