CC — Clément Chardine

‘Make 10’ 게임을 브루트 포스로 풀기

게시일 4 분 분량 알고리즘 · 퍼즐

모든 네 자리 입력(0000–9999)에 대해 ‘Make 10’ 퍼즐을 브루트 포스로 푸는 작은 프로젝트. 규칙, 허용한 연산, 그리고 솔버의 결과를 소개합니다.

얼마 전 유튜브인지 인스타그램인지의 쇼츠에서 누군가 시드니 기차 게임을 푸는 영상을 봤습니다. 규칙은 간단합니다. 객차 번호의 네 숫자를 사칙연산으로 조합해 24를 만드는 거죠. 몇 가지 예시를 풀어 봤는데, 대부분 너무 쉬웠습니다. 그래서 좀 더 도전적인 걸 원했어요.

난이도를 올리려고 목표를 24에서 약수가 더 적은 10으로 바꾸고, 순서를 지키는 연산만 허용했습니다(즉, 숫자의 순서를 바꿀 수 없습니다). 이런 변형을 떠올린 게 제가 처음은 아니겠지만, 더 나은 이름이 없으니 ‘Make 10’ 게임이라고 부르겠습니다.

한동안 머리를 싸맸지만, 개발자로서 당연히 이 풀이를 자동화하는 데 시간을 쓸 수밖에 없었습니다.

그 결과물이 모든 네 자리 입력(0000부터 9999까지)에 대해 목표 숫자 10에 도달하는 모든 연산 조합을 탐색하는 브루트 포스 솔버입니다. 아래에서 제가 정한 규칙과 허용한 연산을 설명하고, 솔버의 결과를 공유합니다.

규칙

목표는 항상 10입니다. 입력은 네 자리 숫자 문자열입니다. 순서는 바꿀 수 없습니다. 네 숫자를 모두 정확히 한 번씩 써야 합니다.

연산

퍼즐이 어렵되 풀 수는 있도록 하고 싶었습니다.

원래 게임의 정신을 지키기 위해, 왼쪽에서 오른쪽으로 의심의 여지 없이 읽을 수 있는 연산만 허용했습니다(그래서 나눗셈을 흔치 않은 빗금으로 표기했습니다).

재미있으면서도 풀 수 있게 만들려면 표준 연산자 집합을 넓혀야 했습니다. 사칙연산만으로는 탐색 공간을 다 채울 수 없지만, 그렇다고 무한한 복잡도를 허용하고 싶지도 않았습니다.

허용한 연산은 다음과 같습니다.

간단한 산수 게임에서 이런 연산 중 일부(계승이나 로그 같은)는 조금 ‘반칙’처럼 느껴질 수 있다는 걸 압니다. 하지만 흥미로운 복잡도를 더해 주고, 목표 숫자에 도달하는 길을 더 많이 열어 줍니다. 처음 시도했을 때 입력의 약 10%는 사칙연산만으로는 풀 수 없었기 때문에, 더 많은 입력에 해답을 찾으려면 이 추가 연산들이 필요했습니다.

아래는 솔버가 모든 네 자리 입력에 대해 찾아낸 해답의 전체 목록입니다. 인터랙티브 목록에는 각 입력에 대해 찾은 가장 간단한 식이 들어 있습니다.

전체 10,000개 중 10,000개

  1. 0000((0! + 0!) · (0! + 0!))?
  2. 0001((0! + 0!) · (0! + 1))?
  3. 00020 + 0 + (0! + 2?)?
  4. 00030 + 0 + (0! + 3)?
  5. 0004(0! + 0!) · (0! + 4)
  6. 0005(0! + 0!) / (0! / 5)
  7. 0006(0! + 0!) · |(0! - 6)|
  8. 00070! + 0! + 0! + 7
  9. 00080! + 0! - (0 - 8)
  10. 00090 + 0! - (0 - 9)
  11. 0010((0! + 0!) · (1 + 0!))?
  12. 0011((0! + 0!) · (1 + 1))?

구현

코드 자체는 혁신적인 게 전혀 없습니다. 식 트리를 만드는 브루트 포스 깊이 우선 탐색입니다. 가장 큰 어려움은 수학이 아니라 기계의 한계였습니다.

  1. 종료: 계승과 삼각수를 중첩하면 금세 오버플로가 납니다. 코드가 우주의 열적 죽음까지 돌아가지 않도록 탐색 깊이를 과감하게 제한해야 했습니다.
  2. 서식: 출력이 ASCII 죽처럼 보이지 않도록 LaTeX 서식과 씨름하는 데 터무니없이 많은 시간을 썼습니다.
  3. 휴리스틱: 그냥 아무 해답이 아니라 가장 간단한 해답을 원했습니다. 삼각수 연산자나 중첩된 제곱근 같은 ‘대량 살상 무기’보다 기본 산술(+, -)을 선호하도록 솔버에 가중치를 줬습니다. 정말 필요할 때만 중화기를 꺼내도록요(적어도 그러려고 노력했습니다).

그리고 혹시 나머지 연산(mod)이나 삼각수 연산자(?)에 기대지 않는 더 간단한 해답을 찾으신다면 꼭 알려 주세요. 반영하겠습니다.

다른 실험들