| Autor |
 Mathematik hinter Suchrätseln |
|
horsthorst
Junior 
Dabei seit: 28.06.2022
Mitteilungen: 6
 |  Themenstart: 2022-06-28
|
Hallo zusammen,
ich möchte mich gerne mal mit Zahlen- und Wörtersuchrätseln beschäftigen. Das sind klassische Rätsel: Es sind Wörter- oder Zahlenkombinationen vorgegeben, die man dann in einer großen Matrix suchen muss.
Welche Mathematik steckt denn eigentlich dahinter? Es gibt ja unheimlich viele Rätselgeneratoren, bei denen man alle möglichen Parameter (Feldgröße, Lage der Wörter etc.) angeben kann. Das lässt mich vermuten, dass man so ein Rätsel auch formelbasiert erstellen kann.
Also als Beispiel:
Ich habe eine bestimmte Anzahl von Wörtern, möchte, dass diese in zwei Richtungen (von rechts nach links und von oben nach unten senkrecht) angeordnet sind und es soll jeder Buchstabe der Matrix mindestens ein Mal verwendet werden.
Kann ich sowas im Voraus "berechnen" um dann zu wissen, wo ich jeden einzelnen Buchstaben platzieren muss? Quasi eine Art Reverse Engineering eines Rätsels. 😁
Gruß
Jan
|
 Profil
|
dietmar0609
Senior 
Dabei seit: 29.06.2007
Mitteilungen: 3195
Wohnort: Oldenburg , Deutschland
 | Beitrag No.1, eingetragen 2022-06-28
|
Hallo Horsthorst,
Willkommen auf dem Matheplaneten.
Wo ist das Rätsel? Kannst du ein konkretes Rätsel/Beispiel nennen ?
Gruß Dietmar
|
Profil
|
horsthorst
Junior
Dabei seit: 28.06.2022
Mitteilungen: 6
|  Beitrag No.2, vom Themenstarter, eingetragen 2022-06-28
|
Hallo Dietmar, danke für's Willkommen 🙂
Hier ein Beispiel. Gibt es auch als Zahlenrätsel:
https://www.wort-suchen.de/buchstabensalat-loesen/
|
Profil
|
Scynja
Senior
Dabei seit: 23.02.2011
Mitteilungen: 573
Wohnort: Deutschland
| Beitrag No.3, eingetragen 2022-06-28
|
Hallo Horsthorst,
meine Vermutung ist, dass du einfach alle Wörter in das Feld schreibst und danach das Feld mit zufälligen Buchstaben auffüllst. Bei den wenigen Worten, um die es in der Regel geht, bekommt man das bestimmt auch mit Papier + Bleistift hin.
Interessant wird es meiner Meinung nach erst, wenn es darum geht aus einer Menge an Worten möglichst viele in so ein Gitter zu schreiben.
|
Profil
|
StrgAltEntf
Senior 
Dabei seit: 19.01.2013
Mitteilungen: 8279
Wohnort: Milchstraße
 | Beitrag No.4, eingetragen 2022-06-28
|
\quoteon(2022-06-28 09:52 - horsthorst im Themenstart)
und es soll jeder Buchstabe der Matrix mindestens ein Mal verwendet werden.
\quoteoff
Hallo horsthorst,
das ist ja in deinem Beispiel bei weitem nicht erfüllt.
Ich sehe das wie Scynja.
|
Profil
|
dietmar0609
Senior
Dabei seit: 29.06.2007
Mitteilungen: 3195
Wohnort: Oldenburg , Deutschland
| Beitrag No.5, eingetragen 2022-06-28
|
Hallo horsthorst,
Dachtest du vielleicht auch an sowas wie WORDLE , ein 5 Buchstabenspiel, was du leicht im Internet finden kannst? Dazu habe ich ein Programm geschrieben, was die Sucherei optimiert.
Gruß Dietmar
|
Profil
|
Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 7141
Wohnort: Niedersachsen
| Beitrag No.6, eingetragen 2022-06-28
|
Rätsel, in denen nach echten, sinnvollen Wörtern (also nicht beliebigen Buchstabenfolgen) gesucht werden muss, die relativ groß sind und gleichzeitig nur wenige ungenutzte Buchstaben enthalten, erfordern schon etwas Optimierungsaufwand.
Ohne wirklich zu wissen, wie die Rätselgeneratoren das im Einzelnen machen, würde ich vermuten, dass die zu findenden Wörter nach und nach an passenden Stellen eingebaut werden.
Um alle gegebenen Wörter einzubauen, gibt es eine einfache Optimierungsheuristik. Wenn sich ein Wort nicht mehr einbauen lässt, weil es an allen möglichen Stellen Kollisionen mit anderen Wörtern gibt, dann kann man nach Stellen mit möglichst wenigen Kollisionen suchen (am besten nur eine). Dann entfernt man die Wörter, die im Wege sind und baut dafür das neue Wort ein.
Für die entfernten Wörter sucht man dann neue Positionen.
Man kann sich das Leben auch einfache machen, in dem man gar nicht fordert, dass _alle_ Wörter einer Liste eingebaut werden, sondern nur möglichst viele. Dann findet man ja immer eine Lösung.
Bei Suchrätseln mit beliebigen Zahlen ist es dagegen praktisch trivial. Da kann man das Rätsel mit Ziffern füllen und dann die zu suchenden Zahlen einfach dem fertigen Rätsel entnehmen.
|
Profil
|
horsthorst
Junior 
Dabei seit: 28.06.2022
Mitteilungen: 6
| Beitrag No.7, vom Themenstarter, eingetragen 2022-06-29
|
Vielen Dank für die rege Beteiligung. Da sind wir schon auf dem richtigen Weg, allerdings aus meiner Sicht ist die Lösung noch nicht gefunden.
Ihr habt es ja bereits angesprochen, der Knackpunkt soll sein, dass alle Buchstaben oder Ziffern in der Matrix verwendet werden. Deswegen funktioniert es nicht, die gesuchten Wörter oder Zahlenkombinationen in einer "leere" Matrix zu platzieren und den Rest willkürlich aufzufüllen. Denn diese Füllmasse würde nicht benutzt werden.
Letztlich sind bei der Fragestellung folgende Aspekte bekannt/gegeben:
- Anzahl und Abfolge gesuchter Buchstaben bzw. Zahlenkombination
- Ausrichtung in der Matrix
- Vorgabe, dass alle Felder mindestens einmal verwendet werden (Überschneidungen sind zulässig)
Unbekannt (und gesucht) ist hingegen in Abhängigkeit zu den vorherigen Festlegungen:
- Anzahl der überhaupt benötigten Felder (Matrixgröße)
- konkrete Anordnung der Buchstaben bzw. Zahlen in der Matrix
Hier vermute ich, dass man sich diesen Themen mathematisch annähern kann und nicht auf Versuche angewiesen ist. Oder irre ich ich da?
|
Profil
|
Scynja
Senior
Dabei seit: 23.02.2011
Mitteilungen: 573
Wohnort: Deutschland
| Beitrag No.8, eingetragen 2022-06-29
|
Hallo horsthorst,
im ersten Schritt kannst du prüfen, ob es theoretisch möglich ist.
Beispiel: Aus den Worten {Schritt, Garten, Neuland, See} ist es unmöglich ein Rechteck zu bauen. Du kannst das ganze vereinfacht als Tetris-Spiel betrachten. Dabei ist es irrelevant, ob ein Wort senkrecht, waagerecht oder diagonal steht. Wenn du das Puzzle zusammensetzen kannst, ist die Aufgabe lösbar. Hierfür gibt es mit Sicherheit auch effiziente Algorithmen.
Den Rest wirst du wohl nur durch geschicktes probieren / backtracking herausfinden. Z. B. könnte man "Henne" und "Rennen" als Baustein "Rennenneh" betrachten. Durch die große Anzahl an Möglichkeiten würde ich das Problem als nicht effizient lösbar betrachten. Ich lasse mich aber gerne eines besseren belehren.
|
Profil
|
StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 8279
Wohnort: Milchstraße
| Beitrag No.9, eingetragen 2022-06-29
|
Hier mal eine Challenge:
\sourceon
ANFANG
ANKER
AUF
DANKE
ERFOLGE
HEUTE
IGEL
KATZEN
MATHE
MATROID
RAT
\sourceoff
(Alles von links nach rechts oder von oben nach unten.)
|
Profil
|
Scynja
Senior
Dabei seit: 23.02.2011
Mitteilungen: 573
Wohnort: Deutschland
| Beitrag No.10, eingetragen 2022-06-29
|
\quoteon(2022-06-29 19:46 - StrgAltEntf in Beitrag No. 9)
Hier mal eine Challenge:
\sourceon
ANFANG
ANKER
AUF
DANKE
ERFOLGE
HEUTE
IGEL
KATZEN
MATHE
MATROID
RAT
\sourceoff
(Alles von links nach rechts oder von oben nach unten.)
\quoteoff
https://matheplanet.com/matheplanet/nuke/html/uploads/b/30857_tetris.PNG
Die Preisfrage: Schafft es jemand mit weniger Feldern? (Ein Rechteck muss natürlich gegeben sein! + jede Seite sollte mindestens 4 Felder hoch / breit sein)
|
Profil
|
StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 8279
Wohnort: Milchstraße
| Beitrag No.11, eingetragen 2022-06-29
|
\quoteon(2022-06-29 20:33 - Scynja in Beitrag No. 10)
Die Preisfrage: Schafft es jemand mit weniger Feldern? (Ein Rechteck muss natürlich gegeben sein! + jede Seite sollte mindestens 4 Felder hoch / breit sein)
\quoteoff
Schon sehr gut 😃 Auch wenn bei dir der Legi statt der Igel vorkommt 😁 Es geht auch mit einem Rechtecke der Größe 35.
|
Profil
|
StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 8279
Wohnort: Milchstraße
| Beitrag No.12, eingetragen 2022-06-29
|
\quoteon(2022-06-29 20:43 - StrgAltEntf in Beitrag No. 11)
\quoteon(2022-06-29 20:33 - Scynja in Beitrag No. 10)
Die Preisfrage: Schafft es jemand mit weniger Feldern? (Ein Rechteck muss natürlich gegeben sein! + jede Seite sollte mindestens 4 Felder hoch / breit sein)
\quoteoff
Schon sehr gut 😃 Auch wenn bei dir der Legi statt der Igel vorkommt 😁 Es geht auch mit einem Rechtecke der Größe 35.
\quoteoff
Nachtrag: Bei meiner Lösung schneiden sich die Wörter teilweise, bei Scynjas Lösung sind die Wörter paarweise disjunkt.
|
Profil
|
Scynja
Senior
Dabei seit: 23.02.2011
Mitteilungen: 573
Wohnort: Deutschland
| Beitrag No.13, eingetragen 2022-06-29
|
\quoteon(2022-06-29 21:32 - StrgAltEntf in Beitrag No. 12)
\quoteon(2022-06-29 20:43 - StrgAltEntf in Beitrag No. 11)
\quoteon(2022-06-29 20:33 - Scynja in Beitrag No. 10)
Die Preisfrage: Schafft es jemand mit weniger Feldern? (Ein Rechteck muss natürlich gegeben sein! + jede Seite sollte mindestens 4 Felder hoch / breit sein)
\quoteoff
Schon sehr gut 😃 Auch wenn bei dir der Legi statt der Igel vorkommt 😁 Es geht auch mit einem Rechtecke der Größe 35.
\quoteoff
Nachtrag: Bei meiner Lösung schneiden sich die Wörter teilweise, bei Scynjas Lösung sind die Wörter paarweise disjunkt.
\quoteoff
Das will ich auch hoffen. Mir ist keine Lösung bekannt, die mit weniger Feldern auskommt, wo sich die Wörter nicht schneiden oder überlappen. Dass man nur von links nach rechts oder von oben nach unten schreiben soll, hatte ich versehentlich überlesen.
|
Profil
|
horsthorst
Junior
Dabei seit: 28.06.2022
Mitteilungen: 6
|  Beitrag No.14, vom Themenstarter, eingetragen 2022-06-30
|
Das mit dem paarweise disjunkt habe ich nicht verstanden. So wie ich es lese, bedeutet paarweise disjunkt, dass in einer Gesamtmenge M jeweils zwei Teilmengen disjunkt zueinander sind. Für mich hieße das: M = alle Wörter, jedes Wort = eine Teilmenge. Dann dürfte doch aber kein Wort einen gemeinsamen Buchstaben mit einem anderen Wort aufweisen?
Zudem kann ich auch nicht nachvollziehen leider, wie ihr auf eure Matrixanordnung gekommen seid sowie zu der Erkenntnis einer Mindestanzahl (35), wenn Wörter sich nicht überschneiden dürfen. Lasst mich an eurem Wissen teilhaben 😮😁
Würde man auch auf eine Mindestzahl kommen, wenn man als zusätzliche Regel hinzufügt: Überschneidungen bei gemeinsamen Buchstaben erlaubt?
Mir sind die Logikschritte noch nicht klar. Oder seid ihr durch Probieren darauf gekommen?
|
Profil
|
StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 8279
Wohnort: Milchstraße
| Beitrag No.15, eingetragen 2022-06-30
|
Hallo horst²,
mit "paarweise disjunkt" meinte ich, dass sich die von mir vorgegeben elf Wörter in Scynjas Lösung nicht kreuzen. Zähl mal die Länge der elf Wörter und addiere die Längen. Das ergibt 56. Das Rechteck von Scynja hat aber genau 56 Kästchen. Wenn jedes der Kästchen zu einem der elf Wörter gehören soll, folgt daraus sofort, dass sie sich gar nicht kreuzen können. (Denn sonst würde mindestens ein Kästchen zu zwei Wörtern gehören, und wir hätten damit mindestens ein Kästchen, das zu keinem Wort gehört.)
Ob 35 die Mindestzahl ist, weiß ich nicht. Und ich bin nicht durch Probieren drauf gekommen. Stattdessen bin ich anders herum vorgegangen: Ich habe zuerst das Rechteck gemalt und darin habe ich dann Buchstaben eingetragen, sodass jedes Kästchen zu mindestens einem echten Wort gehört.
So ging es los:
\sourceon
M A T R O I D
A A
T N
H K
E R F O L G E
\sourceoff
|
Profil
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
