항상 풀리는 라이츠아웃 판을 만드는 법 — 두들라이츠아웃 제작기
라이츠아웃류 퍼즐을 자동 생성하려 할 때 가장 먼저 부딪히는 문제는 "혹시 이 판, 안 풀리는 거 아니야?"다. 표준 라이츠아웃은 격자 크기에 따라 임의의 배치가 풀리지 않는 경우가 실제로 존재한다(이 부분은 배경지식 카테고리의 다른 글에서 다뤘다). 플레이어가 아무리 애써도 원리적으로 풀 수 없는 판을 우연히 만나는 건 최악의 경험이다. 그래서 두들라이츠아웃은 판을 무작위로 만든 뒤 "이게 풀리나?"를 검증하는 방식이 아니라, 애초에 반드시 풀리는 방식으로만 판을 만든다.
거꾸로 만들면 반드시 풀린다
방법은 간단하다. 모든 불이 꺼진, 이미 클리어된 상태에서 출발해서, 서로 다른 칸을 무작위로 몇 개 골라 한 번씩 누른다. 이 조작을 코드에서 그대로 확인할 수 있다. 판마다 정해지는 '파(par)' 숫자만큼 서로 다른 좌표를 뽑아 하나씩 토글하고, 이미 뽑은 좌표는 다시 뽑지 않도록 집합으로 걸러낸다. 이렇게 만들어진 판은 처음에 눌렀던 그 칸들을 그대로 다시 누르기만 하면 반드시 원래의 '올 꺼짐' 상태로 돌아간다. 순서가 상관없다는 성질(다른 글에서 다룬 GF(2)의 교환법칙) 덕분에, 만들 때 누른 순서와 풀 때 누르는 순서가 달라도 상관없다. 결과적으로 "반드시 풀린다"는 보장이 증명이 아니라 만드는 방식 자체에서 자동으로 나온다.
왜 굳이 '서로 다른' 칸이어야 하는가
여기서 눈여겨볼 디테일이 하나 있다. 좌표를 뽑을 때 이미 뽑은 좌표를 다시 뽑지 않도록 집합으로 걸러내는 이유다. 만약 같은 칸을 두 번 뽑아 두 번 누르게 되면, GF(2)의 성질상 그 두 번의 조작은 서로 상쇄돼 결과적으로 아무 효과가 없다. 즉 "par만큼 눌러서 시작 배치를 만든다"고 정해놓고 실제로는 중복된 칸이 섞여 들어가면, 겉보기엔 par번 누른 것 같지만 실질적으로 켜진 칸의 수는 그보다 적어질 수 있다. 이렇게 되면 게임이 화면에 표시하는 "파 N수"라는 숫자와, 실제로 이 판을 만드는 데 쓰인 유효한 조작 횟수가 어긋나 버린다. 좌표를 집합으로 관리해 중복을 원천 차단하는 이 한 줄은, par이라는 숫자가 실제로 의미하는 바와 화면에 표시되는 숫자가 항상 일치하도록 만들어주는 장치다.
파(par)의 진짜 의미
여기서 파(par)라는 숫자가 왜 그 이름으로 불리는지가 분명해진다. 파는 임의로 정한 '적당히 어려운 기준'이 아니라, 실제로 이 판을 만들 때 뒤집은 칸의 개수 그 자체다. 그러니까 파만큼 누르면 반드시 풀린다는 게 생성 로직 안에 이미 보장돼 있고, 게임은 이 숫자를 그대로 플레이어에게 목표치로 보여준다. 파 이하로 끝내면 PERFECT 콤보가 붙는 이유도 여기 있다. 생성기가 판을 섞는 데 쓴 손놀림 수보다 적거나 같은 횟수로 끄면, 생성기보다 더 효율적인 경로를 찾아낸 셈이기 때문이다. 실제 코드에서 파는 단계가 오를수록 4에 단계 수를 더한 값으로 커지다가 14에서 멈춘다. 초반 판은 5수 안팎, 후반 판은 최대 14수까지 늘어난다.
파보다 적은 수로 끌 수도 있는 이유
흥미로운 지점이 하나 더 있다. par는 "이 판을 반드시 풀 수 있는 손놀림 수"를 보장하지만, "이론상 가능한 가장 짧은 손놀림 수"까지 보장하지는 않는다. 배경지식 카테고리에서 다룬 것처럼 라이츠아웃 판에는 눌러도 겉보기에 아무 변화가 없는 '고요한 패턴'이 존재한다. 만약 par개의 칸을 뽑은 조합이 우연히 이 고요한 패턴과 일부 겹치면, 그 조합보다 더 적은 칸만 눌러도 같은 결과에 도달하는 지름길이 생길 수 있다. 물론 이런 우연은 자주 일어나지는 않지만, 이론적으로는 존재한다. 그러니까 아주 가끔 "분명히 파보다 적게 눌렀는데 PERFECT가 떴다"는 경험을 한다면, 그건 버그가 아니라 우연히 더 효율적인 경로를 찾아낸 것이다. par는 '보장된 정답'이지 '유일한 정답'은 아니라는 뜻이다.
드물게 생기는 예외 처리
무작위로 서로 다른 칸을 골라 누르다 보면, 아주 드물게 그 조합이 우연히 서로의 효과를 상쇄해서 결과적으로 아무 불도 켜지지 않는 경우가 생길 수 있다. 다섯 칸씩 뒤집는 조작이 여러 번 겹치면 이런 우연이 이론상 가능하다. 이 경우를 대비해 코드에는 "만약 생성 결과가 완전히 꺼진 상태라면 강제로 한 칸을 눌러 최소 하나는 켜지게 만든다"는 예외 처리가 들어 있다. 사소해 보이지만, 이런 예외를 안 잡아두면 아주 낮은 확률로 '시작하자마자 클리어'라는 김빠지는 판이 플레이어에게 갈 수 있다. 보드 크기도 같은 이유로 무한정 키우지 않았다. 1~5단계는 4×4, 6~10단계는 5×5, 11단계 이후로는 6×6에서 고정된다. 격자가 커질수록 파도 함께 늘어나는데, 어느 지점부터는 한 판을 끝내는 데 필요한 탭 수가 지나치게 많아져 '짧게 즐기는 미니게임'이라는 두들게임즈 전체의 기조에서 벗어난다고 판단해 6×6에서 상한을 뒀다.
검증이 필요 없는 생성기라는 이점
이 생성 방식의 진짜 장점은 속도에 있다. "무작위로 배치를 만들고 풀리는지 검증한다"는 접근을 택했다면, 매번 그 배치가 실제로 풀리는지 확인하는 계산(행렬 연산이나 탐색)이 필요했을 것이다. 배경지식 카테고리에서 다룬 것처럼 5×5 보드에서는 무작위 배치 중 4분의 3이 애초에 풀리지 않기 때문에, 운이 나쁘면 여러 번 다시 만들어야 했을 수도 있다. 반면 두들라이츠아웃의 방식은 애초에 '풀리는 배치의 집합' 안에서만 만들기 때문에 검증 단계 자체가 필요 없다. 정해진 파 숫자만큼 칸을 뽑아 누르는 단순 반복 작업 하나로 끝난다. 판을 새로 시작할 때마다 지연 없이 곧바로 다음 판이 뜨는 것도, 이 생성 방식이 계산적으로 가볍기 때문이다. 안 풀리는 판을 걸러내는 검증 로직을 아예 따로 만들지 않고, 문제를 정의하는 방식 자체를 바꿔서 "안 풀리는 경우가 원천적으로 나올 수 없게" 만든 셈이다. 코드로 버그를 막는 방법에는 예외 처리를 촘촘히 쌓는 길과, 애초에 그 예외가 발생할 수 없는 구조를 설계하는 길이 있는데, 두들라이츠아웃의 판 생성기는 후자에 가깝다. 문제를 어떻게 정의하느냐에 따라 나중에 처리해야 할 예외의 가짓수가 통째로 달라진다는 걸, 작은 퍼즐 게임 하나를 만들면서 다시 확인한 셈이다.