앱 「페그 솔리테어」의 「문제」 모드에서는 「새 게임」을 누를 때마다 모양이 다른 판이 만들어져요. 그런데도 어느 판이든 반드시 풀 수 있어요. 이 글에서는 그 구조를 소개해요.

보통 방식으로 만들면 풀 수 있는지 알 수 없어요

구멍의 모양과 공을 놓는 법을 제멋대로 정하면 풀 수 없는 판이 많이 생겨요. 풀 수 있는지 확인하려면 모든 수를 조사해야 하는데, 공이 많으면 시간이 걸려요.

그래서 앱은 답에서 거꾸로 문제를 만드는 방법을 써요.

거꾸로 뛰기

페그 솔리테어의 한 수는 「공이 옆의 공을 뛰어넘어 빈 구멍으로 뛰고, 뛰어넘은 공을 잡는」 동작이에요. 이것을 거꾸로 하면

공이 두 칸 앞의 빈 구멍으로 돌아가고, 사이의 빈 구멍에 공을 하나 놓는다

는 동작이 돼요. 거꾸로 한 수마다 공이 하나씩 늘어나요.

대장 공 하나에서 시작해요

거꾸로 하는 수를 대장 공이 하나만 남은 판(즉 클리어한 판)에서부터 쌓아 가요. 작은 예로 살펴봐요.

먼저 대장 공만 있는 판이에요.

1번째: 대장 공을 두 칸 위로 돌려놓고 사이에 공을 놓아요.

2번째: 사이에 놓은 공을 두 칸 왼쪽으로 돌려놓고 그 사이에 공을 놓아요.

3번째: 대장 공을 두 칸 오른쪽으로 돌려놓고 사이에 공을 놓아요.

이렇게 공 4개의 문제가 만들어졌어요.

거꾸로 따라간 수가 그대로 답이에요

만든 수를 마지막부터 차례로 보통 방향으로 두면 그대로 답이 돼요. 위의 예에서 쓴 구멍만 판의 구멍으로 삼아 문제의 판으로 만들면 다음과 같이 풀려요.

  1. 1번째 수 e1→c1
  2. 2번째 수 a2→c2
  3. 3번째 수 c1→c3
  4. 3번째 수 뒤 남은 공 1개

거꾸로 만든 수순은 원래 클리어한 판에서 시작했기 때문에 보통 방향으로 따라가면 반드시 대장 공만 남아요. 그래서 어느 문제에나 적어도 하나의 답이 있다는 것이 보장돼요.

앱에서의 궁리

앱에서는 이 만드는 법에 몇 가지 궁리를 더했어요.

  • 구멍을 돌려 쓰기: 거꾸로 하는 수를 고를 때 이미 쓴 구멍을 다시 쓰는 수를 고르기 쉽게 해 둬요. 수순이 얽혀서 그저 일직선으로 늘어선 문제가 되기 어려워져요.
  • 판 모양 다듬기: 만들어진 판의 절반은 구멍을 더해 좌우 대칭 모양으로 만들어요. 나머지는 판 가장자리에 빈 구멍을 1~2개 더해 모양을 바꿔요. 빈 구멍을 더해도 원래의 답은 그대로 둘 수 있어서 풀 수 있다는 점은 변하지 않아요.
  • 같은 씨앗에서는 같은 문제: 문제는 「씨앗」이라고 부르는 수에서 만들기 때문에 같은 씨앗과 난이도에서는 iPhone에서도 Android에서도 같은 문제가 만들어져요.

난이도를 조사하고 맞지 않으면 다시 만들어요

거꾸로 만든 문제에는 답이 반드시 있어요. 하지만 그것만으로는 너무 쉽거나 너무 어려울 수 있어요.

그래서 앱은 만든 문제를 답의 수순 중간에서 두면 더는 대장 공을 남길 수 없게 되는 수(함정 수)가 얼마나 있는지로 조사해요. 함정 수의 비율이 ★1~★5 각각의 범위에 들어갈 때까지 최대 24번 다시 만들어요(범위는 난이도 글).

★5 명인의 문제(공 27~32개)도 만드는 데 걸리는 시간은 개발에 쓰는 Mac에서 평균 0.6초쯤이에요. 게다가 난이도마다 3문제씩 미리 만들어 두고, 쓰면 뒤에서 만들어 채우기 때문에 하는 사람이 기다리는 일은 거의 없어요.

답은 하나라고는 할 수 없어요

거꾸로 만든 수순은 답의 하나예요. 같은 판에 다른 답이 여러 개 있는 일도 흔해요. 웹에서 바로 해 보는 페이지의 「대장 공 연습」 판도 같은 생각으로 만든 것이고, 공 16개의 판에는 300만 가지가 넘는 푸는 방법이 있어요(푸는 방법은 몇 가지?).

앱의 「힌트」는 만들었을 때의 답을 기억하고 있어서 답의 길 위에서는 바로 다음 한 수를 알려 줄 수 있어요. 길에서 벗어났을 때는 푸는 방법을 찾는 프로그램이 다른 길을 찾아요(컴퓨터로 풀기).