One Stroke kostenlos auf dem iPhone ausprobieren
Unendliche Rätsel. Adaptive Schwierigkeit. Keine erzwungene Werbung.
Die mathematische Grundlage jedes One-Stroke-Rätsels – einfach erklärt
Ein Euler-Pfad (auch Euler-Trail genannt) ist ein Pfad durch einen Graphen, der besuchtjede Kante genau einmal. Sie können sich das so vorstellen, als würden Sie jede Linie einer Figur zeichnen, ohne den Stift abzuheben und ohne eine Linie nachzuzeichnen.
A --- B | | C --- D Start: A → Ende: D (anders) Besucht jede Kante einmal
Beginnt und endet um anders Eckpunkte. Erfordert genau 2 Eckpunkte ungeraden Grades.
A / \ B---C \ / D Start: A → Ende: A (gleich) Besucht jede Kante einmal
Beginnt und endet am gleich Scheitelpunkt. Erfordert 0 Eckpunkte ungeraden Grades.
Der entscheidende Unterschied: ein Euler Pfad beginnt an einem Scheitelpunkt und endet an einem anderen. Ein Euler Schaltung beginnt und endet am selben Ort – es ist eine vollständige Schleife.
Euler hat ein einfaches, aber wirkungsvolles Regelwerk bewiesen, um zu bestimmen, ob ein Graph auf einen Schlag verfolgt werden kann:
| Eckpunkte ungeraden Grades | Ergebnis | Typ |
|---|---|---|
| 0 | Nachverfolgbar – beginnen Sie überall und enden Sie dort, wo Sie begonnen haben | Euler-Schaltung |
| 2 | Nachverfolgbar – muss an einem ungeraden Scheitelpunkt beginnen und am anderen enden | Euler-Pfad |
| 4, 6, 8... | Nicht auf einen Schlag auffindbar | Unmöglich |
Das ist es. Zählen Sie die Eckpunkte ungeraden Grades. Bei 0 oder 2 ist das Rätsel lösbar. Wenn es mehr sind, ist es unmöglich. Das nennt mandie ungerade/gerade Scheitelpunktregel.
Die Abschluss eines Scheitelpunkts ist einfach die Anzahl der Kanten (Verbindungen), die ihn berühren. Wenn ein Scheitelpunkt drei Kanten hat, ist sein Grad 3 (ungerade). Wenn es 4 Kanten hat, ist sein Grad 4 (gerade).
Beispiel: Eine Hausform
A (Grad 2 ✓ gerade)
/ \
B---C B (Grad 3 ✗ ungerade)
| | C (Grad 3 ✗ ungerade)
D---E D (Grad 2 ✓ gerade)
E (Grad 2 ✓ gerade)
2 Eckpunkte ungeraden Grades (B und C)
→ Euler-PFAD existiert: beginnt bei B, endet bei C✓ Ja — Euler-Schaltung. Beginnen Sie irgendwo und enden Sie dort, wo Sie begonnen haben.
✓ Ja — Klassische One-Stroke-Herausforderung. Hat genau 2 Eckpunkte ungeraden Grades.
✗ Nein — 4 ungerade Eckpunkte. Euler bewies 1736, dass dies unmöglich war.
✓ Ja — Euler-Schaltung. Alle Eckpunkte eben, sodass Sie überall beginnen und zurückkehren können.
Wenn die One Stroke-App ein neues Rätsel generiert, erstellt sie nicht zufällig Gitter und hofft, dass diese lösbar sind. Stattdessen wird der Satz von Euler verwendet Erstellen Sie Diagramme, bei denen mathematisch garantiert ist, dass sie eine Lösung haben.
Der prozedurale Generierungsalgorithmus stellt sicher, dass jedes Puzzle entweder 0 oder 2 Eckpunkte ungeraden Grades hat – was bedeutet, dass immer ein Euler-Pfad oder -Kreis existiert. Deshalb kann das Spiel unendlich viele lösbare Rätsel versprechen: Es ist kein Glück, es ist Mathematik.
Wenn Sie bei einem Rätsel in One Stroke nicht weiterkommen, versuchen Sie, Eulers Regeln anzuwenden:
Ein Euler-Pfad ist eine Spur in einem Diagramm, die jede Kante genau einmal besucht. Es beginnt an einem Scheitelpunkt und endet an einem anderen Scheitelpunkt. Ein Graph hat genau dann einen Euler-Pfad, wenn er genau zwei Eckpunkte mit ungeradem Grad hat.
Ein Euler-Pfad beginnt und endet an verschiedenen Eckpunkten und besucht jede Kante einmal. Ein Euler-Kreis beginnt und endet am selben Scheitelpunkt und besucht außerdem jede Kante einmal. Ein Euler-Pfad erfordert genau zwei Eckpunkte ungeraden Grades; Eine Euler-Schaltung erfordert 0.
One-Stroke-Rätsel sind im Wesentlichen Euler-Pfad-Probleme. Das Rätsel fordert Sie auf, jede Kante genau einmal zu verfolgen – was die Definition eines Euler-Pfades oder -Kreises ist. Spiele wie One Stroke verwenden den Satz von Euler, um sicherzustellen, dass jedes Rätsel eine gültige Lösung hat.
Nein. Ein Euler-Pfad besucht jeden Kante genau einmal. Ein Hamilton-Pfad besucht jeden Scheitelpunkt genau einmal. Sie sind verwandte, aber unterschiedliche Konzepte. Euler-Pfade haben einen einfachen Test (ungerade Eckpunkte zählen); Hamilton-Pfade sind viel schwieriger zu bestimmen (es handelt sich um ein NP-vollständiges Problem).
Unendliche Rätsel. Adaptive Schwierigkeit. Keine erzwungene Werbung.