5. 풀이법
페그 솔리테어의 풀이법은 여러 분야에서 연구되었다.[1]
- 파고다 함수: 주어진 문제를 선형 프로그래밍 문제로 만들어 해결할 수 있다.[2]
- 조합 최적화: 1996년 논문에서는 페그 솔리테어 문제를 조합 최적화 문제로 공식화하고 실행 가능한 영역의 속성에 대해 논의했다.[4]
- 전수 조사: 1999년에는 모든 가능한 변형을 전수 조사하여 컴퓨터로 페그 솔리테어를 완전히 해결했다. 대칭성, 효율적인 저장, 해싱을 활용했다.[5]
- 기타 연구: 추상대수학을 사용하여 게임이 하나의 페그로 성공적으로 끝날 수 있는 고정 보드 위치가 5개뿐임을 증명할 수 있다.[6] 1989년의 한 연구에서는 잉글리시 보드의 일반화된 버전을 분석하여 "반전 위치" 문제의 최소 이동 횟수가 11번임을 밝혔다.
삼각 보드 등 다양한 변형 보드에서도 페그 솔리테어가 연구되었다. 변형이 적절한 "패리티"를 가지고 충분히 크다면 풀 수 있을 가능성이 높다.
5. 1. 전략
페그 솔리테어 게임에서 승리하기 위한 몇 가지 전략은 다음과 같다.
- 특정 패턴 활용: 3개의 페그로 이루어진 라인, 2x3 블록, L자 모양 등 특정 패턴을 이용하는 전략이 효과적이다.
- 촉매(catalyst) 페그 활용: 촉매 역할을 하는 페그를 사용하여 여러 페그를 제거할 수 있다. 촉매 페그는 "뛰어 나와" "다시 뛰어 들어가는" 방식으로 활용된다. 아래는 촉매를 활용한 예시이다.
```
'''*''' · o o ·
· → · → → o
· · o
```
이 기술은 3개의 선, 2·3 블록, 그리고 밑변의 길이가 3이고 높이가 4인 6개의 말 L자 모양에 사용할 수 있다.
- 기타 전략:
- 구멍 두 개로 시작하여 해당 구멍에 말 두 개로 끝내기
- "여기"에 구멍 하나로 시작하여 "저기"에 말 하나로 끝내기 (영어 판에서는 구멍은 어디든 있을 수 있으며 최종 말은 3의 배수인 위치에서만 끝날 수 있다. 예를 들어 '''a'''에 있는 구멍은 '''a''', '''p''', '''O''' 또는 '''C'''에서만 단일 말을 남길 수 있다.)
영어 판에서 가능한 초기 이동의 한 예시는 다음과 같다.
{| class="wikitable" style="text-align:center"
|-
|
| | □ | □ | □ | | |
| | □ | ● | ● | | |
| □ | □ | ● | □ | □ | □ | □ |
| □ | □ | ● | ● | ● | □ | □ |
| □ | □ | □ | □ | ● | □ | □ |
| | ● | ● | □ | | |
| | □ | □ | □ | | |
|⇒||
| | □ | □ | □ | | |
| | □ | ● | ● | | |
| □ | □ | ● | □ | □ | □ | □ |
| □ | ● | ← | ○ | ● | □ | □ |
| □ | □ | □ | □ | ● | □ | □ |
| | ● | ● | □ | | |
| | □ | □ | □ | | |
|⇒||
| | □ | □ | □ | | |
| | ○ | ← | ○ | | |
| □ | □ | ↓ | □ | □ | □ | □ |
| □ | ● | ● | □ | ● | □ | □ |
| □ | □ | □ | □ | ● | □ | □ |
| | ● | ● | □ | | |
| | □ | □ | □ | | |
|⇒
|-
|
| | □ | □ | □ | | |
| | □ | □ | □ | | |
| □ | □ | □ | □ | □ | □ | □ |
| □ | ○ | → | ○ | → | ● | □ |
| □ | □ | □ | □ | ● | □ | □ |
| | ● | ● | □ | | |
| | □ | □ | □ | | |
|⇒||
| | □ | □ | □ | | |
| | □ | □ | □ | | |
| □ | □ | □ | □ | □ | □ | □ |
| □ | □ | □ | ● | ← | ○ | □ |
| □ | □ | □ | □ | □ | □ | □ |
| | □ | □ | □ | | |
| | □ | □ | □ | | |
|⇒||
| | □ | □ | □ | | |
| | □ | □ | □ | | |
| □ | □ | □ | □ | □ | □ | □ |
| □ | □ | □ | □ | ● | ● | □ |
| □ | □ | □ | □ | ↑ | □ | □ |
| | ○ | → | ○ | | |
| | □ | □ | □ | | |
|
|}
5. 2. 영국식 게임 풀이 예시
표준 English 게임의 최단 솔루션은 여러 번 점프를 한 번의 움직임으로 계산하여 18번의 움직임을 포함한다.[7] 이 솔루션은 1912년에 Ernest Bergholt에 의해 발견되었고 1964년에 John Beasley에 의해 가능한 최단 솔루션임이 증명되었다.[7]
일부 이동 순서는 서로 바꿀 수 있다. 별표 '''*'''를 구멍으로, '''o'''를 페그로 생각하면 마지막 그림에서 시작하여 첫 번째 그림으로 이동하면서 거꾸로 솔루션을 따라가서 퍼즐을 풀 수 있다. 하지만 이렇게 하려면 18번보다 더 많은 이동이 필요하다.
이 솔루션은 또한 솔루션을 더 쉽게 암기할 수 있도록 설계된 https://web.archive.org/web/20140520101224/http://www.topaccolades.com/notation/solitaire.htm Wolstenholme 표기법을 소개하는 페이지에서도 볼 수 있다.
5. 3. 유럽식 게임 풀이 예시
페그 솔리테어는 혼자서 하는 보드 게임의 일종이다. 초기 비합동 위치에 따라 3가지 해결책이 존재한다.[9]
1)
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | | | | o | · | · |
| · | · | · | · | · |
| · | · | · | · | · | · | · |
| · | · | · | · | · | · | · |
| · | · | · | · | · | · | · |
| · | · | · | · | · |
| | | · | · | · |
가능한 해결책: [2:2-0:2, 2:0-2:2, 1:4-1:2, 3:4-1:4, 3:2-3:4, 2:3-2:1, 5:3-3:3, 3:0-3:2, 5:1-3:1, 4:5-4:3, 5:5-5:3, 0:4-2:4, 2:1-4:1, 2:4-4:4, 5:2-5:4, 3:6-3:4, 1:1-1:3, 2:6-2:4, 0:3-2:3, 3:2-5:2, 3:4-3:2, 6:2-4:2, 3:2-5:2, 4:0-4:2, 4:3-4:1, 6:4-6:2, 6:2-4:2, 4:1-4:3, 4:3-4:5, 4:6-4:4, 5:4-3:4, 3:4-1:4, 1:5-1:3, 2:3-0:3, 0:2-0:4]
2)
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | | | | · | · | · |
| · | · | o | · | · |
| · | · | · | · | · | · | · |
| · | · | · | · | · | · | · |
| · | · | · | · | · | · | · |
| · | · | · | · | · |
| | | · | · | · |
가능한 해결책: [1:1-1:3, 3:2-1:2, 3:4-3:2, 1:4-3:4, 5:3-3:3, 4:1-4:3, 2:1-4:1, 2:6-2:4, 4:4-4:2, 3:4-1:4, 3:2-3:4, 5:1-3:1, 4:6-2:6, 3:0-3:2, 4:5-2:5, 0:2-2:2, 2:6-2:4, 6:4-4:4, 3:4-5:4, 2:3-2:1, 2:0-2:2, 1:4-3:4, 5:5-5:3, 6:3-4:3, 4:3-4:1, 6:2-4:2, 3:2-5:2, 4:0-4:2, 5:2-3:2, 3:2-1:2, 1:2-1:4, 0:4-2:4, 3:4-1:4, 1:5-1:3, 0:3-2:3]
3)
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | | | | · | · | · |
| · | · | · | · | · |
| · | · | · | o | · | · | · |
| · | · | · | · | · | · | · |
| · | · | · | · | · | · | · |
| · | · | · | · | · |
| | | · | · | · |
가능한 해결책: [2:1-2:3, 0:2-2:2, 4:1-2:1, 4:3-4:1, 2:3-4:3, 1:4-1:2, 2:1-2:3, 0:4-0:2, 4:4-4:2, 3:4-1:4, 6:3-4:3, 1:1-1:3, 4:6-4:4, 5:1-3:1, 2:6-2:4, 1:4-1:2, 0:2-2:2, 3:6-3:4, 4:3-4:1, 6:2-4:2, 2:3-2:1, 4:1-4:3, 5:5-5:3, 2:0-2:2, 2:2-4:2, 3:4-5:4, 4:3-4:1, 3:0-3:2, 6:4-4:4, 4:0-4:2, 3:2-5:2, 5:2-5:4, 5:4-3:4, 3:4-1:4, 1:5-1:3]
5. 4. 기타
표준 문제에 대한 해법을 설명하기 위해 구멍에 문자를 할당하는 표기법이 사용된다.
유럽 판에서는 구멍을 특정 위치에서 시작하여 해당 위치의 거울 이미지 위치에 단일 말을 남기는 대체 게임을 할 수 있다. 영어 판에서는 구멍을 시작하여 동일한 위치에 말을 남기는 게임을 할 수 있다.
초기 구멍이 중앙에 위치한 유럽 판에서는 직각으로만 움직일 수 있다면 해법이 없다. 보드의 위치를 A, B, C 위치로 나누면 다음과 같다.
| A B C |
| A B C A B |
| A B C A B C A |
| B C A B C A B |
| C A B C A B C |
| B C A B C |
| A B C |
처음 중앙 위치만 비어 있는 경우 덮인 A, B, C 위치의 수는 각각 12개이다. 모든 움직임 후에 덮인 각 위치의 수는 1만큼 증가하거나 감소한다. 따라서 짝수 번의 움직임 후에는 이 세 숫자가 모두 짝수가 되고, 홀수 번의 움직임 후에는 이 세 숫자가 모두 홀수가 된다. 따라서 마지막 위치에 말 하나만 남는 것은 불가능하다.
그러나 단일 초기 구멍을 단일 말로 줄일 수 있는 다른 구성이 있다. 촉매를 사용하여 패키지를 완전히 제거하는 전술을 사용할 수 있다. 촉매는 "뛰어 나와" "다시 뛰어 들어간다". 아래는 그 예시이다.
'''*''' · o o ·
· → · → → o
· · o
이 기술은 3개의 선, 2·3 블록, 그리고 밑변의 길이가 3이고 높이가 4인 6개의 말 L자 모양에 사용할 수 있다.
다른 대체 게임으로는 구멍 두 개로 시작하여 해당 구멍에 말 두 개로 끝내는 게임, "여기"에 구멍 하나로 시작하여 "저기"에 말 하나로 끝내는 게임이 있다. 영어 판에서는 구멍은 어디든 있을 수 있으며 최종 말은 3의 배수인 위치에서만 끝날 수 있다. 따라서 '''a'''에 있는 구멍은 '''a''', '''p''', '''O''' 또는 '''C'''에서만 단일 말을 남길 수 있다.
