프리셀은 모든 카드가 보이니까 컴퓨터로 푸는 방법을 찾기에 알맞은 게임이에요. 여기서는 컴퓨터가 프리셀을 어떻게 푸는지 쉽게 소개해요. 이 페이지를 위해 앱 「프리셀」과 같은 규칙으로 움직이는 프로그램을 만들어 시험해 봤어요.
탐색: 수를 두면서 앞을 조사하기
컴퓨터는 사람처럼 「이 수를 두면 어떻게 될까」를 조사해요. 다른 건 그 수의 많음이에요.
- 지금 판에서 둘 수 있는 수를 전부 적어 낸다(프리셀에 놓기, 열에 겹치기, 홈셀에 쌓기 등).
- 수 하나를 두어 새 판을 만든다.
- 그 판에서 다시 둘 수 있는 수를 전부 적어 낸다.
- 홈셀에 52장을 쌓은 판이 나오면 거기까지의 순서가 답이다.
이렇게 「판에서 판으로 가지를 치며 따라가는 것」을 탐색이라고 해요.
방법 1: 같은 판을 두 번 조사하지 않기
프리셀에서는 다른 순서로 움직여도 같은 판에 이르는 일이 자주 있어요. 카드를 오른쪽으로 움직였다가 다시 왼쪽으로 되돌리면 원래 판이에요. 한 번 조사한 판을 기억해 두고 같은 판이 나오면 조사하지 않으면 낭비가 크게 줄어요.
게다가 열의 순서만 다른 판이나 프리셀 안의 배열만 다른 판도 푸는 방법은 같아요. 이런 것들을 같은 판으로 다루면 조사하는 수를 더 줄일 수 있어요.
방법 2: 가능성이 높은 판부터 조사하기
모든 판을 차례로 조사하면 시간이 너무 오래 걸려요. 그래서 「홈셀에 쌓은 장수가 많다」 「다음에 홈셀에 쌓고 싶은 카드 위에 놓인 장수가 적다」 「프리셀이 비어 있다」 같은 점수를 매겨서 가능성이 높은 판부터 먼저 조사해요.
이 페이지의 프로그램으로 Windows 프리셀 1번 배치를 풀게 하면 843개의 판을 조사한 시점에 110수의 풀이를 찾았어요. 사람이 생각하면 힘들어도 컴퓨터에게는 순식간이에요. 찾은 순서가 가장 짧은 순서라고는 할 수 없어요(이동 횟수와 클리어의 수).
풀 수 없다는 걸 확인하기
푸는 방법을 찾으면 그 배치는 풀 수 있어요. 그럼 「풀 수 없다」는 건 어떻게 확인할까요?
답은 갈 수 있는 판을 전부 조사하는 것이에요. 어떤 수를 두어도 더는 새 판이 나오지 않고, 그래도 52장을 쌓은 판이 없으면 그 배치는 풀 수 없다는 걸 알 수 있어요.
Windows 프리셀의 11982번은 풀 수 없는 배치로 알려져 있어요. 이 페이지의 프로그램에서도 11982번은 홈셀에서 되돌리는 수까지 포함해 갈 수 있는 판(약 9만 5천 개)을 전부 조사해도 푸는 방법이 없었어요(프리셀은 거의 풀 수 있어요).
한꺼번에 옮기는 규칙은 풀 수 있는지와 상관없어요
앱 「프리셀」에서 한 번에 옮길 수 있는 건 「비어 있는 프리셀 수+1」장까지이고 빈 열에서는 늘지 않아요(한꺼번에 옮길 수 있는 장수). 하지만 한꺼번에 옮기는 수는 프리셀이나 빈 열을 쓴 한 장씩의 수로 나눌 수 있어요. 갈 수 있는 판은 같으니 풀 수 있는 배치는 같아요. 달라지는 건 이동 횟수를 세는 방법뿐이에요.
앱 「프리셀」의 카드 배치 검산
앱 「프리셀」의 카드 배치는 매번 무작위로 섞어서 나눠 줘요. 만든 사람은 무작위로 만든 10만 가지 배치를 컴퓨터로 풀고, 찾은 풀이를 앱과 같은 게임 구조로 실제로 끝까지 둬서 확인했어요. 결과는 10만 가지 모두에 푸는 방법이 있었어요.
다만 이것이 「모든 배치를 풀 수 있다」는 증명은 아니에요. 조사하지 않은 배치 중에 풀 수 없는 것이 드물게 있을 가능성은 남아요.
푸는 생각법은 사람이 할 때도 도움이 돼요. 프리셀 공략과 필승법도 읽어 보세요.
