페그 솔리테어의 답은 컴퓨터로 찾을 수 있어요. 앱 「페그 솔리테어」의 「힌트」도, 이 사이트에서 답을 확인할 때도 같은 생각의 프로그램을 써요. 여기서는 그 구조를 쉽게 소개해요.
모든 수를 차례로 시도해요
가장 단순한 방법은 둘 수 있는 수를 하나 골라 두고, 또 둘 수 있는 수를 하나 골라 두는 일을 되풀이하는 거예요. 막히면 한 수 되돌려서 아직 시도하지 않은 다른 수를 골라요.
- 지금 판 상태에서 둘 수 있는 수를 하나 골라 둔다.
- 공이 하나가 되면 답을 찾은 것이다.
- 둘 수 있는 수가 없어지면 한 수 되돌려서 다른 수를 시도한다.
- 어느 수든 다 시도했다면 한 수 더 되돌린다.
이 방법을 깊이 우선 탐색이라고 해요. 사람이 「한 수 되돌리기」를 써서 시도하는 것과 같은 일을 엄청난 속도로 되풀이해요.
같은 판 상태를 여러 번 조사하지 않아요
페그 솔리테어에서는 다른 순서로 두어도 같은 판 상태가 되는 일이 자주 있어요. 영국식 33구멍에서는 7수째 뒤의 두는 방법이 22만 가지를 넘지만 만들어지는 판 상태는 2만 2천 종류쯤이에요(푸는 방법은 몇 가지?).
그래서 한 번 조사해서 막다른 길이라고 알게 된 판 상태를 기억해 두고 다시 만나면 바로 되돌아가요. 이것만으로 조사하는 양이 크게 줄어요.
이 글의 사이트에서 쓴 프로그램에서는 영국식 33구멍을 한가운데에서 시작해 한가운데에 남기는 답이 순식간에(0.1초도 걸리지 않고) 발견되었어요. 다만 항상 빠른 것은 아니에요. 2수째를 바꾼 판에서 같은 방식으로 찾았더니 9초쯤 걸렸어요. 어느 수부터 시도하느냐에 따라 걸리는 시간이 크게 달라져요.
앞을 읽지 않고 중단해요
또 하나의 궁리는 이 판 상태에서는 어떻게 두어도 목표에 닿을 수 없다는 것을 알게 되면 그 앞을 조사하지 않고 중단하는 거예요. 이것을 「가지치기」라고 해요.
앱에서는 다음 두 가지로 가지를 쳐요.
- 3색 칠하기: 판을 대각선으로 3색으로 칠하면 한 수마다 3색 모두의 공 수의 짝수·홀수가 뒤바뀌어요. 그래서 지금 판 상태에서 마지막 하나를 남길 수 있는 구멍을 계산만으로 알 수 있어요(3색 칠하기 글).
- 대장 공의 행과 열: 대장 공은 한 번에 두 칸씩 움직이기 때문에 있는 구멍의 행과 열의 짝수·홀수가 변하지 않아요(대장 공을 마지막에 남기는 요령).
두 조건을 모두 만족하는 구멍이 판에 하나도 없게 되면 대장 공을 마지막에 남길 수 있는 구멍은 없어요. 그 판 상태는 앞을 읽을 것도 없이 「풀 수 없다」는 것을 알 수 있어요.
앱의 「힌트」에서는
앱의 「힌트」는 지금 판 상태에서 목표에 닿을 수 있는 다음 한 수를 찾아서 금색 고리로 빛내 줘요.
- 문제의 답을 먼저 기억해 둬요: 「문제」의 판은 거꾸로 뛰어서 만들기 때문에 만들 때의 답을 알고 있어요(반드시 풀 수 있는 문제를 만드는 법). 그 답의 길 위에 있는 판 상태는 「풀 수 있다」고 기억해 두기 때문에 바로 대답할 수 있어요. 길에서 벗어난 판 상태에서도 찾다가 답의 길에 합류하면 거기서 멈출 수 있어요.
- 조사하는 양에 상한을 둬요: 한 번의 힌트에서 조사하는 것은 150만 판 상태나 3초까지예요. 큰 판에서는 그 안에 답이 나오지 않을 수도 있어요.
- 되돌릴 수를 알려 줘요: 지금 판 상태에서 더는 목표에 닿을 수 없을 때나 상한까지 알아내지 못했을 때는 「한 수 되돌리기」로 돌아갈 수 있는 판 상태를 조사해서 「3수 되돌리면 남길 수 있어요」처럼 몇 수 되돌리면 되는지 알려 줘요. 돌아갈 수 있는 판 상태를 절반씩 좁혀 가며 조사하기 때문에 수가 많아도 빨리 찾을 수 있어요.
사람이 풀 때의 힌트
컴퓨터의 궁리는 사람이 풀 때도 쓸 수 있어요.
- 막다른 모양을 외워 둬요: 한 번 실패한 모양은 다른 순서로 도달해도 역시 실패해요.
- 목표에서 생각해요: 마지막에 남길 수 있는 구멍은 처음부터 정해져 있어요. 목표로 할 구멍을 먼저 정하면 수를 고르기 쉬워져요(한가운데에 남기려면).
- 되돌려서 시도해요: 깊이 우선 탐색처럼 헤맬 때 조금 되돌려서 다른 수를 시도하는 것은 올바른 방법이에요.
