라이츠아웃의 계보: 장난감에서 시작된 선형대수 퍼즐
두들라이츠아웃처럼 '누르면 십자 모양으로 뒤집히는' 퍼즐에는 라이츠아웃(Lights Out)이라는 이름이 붙어 있다. 이 이름은 실제로 1995년에 나온 상품에서 왔다.
1995년, 손바닥만 한 장난감
미국의 완구회사 타이거 일렉트로닉스(Tiger Electronics)는 1995년 '라이츠아웃'이라는 휴대용 전자 퍼즐을 출시했다. 5×5 격자에 LED 버튼이 박혀 있고, 하나를 누르면 그 버튼과 상하좌우 네 개, 총 다섯 개의 불이 함께 뒤집히는 방식이었다. 규칙은 단순했지만 인기가 상당해서 후속작과 변형판이 여러 개 나왔고, 이후 수십 년간 '라이츠아웃'이라는 이름 자체가 이 유형의 퍼즐을 통칭하는 말로 굳어졌다. 두들라이츠아웃의 토글 규칙(누른 칸과 상하좌우가 함께 뒤집힌다)은 이 원작 장난감의 규칙을 그대로 따른다.
원조 전에도, 후에도 비슷한 장난감이 있었다
라이츠아웃이 완전히 처음 나온 아이디어는 아니었다. 1970년대에 파커 브라더스(Parker Brothers)가 내놓은 전자 게임 '멀린(Merlin)'에도 비슷한 규칙이 일부 들어 있었고, 3×3 격자로 더 작은 판이었다. 1983년에는 벌컨 일렉트로닉스(Vulcan Electronics)가 'XL-25'라는 이름으로 비슷한 게임을 내놓기도 했다. 타이거 일렉트로닉스의 1995년판이 유독 널리 알려지고 학계 분석 대상이 된 건 5×5라는 딱 알맞은 크기, 그리고 상업적으로 크게 성공해 후속작이 이어졌기 때문이다. 이후 여러 색을 쓰는 '라이츠아웃 2000', 3×3 면 여섯 개가 모서리를 사이에 두고 서로 영향을 주는 정육면체형 '라이츠아웃 큐브', 격자를 6×6으로 키운 '라이츠아웃 디럭스' 같은 변형판이 잇따라 나왔다. 1997년에는 타이거토이즈의 휴대용 게임기 '게임닷컴(Game.com)'에 카트리지판으로 이식돼, 본체를 살 때 무료로 함께 딸려 오기도 했다.
장난감보다 먼저 있었던 수학
흥미로운 건 이 퍼즐의 수학적 뼈대가 장난감보다 먼저 학계에 존재했다는 점이다. 컴퓨터과학자 클라우스 수트너(Klaus Sutner)는 1989년 논문에서 '선형 셀룰러 오토마타'라는, 인접한 칸이 서로 영향을 주고받으며 상태가 뒤집히는 격자 구조를 수학적으로 분석했다. 라이츠아웃의 토글 규칙은 이 셀룰러 오토마타의 한 특수 사례에 정확히 들어맞는다. 즉 장난감이 먼저 나오고 학자들이 나중에 분석한 게 아니라, 비슷한 구조의 수학이 이미 연구되고 있던 와중에 우연히 같은 구조를 가진 장난감이 시장에 나온 셈이다. 셀룰러 오토마타는 원래 각 칸이 이웃 칸의 상태에 따라 다음 단계의 상태를 스스로 정하는 훨씬 더 일반적인 수학적 모델을 가리키는데, 라이츠아웃은 그중에서도 '누르면 즉시 이웃까지 뒤집힌다'는 아주 단순한 규칙만 남긴 특수한 경우인 셈이다.
대수학 문제가 되다
장난감이 인기를 끈 뒤, 수학자 앤더슨(Marlow Anderson)과 페일(Todd Feil)은 1998년 『The College Mathematics Journal』에 실은 논문 「Turning Lights Out With Linear Algebra」에서 이 퍼즐을 정식으로 선형대수 문제로 정리했다. 각 칸의 상태를 0과 1로 표현하고, 버튼 하나를 누르는 행위를 GF(2, 원소가 두 개뿐인 대수 체계) 위의 벡터 더하기로 치환하면, 어떤 시작 상태가 풀리는지 안 풀리는지, 그리고 최소 몇 번 눌러야 풀리는지를 행렬 연산만으로 답할 수 있다는 게 이 논문의 핵심이었다. 같은 이유로, 어떤 판이 풀린다면 그 판은 각 버튼을 많아야 한 번씩만 눌러서 풀 수 있다는 것도 이 대수 구조의 자연스러운 결론이다. 두 번 누르면 원래대로 돌아오는 GF(2)의 성질상, 같은 버튼을 두 번 누르는 건 언제나 낭비이기 때문이다. 이 논문 덕분에 라이츠아웃은 지금도 여러 대학의 선형대수 강의에서 GF(2) 계산의 예시로 다뤄진다.
풀리지 않는 배치가 실제로 얼마나 되는가
앤더슨과 페일의 논문에서 가장 놀라운 결론은 숫자로 확인할 수 있다. 표준 5×5 라이츠아웃에서 25칸 각각을 켜거나 끈 상태로 무작위로 설정하면, 이론적으로 나올 수 있는 시작 배치는 2의 25제곱, 약 3,350만 가지다. 그런데 이 중 실제로 풀 수 있는(모든 불을 끌 수 있는) 배치는 딱 4분의 1뿐이다. 나머지 4분의 3은 어떤 순서로, 몇 번을 누르든 절대로 다 끌 수 없는 배치라는 뜻이다. 이 결과는 '버튼을 누르는 25가지 조작'을 행렬로 표현했을 때, 그 행렬의 실질적인 계수(rank)가 25가 아니라 23이라는 사실에서 나온다. 나머지 2개 차원은 이른바 '고요한 패턴(quiet pattern)'이 차지한다. 특정 버튼들을 정확한 조합으로 함께 누르면, 각 칸이 짝수 번씩 뒤집히면서 겉보기에는 화면에 아무 변화도 없이 원상태로 돌아오는 조합이 존재한다는 뜻이다. 이런 '아무 효과 없는' 조합이 5×5 보드에는 자명한 경우(아예 안 누르기)를 포함해 총 4가지 있고, 이 때문에 25개 버튼으로 만들 수 있는 조작의 실질적인 가짓수가 2의 25제곱이 아니라 2의 23제곱으로 줄어든다. 그리고 정확히 그만큼의 비율로, 도달 가능한(=풀 수 있는) 시작 배치의 가짓수도 전체의 4분의 1로 줄어든다. 보드 크기가 바뀌면 이 비율도 함께 바뀐다는 점도 흥미로운데, 격자 크기에 따라 계수와 고요한 패턴의 개수가 달라지기 때문에 어떤 크기의 보드는 임의의 시작 상태가 항상 풀리기도 하고, 5×5처럼 그렇지 않기도 하다.
두들라이츠아웃은 조금 다르게 만들었다
원작 장난감과 학계 분석은 대개 '주어진 임의의 시작 상태'를 다룬다. 방금 살펴본 것처럼 표준 5×5 격자에서는 임의의 시작 상태 중 4분의 3이 애초에 풀리지 않는 배치다. 두들라이츠아웃은 이 함정을 피하기 위해 정반대 방향에서 판을 만든다. 이미 다 꺼진 상태에서 출발해 몇 개의 칸을 무작위로 눌러 시작 화면을 만들기 때문에, 어떤 판이 나오든 반드시 풀린다는 게 구조적으로 보장된다. 다 꺼진 상태에서 몇 번을 눌러 만든 배치는 정의상 '도달 가능한' 4분의 1 안에 항상 속하기 때문이다. 이 생성 방식에 대해서는 제작기 카테고리에서 더 자세히 다룬다. 1995년의 손바닥만 한 장난감 하나가 학술지의 선형대수 논문 소재가 되고, 다시 30년 가까이 지나 모바일 웹의 손그림 스타일 캐주얼 게임으로 이어지는 이 흐름을 보면, 규칙 자체는 처음 나온 그대로인데 그 규칙을 설명하는 언어만 장난감 설명서에서 대수학 논문으로, 다시 짧은 웹 가이드 글로 계속 옷을 갈아입어 온 셈이다.