iPhone で One Stroke を無料で試す
無限パズル。適応難易度。強制広告なし。
すべての一筆パズルの数学的基礎 — 簡単に説明
アン オイラー経路 (オイラー トレイルとも呼ばれます) は、次のようなグラフを通るパスです。すべてのエッジを 1 回だけ。これは、ペンを持ち上げたり、線を引き戻さずに、図のすべての線を描くことと考えることができます。
A --- B | | C --- D 開始：A → 終了：D（異なる） すべてのエッジを 1 回訪問します
に開始して終了します 違う 頂点。正確に必要 2 つの奇数次の頂点。
あ ／＼ B---C \/ D 開始：A → 終了：A（同） すべてのエッジを 1 回訪問します
で始まり、で終わります 同じ 頂点。必要なもの 奇数次の頂点が 0 個あります。
主な違い: オイラー パス ある頂点で始まり、別の頂点で終わります。オイラー 回路 同じ場所で始まり同じ場所で終わります。これは完全なループです。
オイラーは、グラフを 1 ストロークでトレースできるかどうかを判断するための、シンプルだが強力な一連のルールを証明しました。
| 奇数次の頂点 | 結果 | タイプ |
|---|---|---|
| 0 | 追跡可能 — どこからでも開始し、開始した場所で終了します | オイラー回路 |
| 2 | 追跡可能 — 1 つの奇数の頂点から開始し、もう 1 つの頂点で終了する必要があります | オイラーパス |
| 4、6、8... | 一度のストロークではトレースできません | 不可能 |
それだけです。 奇数次の頂点を数えます。 0か2があればパズルは解けます。それ以上だったら無理です。これはと呼ばれます奇数/偶数頂点ルール。
の 学位 頂点の数は、単にそれに接するエッジ (接続) の数です。頂点に 3 つのエッジがある場合、その次数は 3 (奇数) です。エッジが 4 つある場合、次数は 4 (偶数) です。
例：家の形
A (次数 2 ✓ 偶数)
／＼
B---C B (次数 3 ✗ 奇数)
| | C (3度✗奇数)
D---E D (次数 2 ✓ 偶数)
E (次数 2 ✓ 偶数)
2 つの奇数次の頂点 (B および C)
→ オイラー PATH が存在します: B で開始、C で終了✓ はい — オイラー回路。どこからでも始めて、始めた場所で終わります。
✓ はい — 古典的な 1 ストローク チャレンジ。奇数次の頂点が 2 つだけあります。
✓ はい — オイラー回路。すべての頂点が均等なので、どこからでも開始して戻ることができます。
One Stroke アプリが新しいパズルを生成するとき、ランダムにグリッドを作成することはなく、それらが解けることを期待します。代わりに、オイラーの定理を使用して、 数学的に解が保証されているグラフを構築する。
手続き型生成アルゴリズムにより、すべてのパズルに 0 または 2 つの奇数次の頂点が確実に含まれます。つまり、オイラー パスまたはオイラー回路が常に存在します。これが、このゲームが無限に解けるパズルを約束できる理由です。それは運ではなく、数学です。
One Stroke のパズルに行き詰まった場合は、オイラーの法則を適用してみてください。
オイラー パスは、すべてのエッジを正確に 1 回訪れるグラフ内の軌跡です。ある頂点から始まり、別の頂点で終わります。グラフにオイラー パスが含まれるのは、奇数次数の頂点が 2 つだけある場合に限られます。
オイラー パスは、さまざまな頂点で開始および終了し、すべてのエッジを 1 回訪れます。オイラー回路は同じ頂点で開始および終了し、すべてのエッジを 1 回訪問します。オイラー パスには奇数次の頂点が 2 つ必要です。オイラー回路には 0 が必要です。
一筆書きパズルは基本的にオイラー経路の問題です。このパズルでは、すべてのエッジを 1 回正確にトレースするように求められます。これがオイラー パスまたはオイラー回路の定義です。 One Stroke のようなゲームはオイラーの定理を使用して、すべてのパズルに有効な解決策があることを保証します。
いいえ。オイラー パスはすべての場所を訪れます。 エッジ まさに一度。ハミルトニアン パスはあらゆる場所を訪れます。 頂点 まさに一度。これらは関連していますが、異なる概念です。オイラー パスには簡単なテスト (奇数の頂点を数える) があります。ハミルトニアン パスを決定するのは非常に困難です (これは NP 完全問題です)。
無限パズル。適応難易度。強制広告なし。