Experimentar One Stroke grátis no iPhone
Quebra-cabeças infinitos. Dificuldade adaptativa. Sem anúncios forçados.
A base matemática de cada quebra-cabeça de um golpe — explicada de forma simples
Um Caminho de Euler (também chamada de trilha euleriana) é um caminho através de um grafo que visitacada aresta exatamente uma vez. Você pode pensar nisso como desenhar cada linha de uma figura sem levantar a caneta e sem refazer nenhuma linha.
A --- B | | C --- D Início: A → Fim: D (diferente) Visita todas as arestas uma vez
Começa e termina às diferente vértices. Requer exatamente 2 vértices de grau ímpar.
Um / \ B---C \/ D Início: A → Fim: A (mesmo) Visita todas as arestas uma vez
Começa e termina no mesmo vértice. Requer 0 vértices de grau ímpar.
A principal diferença: um Euler caminho começa em um vértice e termina em outro. Um Euler circuito começa e termina no mesmo lugar — é um loop completo.
Euler provou um conjunto de regras simples, mas poderoso, para determinar se um gráfico pode ser traçado de uma só vez:
| Vértices de grau ímpar | Resultado | Tipo |
|---|---|---|
| 0 | Rastreável – comece em qualquer lugar e termine onde você começou | Circuito de Euler |
| 2 | Rastreável – deve começar em um vértice ímpar e terminar no outro | Caminho de Euler |
| 4, 6, 8... | Não rastreável de uma só vez | Impossível |
É isso. Conte os vértices de graus ímpares. Se houver 0 ou 2, o quebra-cabeça pode ser resolvido. Se houver mais, é impossível. Isso é chamadoa regra do vértice ímpar/par.
O grau de um vértice é simplesmente o número de arestas (conexões) que o tocam. Se um vértice possui 3 arestas, seu grau é 3 (ímpar). Se tiver 4 arestas, seu grau é 4 (par).
Exemplo: uma forma de casa
A (grau 2 ✓ par)
/ \
B---C B (grau 3 ✗ ímpar)
| | C (grau 3 ✗ ímpar)
D---E D (grau 2 ✓ par)
E (grau 2 ✓ par)
2 vértices de grau ímpar (B e C)
→ Euler PATH existe: começa em B, termina em C✓ Sim - Circuito de Euler. Comece em qualquer lugar, termine onde você começou.
✓ Sim — Desafio clássico de um golpe. Tem exatamente 2 vértices de graus ímpares.
✗ Não — 4 vértices ímpares. Euler provou que isso era impossível em 1736.
✓ Sim - Circuito de Euler. Todos os vértices iguais, para que você possa começar em qualquer lugar e retornar.
Quando o aplicativo One Stroke gera um novo quebra-cabeça, ele não cria grades aleatoriamente e espera que sejam solucionáveis. Em vez disso, usa o teorema de Euler para construir gráficos que tenham uma solução matematicamente garantida.
O algoritmo de geração processual garante que cada quebra-cabeça tenha 0 ou 2 vértices de graus ímpares - o que significa que sempre existe um caminho ou circuito de Euler. É por isso que o jogo pode prometer infinitos quebra-cabeças solucionáveis: não é sorte, é matemática.
Quando você estiver preso em um quebra-cabeça em One Stroke, tente aplicar as regras de Euler:
Um caminho de Euler é uma trilha em um grafo que visita cada aresta exatamente uma vez. Começa em um vértice e termina em um vértice diferente. Um grafo tem um caminho de Euler se e somente se tiver exatamente dois vértices com grau ímpar.
Um caminho de Euler começa e termina em vértices diferentes, visitando cada aresta uma vez. Um circuito de Euler começa e termina no mesmo vértice, visitando também cada aresta uma vez. Um caminho de Euler requer exatamente 2 vértices de graus ímpares; um circuito Euler requer 0.
Os quebra-cabeças de um golpe são essencialmente problemas de caminho de Euler. O quebra-cabeça pede que você trace cada aresta exatamente uma vez – que é a definição de um caminho ou circuito de Euler. Jogos como One Stroke usam o teorema de Euler para garantir que cada quebra-cabeça tenha uma solução válida.
Não. Um caminho de Euler visita cada borda exatamente uma vez. Um caminho hamiltoniano visita cada vértice exatamente uma vez. Eles estão relacionados, mas são conceitos diferentes. Os caminhos de Euler têm um teste simples (contar vértices ímpares); Os caminhos hamiltonianos são muito mais difíceis de determinar (é um problema NP-completo).
Quebra-cabeças infinitos. Dificuldade adaptativa. Sem anúncios forçados.