소트 퍼즐을 푸는 데 최소 몇 수가 들까요? 앱 「소트 퍼즐」의 ★1(4색·빈 용기 2) 크기라면 배치를 전부 조사할 수 있어요. 「붓기」의 수로 모든 배치의 최소 수를 세어 봤어요.
조사 방법
- 같은 색이 3개 이상 이어진 용기가 없는 「공정한 배치」만 조사해요(앱이 내놓는 것은 이 배치뿐이에요).
- 용기의 순서만 바꾼 배치나 색만 바꿔 칠한 배치는 같은 것으로 봐요. 그러면 89,675종류가 돼요(나누는 방법은 몇 가지?).
- 각 배치에서 1수로 갈 수 있는 국면, 2수로 갈 수 있는 국면…을 전부 펼쳐서 처음으로 맞춰지는 수를 구해요(너비 우선 탐색).
최소 수의 분포
| 최소 수 | 배치의 종류 |
|---|---|
| 5수 | 3 |
| 6수 | 8 |
| 7수 | 124 |
| 8수 | 741 |
| 9수 | 3,523 |
| 10수 | 11,070 |
| 11수 | 21,321 |
| 12수 | 26,778 |
| 13수 | 19,271 |
| 14수 | 6,635 |
| 15수 | 197 |
| 16수 | 4 |
가장 많은 것은 12수이고, 10~13수가 전체의 8할 이상이에요. 5수로 풀리는 배치는 3종류, 16수가 드는 배치는 4종류뿐이에요.
(여기서의 수는 「종류」예요. 앱에서 실제로 나올 확률은 종류마다 조금씩 달라요.)
가장 짧은 판(5수)
어느 용기든 같은 색이 2개씩 겹쳐 있어요. 빈 용기 2개를 써서 5수로 맞춰져요.
가장 수가 많이 드는 판(16수)
1번과 2번, 3번과 4번이 완전히 같은 배열이에요. 어느 용기든 이웃한 색이 모두 다르고, 빨강과 연두는 각각 2개 용기의 바닥에 있어요.
16수 풀이 보기
수의 하한 찾기
최소 수는 전부 조사하지 않아도 하한(이보다 적을 수는 없는 수)이라면 판을 보기만 해도 알 수 있어요.
- 용기 안의 색이 바뀌는 곳의 수를 세요.
- 같은 색이 여러 용기의 바닥에 있다면 「그 수-1」을 더해요.
이 합계는 붓기 한 번에 많아야 1밖에 줄지 않으므로 최소 수보다 커지지 않아요(컴퓨터로 풀기).
- 5수의 판: 바뀌는 곳이 4개이고, 빨강이 2개 용기의 바닥에 있으니 1을 더해서 하한은 5. 딱 최소 수예요.
- 16수의 판: 바뀌는 곳이 12개이고, 빨강과 연두가 각각 2개 용기의 바닥에 있으니 2를 더해서 하한은 14. 실제로는 16수가 들어요.
89,675종류 중 하한과 최소 수가 딱 일치한 것은 38,571종류(약 43%) 였어요. 나머지는 하한보다 많이 들어요.
더 큰 판에서는
색이 늘면 배치가 너무 많아서 전부는 조사할 수 없어요. 앱과 같은 방식으로 만든 문제 20개씩의 최소 수의 평균은 ★1이 11.8수, ★2(6색)가 18.1수였어요. ★3 이상은 문제 하나의 최소 수를 구하는 데도 시간이 걸려요.
앱의 「힌트」는 최소 수가 아니라 빨리 찾은 푸는 방법을 알려 줘요. 최소 수에 도전한다면 하한을 기준으로 스스로 순서를 생각해 보세요(힌트 사용법).
