iPhone에서 One Stroke 무료로 해보기
무한 퍼즐. 적응형 난이도. 강제 광고 없음.
모든 One Stroke 퍼즐의 수학적 기초 - 간단하게 설명
안오일러 경로(오일러 트레일이라고도 함)은 다음을 방문하는 그래프를 통과하는 경로입니다.모든 가장자리는 정확히 한 번씩. 펜을 떼거나 선을 다시 그리지 않고 그림의 모든 선을 그리는 것으로 생각할 수 있습니다.
A --- B | | C --- D 시작 : A → 끝 : D (다름) 모든 Edge를 한 번씩 방문합니다.
시작 및 종료 시간:다른정점. 정확히 필요합니다2개의 홀수 꼭지점.
에이 / \ B---C \ / 디 시작 : A → 끝 : A (동일) 모든 Edge를 한 번씩 방문합니다.
다음에서 시작하고 끝납니다.같은꼭지점. 필요하다0개의 홀수 꼭짓점.
주요 차이점: 오일러길한 꼭지점에서 시작하여 다른 꼭지점에서 끝납니다. 오일러회로같은 위치에서 시작하고 끝나므로 완전한 루프입니다.
오일러는 그래프를 한 번에 추적할 수 있는지 여부를 결정하는 간단하지만 강력한 규칙 집합을 입증했습니다.
| 홀수차 정점 | 결과 | 유형 |
|---|---|---|
| 0 | 추적 가능 — 어디에서나 시작하고 시작한 곳에서 끝납니다. | 오일러 회로 |
| 2 | 추적 가능 — 하나의 홀수 꼭지점에서 시작하고 다른 꼭지점에서 끝나야 합니다. | 오일러 경로 |
| 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에서 끝납니다.✓ 예— 오일러 회로. 어디서든 시작하고, 시작한 곳에서 끝나세요.
✓ 예— 고전적인 One Stroke 챌린지. 홀수차 정점이 정확히 2개 있습니다.
✗ 아니요— 4개의 홀수 정점.오일러는 1736년에 이것이 불가능하다는 것을 증명했습니다.
✓ 예— 오일러 회로. 모든 정점이 균일하므로 어디서든 시작하고 돌아올 수 있습니다.
One Stroke 앱은 새로운 퍼즐을 생성할 때 그리드를 무작위로 생성하지 않고 풀 수 있기를 바랍니다. 대신에 오일러의 정리를 사용합니다.수학적으로 해가 보장되는 그래프를 구성합니다..
절차적 생성 알고리즘은 모든 퍼즐에 0 또는 2개의 홀수차 정점이 있도록 보장합니다. 즉, 오일러 경로 또는 회로가 항상 존재한다는 의미입니다. 이것이 게임이 풀 수 있는 무한한 퍼즐을 약속할 수 있는 이유입니다. 그것은 운이 아니라 수학입니다.
One Stroke에서 퍼즐을 풀지 못할 때 오일러의 규칙을 적용해보세요.
오일러 경로는 모든 가장자리를 정확히 한 번씩 방문하는 그래프의 흔적입니다. 한 꼭지점에서 시작하여 다른 꼭지점에서 끝납니다. 그래프에 홀수 차수의 정점이 정확히 두 개 있는 경우에만 그래프에 오일러 경로가 있습니다.
오일러 경로는 서로 다른 정점에서 시작하고 끝나며 모든 가장자리를 한 번 방문합니다. 오일러 회로는 동일한 정점에서 시작하고 끝나며 모든 가장자리를 한 번 방문합니다. 오일러 경로에는 정확히 2개의 홀수차 정점이 필요합니다. 오일러 회로에는 0이 필요합니다.
One Stroke 퍼즐은 본질적으로 오일러 경로 문제입니다. 퍼즐은 모든 모서리를 정확히 한 번만 추적하도록 요구합니다. 이것이 오일러 경로 또는 회로의 정의입니다. One Stroke와 같은 게임은 오일러의 정리를 사용하여 모든 퍼즐에 유효한 답이 있음을 보장합니다.
아니요. 오일러 경로는 매번 방문합니다.가장자리정확히 한 번. 해밀턴 경로는 매일 방문합니다.꼭지점정확히 한 번. 서로 관련되어 있지만 다른 개념입니다. 오일러 경로에는 간단한 테스트가 있습니다(홀수 정점 계산). 해밀턴 경로는 결정하기가 훨씬 어렵습니다(NP 완전 문제입니다).
무한 퍼즐. 적응형 난이도. 강제 광고 없음.