Essayer One Stroke gratuitement sur iPhone
Puzzles infinis. Difficulté adaptative. Aucune pub forcée.
Le fondement mathématique de chaque puzzle en un seul coup - expliqué simplement
Un chemin d'Euler (également appelé sentier eulérien) est un chemin à travers un graphique qui visitechaque bord exactement une fois. Vous pouvez imaginer que cela consiste à tracer chaque ligne d’une figure sans lever votre stylo et sans retracer aucune ligne.
A --- B | | C---D Début : A → Fin : D (différent) Visite chaque bord une fois
Commence et se termine à différent sommets. Nécessite exactement 2 sommets de degrés impairs.
Un /\ B---C \/ ré Début : A → Fin : A (idem) Visite chaque bord une fois
Commence et se termine au pareil sommet. Nécessite 0 sommet de degré impair.
La principale différence : un Euler chemin commence à un sommet et se termine à un autre. Un Euler circuit commence et se termine au même endroit – c'est une boucle complète.
Euler a prouvé un ensemble de règles simples mais puissantes pour déterminer si un graphique peut être tracé d'un seul coup :
| Sommets de degrés impairs | Résultat | Tapez |
|---|---|---|
| 0 | Traçable : commencez n'importe où, terminez là où vous avez commencé | Circuit d'Euler |
| 2 | Traçable : doit commencer à un sommet impair et se terminer à l'autre | Chemin d'Euler |
| 4, 6, 8... | Non traçable d'un seul coup | Impossible |
C'est tout. Comptez les sommets de degrés impairs. S’il y en a 0 ou 2, le puzzle peut être résolu. S'il y en a plus, c'est impossible. Ceci s'appellela règle des sommets impairs/pairs.
Le diplôme d'un sommet est simplement le nombre d'arêtes (connexions) qui le touchent. Si un sommet a 3 arêtes, son degré est 3 (impair). S'il a 4 arêtes, son degré est 4 (pair).
Exemple : une forme de maison
A (degré 2 ✓ pair)
/\
B---C B (degré 3 ✗ impair)
| | C (degré 3 ✗ impair)
D---E D (degré 2 ✓ pair)
E (degré 2 ✓ pair)
2 sommets de degrés impairs (B et C)
→ Euler PATH existe : commence en B, fin en C✓ Oui — Circuit d'Euler. Commencez n’importe où, terminez là où vous avez commencé.
✓ Oui — Défi classique en un seul coup. A exactement 2 sommets de degrés impairs.
✗ Non — 4 sommets impairs. Euler prouva cela impossible en 1736.
✓ Oui — Circuit d'Euler. Tous les sommets sont égaux, vous pouvez donc commencer n'importe où et revenir.
Lorsque l'application One Stroke génère un nouveau puzzle, elle ne crée pas de grilles au hasard et espère qu'elles pourront être résolues. Au lieu de cela, il utilise le théorème d'Euler pour construire des graphiques dont la solution est mathématiquement garantie.
L'algorithme de génération procédurale garantit que chaque puzzle comporte 0 ou 2 sommets de degré impair, ce qui signifie qu'un chemin ou un circuit d'Euler existe toujours. C'est pourquoi le jeu peut promettre des énigmes infinies à résoudre : ce n'est pas de la chance, c'est des mathématiques.
Lorsque vous êtes bloqué sur une énigme dans One Stroke, essayez d'appliquer les règles d'Euler :
Un chemin d'Euler est un chemin dans un graphique qui visite chaque arête exactement une fois. Il commence à un sommet et se termine à un autre sommet. Un graphe a un chemin d’Euler si et seulement s’il a exactement deux sommets de degré impair.
Un chemin d'Euler commence et se termine à différents sommets, visitant chaque arête une fois. Un circuit d'Euler commence et se termine au même sommet, visitant également chaque arête une fois. Un chemin d'Euler nécessite exactement 2 sommets de degré impair ; un circuit Euler nécessite 0.
Les énigmes à un coup sont essentiellement des problèmes de chemin d’Euler. Le puzzle vous demande de tracer chaque arête exactement une fois, ce qui est la définition d'un chemin ou d'un circuit d'Euler. Des jeux comme One Stroke utilisent le théorème d'Euler pour garantir que chaque puzzle a une solution valide.
Non. Un chemin d'Euler visite chaque bord exactement une fois. Un chemin hamiltonien visite chaque sommet exactement une fois. Ce sont des concepts liés mais différents. Les chemins d'Euler ont un test simple (compter les sommets impairs) ; Les chemins hamiltoniens sont beaucoup plus difficiles à déterminer (c'est un problème NP-complet).
Puzzles infinis. Difficulté adaptative. Aucune pub forcée.