Probar One Stroke gratis en iPhone
Puzles infinitos. Dificultad adaptativa. Sin anuncios forzados.
La base matemática de cada rompecabezas de un solo golpe, explicada de forma sencilla
UnCamino de Euler(también llamado sendero Euleriano) es un camino a través de un grafo que visitacada borde exactamente una vez. Puedes pensar en ello como dibujar cada línea de una figura sin levantar el bolígrafo y sin volver a trazar ninguna línea.
A --- B | | C---D Inicio: A → Fin: D (diferente) Visita cada borde una vez
Comienza y termina endiferentevértices. Requiere exactamente2 vértices de grado impar.
un /\ B---C \ / re Inicio: A → Fin: A (igual) Visita cada borde una vez
Comienza y termina en elmismovértice. Requiere0 vértices de grado impar.
La diferencia clave: un Eulercaminocomienza en un vértice y termina en otro. un eulercircuitocomienza y termina en el mismo lugar: es un bucle completo.
Euler demostró un conjunto de reglas simple pero poderoso para determinar si una gráfica se puede trazar de un solo trazo:
| Vértices de grados impares | Resultado | Tipo |
|---|---|---|
| 0 | Trazable: comienza en cualquier lugar y termina donde empezaste | Circuito de Euler |
| 2 | Trazable: debe comenzar en un vértice impar y terminar en el otro. | Camino de Euler |
| 4, 6, 8... | No rastreable de un solo golpe | Imposible |
Eso es todo.Cuente los vértices de grados impares.Si hay 0 o 2, el rompecabezas se puede resolver. Si hay más, es imposible. esto se llamala regla del vértice par/impar.
Elgradode un vértice es simplemente el número de aristas (conexiones) que lo tocan. Si un vértice tiene 3 aristas, su grado es 3 (impar). Si tiene 4 aristas, su grado es 4 (par).
Ejemplo: la forma de una casa
A (grado 2 ✓ par)
/\
B---C B (grado 3 ✗ impar)
| | C (grado 3 ✗ impar)
D---E D (grado 2 ✓ par)
E (grado 2 ✓ par)
2 vértices de grado impar (B y C)
→ Euler PATH existe: comienza en B, termina en C✓ Sí— Circuito de Euler. Comienza en cualquier lugar y termina donde empezaste.
✓ Sí— Desafío clásico de un solo golpe. Tiene exactamente 2 vértices de grado impar.
✗No— 4 vértices impares.Euler demostró que esto era imposible en 1736.
✓ Sí— Circuito de Euler. Todos los vértices son iguales, por lo que puedes empezar en cualquier lugar y regresar.
Cuando la aplicación One Stroke genera un nuevo rompecabezas, no crea cuadrículas al azar y espera que se puedan resolver. En cambio, utiliza el teorema de Euler paraConstruir gráficas que matemáticamente garanticen que tendrán una solución..
El algoritmo de generación de procedimientos garantiza que cada rompecabezas tenga 0 o 2 vértices de grado impar, lo que significa que siempre existe una ruta o circuito de Euler. Es por eso que el juego puede prometer infinitos acertijos solucionables: no es suerte, son matemáticas.
Cuando estés atrapado en un rompecabezas en One Stroke, intenta aplicar las reglas de Euler:
Un camino de Euler es un sendero en un gráfico que visita cada borde exactamente una vez. Comienza en un vértice y termina en otro vértice diferente. Un grafo tiene un camino de Euler si y sólo si tiene exactamente dos vértices con grado impar.
Un camino de Euler comienza y termina en diferentes vértices, visitando cada borde una vez. Un circuito de Euler comienza y termina en el mismo vértice, visitando también cada arista una vez. Un camino de Euler requiere exactamente 2 vértices de grados impares; un circuito de Euler requiere 0.
Los acertijos de un solo golpe son esencialmente problemas del camino de Euler. El rompecabezas te pide que traces cada borde exactamente una vez, que es la definición de un camino o circuito de Euler. Juegos como One Stroke utilizan el teorema de Euler para garantizar que cada rompecabezas tenga una solución válida.
No. Un camino de Euler visita cadabordeexactamente una vez. Un camino hamiltoniano visita cadavérticeexactamente una vez. Son conceptos relacionados pero diferentes. Los caminos de Euler tienen una prueba simple (cuenta los vértices impares); Los caminos hamiltonianos son mucho más difíciles de determinar (es un problema NP completo).
Puzles infinitos. Dificultad adaptativa. Sin anuncios forzados.