앱 「소트 퍼즐」은 문제를 내놓기 전에 컴퓨터로 풀 수 있는지 확인해요. 「힌트」의 다음 한 수도 같은 풀이가 찾은 순서의 첫 수예요. 여기서는 그 풀이의 구조를 소개해요.

국면과 수를 따라가기

소트 퍼즐 판의 상태(어느 용기에 무슨 색이 들어 있는지)를 국면이라고 불러요. 한 수 옮기면 다른 국면이 돼요. 처음 국면에서 수를 따라가다가 맞춰진 국면에 닿으면 따라온 길이 답이에요.

가장 소박한 탐색 방법은 1수로 갈 수 있는 국면을 전부, 다음으로 2수로 갈 수 있는 국면을 전부… 이렇게 넓혀 가는 너비 우선 탐색이에요. 반드시 최소 수의 답이 찾아지지만, 색이 많으면 조사할 국면이 엄청나게 많아져요.

다 맞춰질 때까지의 「거리」 기준

그래서 앱은 국면마다 다 맞춰질 때까지의 거리 기준을 세어서 가까워 보이는 국면부터 먼저 조사해요. 기준은 다음 두 가지의 합계예요.

  1. 용기 안의 색이 바뀌는 곳의 수: 아래에서 봤을 때 색이 바뀌는 곳의 수.
  2. 바닥의 겹침: 같은 색이 여러 용기의 바닥에 있다면 그 수에서 1을 뺀 것.
123456

이 판이라면 색이 바뀌는 곳은 1번이 2개, 2번이 2개, 3번이 3개, 4번이 3개로 합쳐서 10. 하늘색이 3번과 4번의 바닥에 있으니 바닥의 겹침이 1. 기준은 11이에요. 맞춰진 국면에서는 바뀌는 곳도 겹침도 없어지므로 기준은 0이 돼요.

기준은 최소 수보다 커지지 않아요

이 기준에는 좋은 성질이 있어요. 1수로 기준은 1보다 많이 줄지 않아요.

  • 붓기 한 번으로 옮기는 쪽 용기의 바뀌는 곳은 많아야 1개밖에 줄지 않아요. 옮겨 가는 곳은 같은 색 위나 빈 용기이므로 바뀌는 곳은 늘지도 줄지도 않아요.
  • 용기가 비어서 바닥의 겹침이 1개 줄어드는 것은 그 용기의 마지막 한 덩어리를 옮겼을 때뿐이고, 그때 바뀌는 곳은 줄지 않아요.

즉 기준이 11인 판은 적어도 11수가 들어요. 여러 판에서 12만 가지 남짓한 수를 조사해도 1수로 기준이 2 이상 줄어드는 수는 없었어요. 위의 판의 최소 수는 딱 11수예요.

가중 A* 탐색

앱은 국면에 「지금까지의 수 + 3 × 기준」이라는 점수를 매기고 점수가 작은 국면부터 먼저 조사해요. 이것을 가중 A*(에이스타) 탐색이라고 해요.

  • 가중치를 1로 하면(보통의 A* 탐색) 기준이 최소 수의 하한이므로 반드시 최소 수의 답이 찾아져요.
  • 가중치를 3으로 하면 기준이 작은 국면을 계속 먼저 조사하므로 답이 훨씬 빨리 찾아져요. 그 대신 최소 수보다 조금 긴 답이 나올 수도 있어요.

앱과 같은 방식으로 만든 문제 20개씩으로, 맞춰질 때까지 조사한 국면의 수와 찾은 답의 수를 비교했어요(★3의 너비 우선 탐색은 국면이 너무 많아서 세지 않았어요).

★1(4색·빈 용기 2)조사한 국면답의 수
너비 우선 탐색53711.8
A*(가중치 1)20311.8
A*(가중치 3)3911.9
★2(6색·빈 용기 2)조사한 국면답의 수
너비 우선 탐색293418.1
A*(가중치 1)62218.1
A*(가중치 3)6418.8

둘 다 20문제의 평균이에요. 가중치 3은 너비 우선 탐색의 수십 분의 1의 국면으로 답을 찾았고, 수의 늘어남은 아주 조금이었어요.

조사하는 수를 줄이는 비결

앱의 풀이는 그 밖에도 다음 비결로 조사하는 국면을 줄여요.

  • 용기의 순서를 구분하지 않기: 용기의 내용물이 같다면 순서가 달라도 같은 국면으로 다뤄요.
  • 의미 없는 수를 조사하지 않기: 한 가지 색뿐인 용기를 빈 용기로 옮기는 수(모양이 바뀌지 않아요)와 두 번째 이후의 빈 용기로 옮기는 수(첫 번째와 같은 국면이 돼요)는 빼요.
  • 「붓기」의 수만으로 찾기: 「쌓기」 문제도 붓는 수로 풀 수 있는지 조사해요(「붓기」와 「쌓기」의 차이).
  • 상한을 정하기: 6만 국면을 조사해도 찾지 못하면 「모르겠다」로 하고 그 배치는 쓰지 않아요.

이 풀이로 문제 만들기의 「풀 수 있는지 확인」(반드시 풀리는 문제 만드는 법)과 「힌트」(힌트 사용법)를 모두 해결해요. 바닥의 색 생각은 어떤 색부터 모을까?에서도 소개해요.