nicht angemeldet
Matthias Apsel
Der Martin
Matthias Apsel
Matthias Apsel
Der Martin
Rolf B
Matthias Apsel
Rolf B
Matthias Apsel
Rolf B
Matthias Apsel
Rolf B
Hallo alle,
wieviele Möglichkeiten gibt es, 24 Türchen des Adventskalenders so in einem 6 × 4 -Raster anzuordnen, dass sich benachbarte Zahlen nicht berühren?
Beispiel: In keinem der vier Felder, die mit dem Feld der 2 eine gemeinsame Seite haben, darf die 1 oder die 3 stehen.
Beispiel: In keinem der acht Felder, die mit dem Feld der 2 eine gemeinsame Seite oder Ecke haben, darf die 1 oder die 3 stehen.
Bis demnächst
Matthias
Hallo Matthias,
wieviele Möglichkeiten gibt es, 24 Türchen des Adventskalenders so in einem 6 × 4 -Raster anzuordnen, dass sich benachbarte Zahlen nicht berühren?
verstehe ich dich richtig, dass du zwei unterschiedliche Aufgabenstellungen hast?
Beispiel: In keinem der vier Felder, die mit dem Feld der 2 eine gemeinsame Seite haben, darf die 1 oder die 3 stehen.
Das wäre die etwas einfachere Aufgabe.
Beispiel: In keinem der acht Felder, die mit dem Feld der 2 eine gemeinsame Seite oder Ecke haben, darf die 1 oder die 3 stehen.
Und das die verschärfte.
Gibt es denn eine systematische, methodische Lösung? Klar ist mir, dass es 24! Möglichkeiten gibt, die 24 Zahlen ohne weitere Bedingungen anzuordnen[1]. Ich muss also "nur" einen mathematischen Ausdruck finden, der die Zahl der verbotenen Lösungen ergibt, und das von der Gesamtzahl abziehen.
Easy. 😉
Aber im Moment fehlt mir noch der Ansatz. Es gibt viele unterschiedliche Fälle zu beachten.
Live long and pros healthy,
Martin
24!/4, wenn man die vertikal oder horizontal gespiegelten Varianten als gleichwertig betrachtet. ↩︎
Hallo Der Martin,
verstehe ich dich richtig, dass du zwei unterschiedliche Aufgabenstellungen hast?
Ja.
Gibt es denn eine systematische, methodische Lösung?
Im Moment habe ich keine. Wenn ich eine solche Lösung finden sollte, würde ich dafür sorgen, dass weder die 1 noch die 24 am Rand sind.
Aber im Moment fehlt mir noch der Ansatz. Es gibt viele unterschiedliche Fälle zu beachten.
Vielleicht ist es auch was für den Programmierer?
Bis demnächst
Matthias
Hallo Matthias Apsel,
Vielleicht ist es auch was für den Programmierer?
Es scheint wohl sehr viele Möglichkeiten zu geben, wenn sich ohne Schwierigkeiten eine finden lässt.
1 13 2 14 3 15
4 16 5 17 6 18
7 19 8 20 9 21
10 22 11 23 12 24
würde ich mal als triviale Lösung bezeichnen (ich hoffe, ich habe mich nicht verguckt und es auch wirklich eine).
Bis demnächst
Matthias
Hallo,
Es scheint wohl sehr viele Möglichkeiten zu geben, wenn sich ohne Schwierigkeiten eine finden lässt.
1 13 2 14 3 15 4 16 5 17 6 18 7 19 8 20 9 21 10 22 11 23 12 24
sieht in der Tat nach einer gültigen Lösung aus. Sogar für die schärfere zweite Variante.
Und aus dieser einen Lösung werden allein durch Vorstellungskraft 2*6*6*24*24 = 41472 mögliche Lösungen. Denn ich kann unabhängig voneinander
Bestimmt geht noch eine Menge mehr. Und das nur von deiner sehr regelmäßigen Anordnung ausgehend. Wahrscheinlich gibt es noch sehr viel mehr mögliche Lösungen mit chaotischer Anordnung.
Live long and pros healthy,
Martin
Hallo Martin,
ich habe mal ein bisschen rekursiv programmiert, mit einem Abbruch nach 120 Sekunden.
In der Zeit hat der Algorithmus 238 Millionen Lösungen gefunden, und ich habe mir keine sonderliche Mühe gegeben, zu optimieren. Diagonale Nachbarn waren dabei erlaubt. Wenn ich die verbiete, findet er immer noch 171 Millionen.
Der Algorithmus beginnt mit der 1 und probiert für sie alle Positionen durch. Pro Position macht er das gleiche mit der 2, und so weiter. Bei jeder Platzierung werden die Vorausetzungen überprüft. Da die Zahlen aufsteigend gesetzt werden, muss ich nur schauen, ob ringsum eine Zahl steht die um 1 kleiner ist.
Auf Ebene der 12 habe ich eine Ausgabe eingebaut, die sagt, dass er die 12 nun auf Position (x,y) setzt. Die 12 ergab sich aus der zeitlichen Distanz zwischen zwei Platzierungen.
Wenn ich die Diagonalen mit prüfe, braucht er pro 12 ca eine Sekunde. Tue ich das nicht, braucht er pro 12 etwa 10 Sekunden.
Und das bei 99 Billionen Möglichkeiten, die Zahlen von 1-11 zu platzieren. Nein, das ist nichts für mein Siliziumkleinhirn.
Rolf
Hallo Rolf B,
das hätte ich so nicht erwartet. Wieviel Prozent der Möglichkeiten genügen denn zweiten Bedingung?
Bis demnächst
Matthias
Hallo Matthias,
ok, um das vergleichen zu können musste ich die Betrachtungsmenge standardisieren. Vorher hatte ich nach Laufzeit abgebrochen.
Ich platziere also die Zahlen von 1-11 und probiere dann alle 12 durch. Wenn ich auf die Diagonalen nicht achte, dauert das 72 Sekunden und ich finde 286 Millionen Möglichkeiten.
Wenn ich die Diagonalen mitnehme, dauert es 8 Sekunden und ich finde 17,9 Millionen Möglichkeiten.
Gemacht mit diesem JavaScript. Vorsicht beim Laufenlassen, wenn ein JS läuft, kann man es im Browser nur durch F5 abbrechen. Und weil jsFiddle es dann sofort wieder anstartet, habe ich einen RUN Button davorgesetzt.
Rolf
Hallo Rolf B,
Spannend.
Es gab eine Zeit lang die Apsel'sche Sudoku-Vermutung, dass es in jedem der 5.5 Mrd Sudokus mindestens zwei Schnittpunkte von Feldern gibt, an denen sich dieselben Symbole diagonal gegenüberstehen.
Es gibt aber Sudokus, bei denen das nicht der Fall ist, etwa das Wikipedia-Beispiel zum X-Sudoku.
Gibt es aber auch Sudokus mit nur einem solcher Schnittpunkte, oder muss es, wenn es einen gibt, auch mindestens einen weiteren geben?
Bis demnächst
Matthias
Hallo Matthias,
Schnittpunkte von Feldern gibt, an denen sich dieselben Symbole diagonal gegenüberstehen
Ich habe nicht die geringste Vorstellung, was Du hiermit meinst.
Rolf
Hallo Rolf B,
Schnittpunkte von Feldern gibt, an denen sich dieselben Symbole diagonal gegenüberstehen
Ich habe nicht die geringste Vorstellung, was Du hiermit meinst.
https://commons.wikimedia.org/wiki/Category:Sudoku?uselang=de#/media/File:A_Didoku_NRNI_(Non-Repeto_and_Non-Inscripted)_on_Sudoku_board_by_Miguel_Palomo.png Siehe die 2, 6, 7, 9 in der dritten und vierten Zeile.
Bis demnächst
Matthias
Hallo Matthias,
ja ok. Aber um dazu Aussagen machen zu können, müsste man die Strukturen eines Sudoku irgendwie mathematisieren - und davon habe ich nicht die geringste Ahnung. Und auch, ganz ehrlich, kein Interesse.
Rolf
_on_Sudoku_board_by_Miguel_Palomo.png){kind=link}