‘Make 10’ 게임을 브루트 포스로 풀기
모든 네 자리 입력(0000–9999)에 대해 ‘Make 10’ 퍼즐을 브루트 포스로 푸는 작은 프로젝트. 규칙, 허용한 연산, 그리고 솔버의 결과를 소개합니다.
얼마 전 유튜브인지 인스타그램인지의 쇼츠에서 누군가 시드니 기차 게임을 푸는 영상을 봤습니다. 규칙은 간단합니다. 객차 번호의 네 숫자를 사칙연산으로 조합해 24를 만드는 거죠. 몇 가지 예시를 풀어 봤는데, 대부분 너무 쉬웠습니다. 그래서 좀 더 도전적인 걸 원했어요.
난이도를 올리려고 목표를 24에서 약수가 더 적은 10으로 바꾸고, 순서를 지키는 연산만 허용했습니다(즉, 숫자의 순서를 바꿀 수 없습니다). 이런 변형을 떠올린 게 제가 처음은 아니겠지만, 더 나은 이름이 없으니 ‘Make 10’ 게임이라고 부르겠습니다.
한동안 머리를 싸맸지만, 개발자로서 당연히 이 풀이를 자동화하는 데 시간을 쓸 수밖에 없었습니다.
그 결과물이 모든 네 자리 입력(0000부터 9999까지)에 대해 목표 숫자 10에 도달하는 모든 연산 조합을 탐색하는 브루트 포스 솔버입니다. 아래에서 제가 정한 규칙과 허용한 연산을 설명하고, 솔버의 결과를 공유합니다.
규칙
목표는 항상 10입니다. 입력은 네 자리 숫자 문자열입니다. 순서는 바꿀 수 없습니다. 네 숫자를 모두 정확히 한 번씩 써야 합니다.
연산
퍼즐이 어렵되 풀 수는 있도록 하고 싶었습니다.
원래 게임의 정신을 지키기 위해, 왼쪽에서 오른쪽으로 의심의 여지 없이 읽을 수 있는 연산만 허용했습니다(그래서 나눗셈을 흔치 않은 빗금으로 표기했습니다).
재미있으면서도 풀 수 있게 만들려면 표준 연산자 집합을 넓혀야 했습니다. 사칙연산만으로는 탐색 공간을 다 채울 수 없지만, 그렇다고 무한한 복잡도를 허용하고 싶지도 않았습니다.
허용한 연산은 다음과 같습니다.
- 기본: 덧셈, 뺄셈, 곱셈, 나눗셈.
- 거듭제곱과 제곱근: 거듭제곱, 제곱근, n제곱근.
- 함수: 로그, 계승, 나머지 연산, 절댓값.
- 삼각수 연산자: 삼각수도 포함했는데, 여기서는 커누스의 표기법에 따라
?로 씁니다(예:3?= 6). 자세한 내용은 위키백과의 삼각수 문서에서 볼 수 있습니다.
간단한 산수 게임에서 이런 연산 중 일부(계승이나 로그 같은)는 조금 ‘반칙’처럼 느껴질 수 있다는 걸 압니다. 하지만 흥미로운 복잡도를 더해 주고, 목표 숫자에 도달하는 길을 더 많이 열어 줍니다. 처음 시도했을 때 입력의 약 10%는 사칙연산만으로는 풀 수 없었기 때문에, 더 많은 입력에 해답을 찾으려면 이 추가 연산들이 필요했습니다.
아래는 솔버가 모든 네 자리 입력에 대해 찾아낸 해답의 전체 목록입니다. 인터랙티브 목록에는 각 입력에 대해 찾은 가장 간단한 식이 들어 있습니다.
구현
코드 자체는 혁신적인 게 전혀 없습니다. 식 트리를 만드는 브루트 포스 깊이 우선 탐색입니다. 가장 큰 어려움은 수학이 아니라 기계의 한계였습니다.
- 종료: 계승과 삼각수를 중첩하면 금세 오버플로가 납니다. 코드가 우주의 열적 죽음까지 돌아가지 않도록 탐색 깊이를 과감하게 제한해야 했습니다.
- 서식: 출력이 ASCII 죽처럼 보이지 않도록 LaTeX 서식과 씨름하는 데 터무니없이 많은 시간을 썼습니다.
- 휴리스틱: 그냥 아무 해답이 아니라 가장 간단한 해답을 원했습니다. 삼각수 연산자나 중첩된 제곱근 같은 ‘대량 살상 무기’보다 기본 산술(
+,-)을 선호하도록 솔버에 가중치를 줬습니다. 정말 필요할 때만 중화기를 꺼내도록요(적어도 그러려고 노력했습니다).
그리고 혹시 나머지 연산(mod)이나 삼각수 연산자(?)에 기대지 않는 더 간단한 해답을 찾으신다면 꼭 알려 주세요. 반영하겠습니다.