TigerDocu 개발기 ② 답이 하나뿐인 퍼즐을 폰에서 만든다

1편에서 “게임 로직에는 네트워크를 쓰지 않는다” 고 정했다. 그러니 퍼즐을 내려받을 서버가 없다. 판은 빌드할 때 미리 만들어 앱에 넣거나, 폰에서 직접 만들어야 한다. 둘 다 같은 생성기를 쓴다. 이번 편은 그 생성기 이야기다.

좋은 퍼즐 판의 조건은 두 가지다.

답이 정확히 하나 — 답이 둘이면 논리로 풀다가 막히고 찍어야 한다.
사람이 논리로 풀 수 있음 — 답이 하나여도 사람이 쓰는 추론으로 도달할 수 없으면, 사람에겐 찍기와 같다.

자료구조 하나로 문제가 작아졌다

호랑이는 가로줄마다 정확히 한 마리다. 그러니 답은 2차원 판이 아니라 길이 N 인 배열 solution[행] = 열 로 쓸 수 있다. 이렇게 쓰면 “줄마다 하나” 는 구조상 자동으로 지켜지고, 남는 검사는 셋뿐이다.

세로줄이 겹치지 않는가 (배열이 순열인가)
색 영역이 겹치지 않는가
위아래 행끼리 붙지 않는가 — |sol[r] − sol[r+1]| ≥ 2

마지막 검사가 이웃 행만 보면 되는 이유가 있다. 같은 행에는 한 마리뿐이니 좌우로 붙을 수 없고, 두 줄 이상 떨어진 행끼리는 대각선으로도 닿지 않는다. 그래서 해를 세는 솔버는 행 단위 백트래킹 하나로 끝난다.

const rec = (r: number) => {
  if (r === n) { count++; return }
  if (regionDead(n, maxRow, regionUsed, r)) return   // ← 뒤에서 설명할 가지치기
  for (let c = 0; c < n; c++) {
    if (colUsed[c]) continue
    if (r > 0 && Math.abs(place[r - 1] - c) < 2) continue
    const reg = regions[r * n + c]
    if (regionUsed[reg]) continue
    colUsed[c] = regionUsed[reg] = 1; place[r] = c
    rec(r + 1)
    colUsed[c] = regionUsed[reg] = 0; place[r] = -1
    if (count >= limit) return   // 유일해 검사는 limit=2 — 두 번째 해가 보이면 끝
  }
}

유일해: 다시 뽑지 말고 고친다

생성 순서는 이렇다.

규칙에 맞는 답 배치를 먼저 무작위로 만든다.
답 칸을 씨앗 삼아 색 영역을 키운다.
답이 하나가 될 때까지 영역을 고친다.
사람의 기법으로 풀리는지 잰다.

3번에서 처음 떠오르는 방법은 “답이 둘이면 영역을 새로 그린다” 다. 재 보니 안 됐다. 영역을 400번 새로 그렸을 때 답이 하나인 판이 나온 횟수는 6×6 에서 1번, 7×7 이상에서는 0번이었다.

그래서 수리 로 바꿨다. 솔버가 찾은 다른 답(alt)을 보고, alt 가 쓰는 칸 하나를 alt 의 다른 호랑이가 이미 있는 이웃 영역으로 넘긴다. 그러면 그 영역에 alt 의 호랑이가 둘이 되어 alt 는 바로 답이 아니게 된다. 씨앗(진짜 답의 칸)은 절대 옮기지 않으니 의도한 답은 항상 살아 있다. 이걸 다른 답이 안 보일 때까지 반복한다.

함정이 하나 있었다. 수리를 거듭할수록 영역이 가늘어지고, 경계 칸 하나를 빼면 영역이 두 동강 나는 경우가 많아진다. 옮길 수 있는 칸이 없어서 수리가 멈춘다. 판 전체에서 아무 경계 칸이나 옮기는 마지막 순위의 이동을 추가했더니 12×12 의 유일해 도달률이 0/12 에서 3/3 이 됐다.

난이도는 “사람이 쓰는 기법” 으로 잰다

답이 하나인지는 컴퓨터가 확인한다. 하지만 어려움 은 컴퓨터의 탐색 시간이 아니라 사람이 쓰는 추론으로 재야 한다. 그래서 솔버를 하나 더 만들었다. 사람이 쓰는 기법만으로 풀어 보고, 가장 어려운 기법이 몇 단계였는지 와 추론을 몇 번 했는지 를 돌려준다. 이 솔버로 끝까지 못 풀면 답이 하나여도 버린다.

단계	기법	한 줄 설명
1·2	강제 배치	줄이나 영역에 놓을 자리가 하나뿐
3	영역 가두기	영역의 남은 칸이 한 줄에 몰려 있으면 그 줄의 나머지는 ✕
4	줄 가두기	줄의 남은 칸이 한 영역에 몰려 있으면 그 영역의 나머지는 ✕
5	모양 지우기	어디에 놓든 반드시 붙게 되는 칸은 ✕
6	N개 묶음	영역 K개가 줄 K개를 정확히 차지하면 그 줄의 다른 칸은 ✕
7	배제	여기 놓으면 어떤 영역이 텅 비게 되는 칸은 ✕

큰 판의 열쇠는 5단계였다. 아무것도 확정되지 않은 첫 상태에서 붙으면 안 된다 는 규칙만으로 후보를 지우는 유일한 기법이다. 이게 없을 땐 큰 판이 전부 “논리로 안 풀림” 으로 버려졌다.

큰 판 생성, 첫 번째 측정 — 병목은 생각한 곳에 없었다

8월 말의 숫자는 이랬다. 10×10 은 2.8초에 성공률 25%. 12×12 는 5분을 돌려도 0/3. 13×13 은 아예 나오지 않았다.

처음엔 당연히 논리 풀이 가 느리다고 생각했다. 기법을 더 넣으면 풀리는 판이 늘 테니까. 하지만 고치기 전에 단계별로 쟀다. “유일해에 도달하는 데 걸린 시간” 과 “논리로 푸는 데 걸린 시간” 을 따로 찍는 스크립트(funnel.ts)를 만들었다.

결과는 예상과 달랐다. 병목은 논리 풀이가 아니라 유일해 검사였다. 수리 루프는 매번 “다른 답이 없다” 를 증명해야 하는데, 답이 하나에 가까운 판일수록 그 증명은 탐색 트리 전체를 뒤지는 일이다. 생성기가 바로 그런 판을 계속 만들어 내고 있었다.

처방은 위 코드의 regionDead 한 줄이다. r행까지 놓았다면 남은 행은 n−r 개이고 남은 영역도 정확히 n−r 개다. 아직 안 쓴 영역의 칸이 전부 r행보다 위에 있으면 그 영역은 영원히 쓸 수 없다. 그 가지를 바로 버린다.

	전	후
10×10	2,787ms, 성공 2/8	270ms, 성공 40/40
13×13 (같은 시드 3개 합)	1,164초	245초 (4.8배)

이때 문서에 이렇게 적어 뒀다. 그 측정이 없었으면 기법만 계속 추가하며 헛수고했을 것이다. 성능 문제는 추측하지 말고 먼저 재라.

두 번째 측정 — 진짜 원인은 “난이도 맞추기” 였다

9월 7일, 차수 모드를 만들면서 다시 쟀다. 이번엔 숫자가 이상했다.

9×9 쉬움: 1,031ms / 9×9 전문가: 15ms
11×11 쉬움: 성공률 0%, 한 번에 46초

쉬운 판이 어려운 판보다 70배 느렸다. 판이 커지면 1~2단계 기법만으로 풀리는 배치 가 거의 존재하지 않는다. 그런 판을 찾느라 96번을 다 돌리고 결국 버리는 비용이 전부였다. 반대로 큰 판에서 전문가 판은 흔하고 싸다.

그래서 11칸 이상은 “이 기법 단계 안에서만” 이라는 조건을 걷었다. 아무 판이나 만든 뒤 측정해서 난이도 라벨을 붙인다. 체감 난이도는 기법 단계 대신 추론 횟수의 하한 으로 조절한다.

크기	전	후
11×11	46초, 0%	2.0초, 100%
12×12	—	1.0초, 100%
13×13	—	22.8초, 100%

다만 만들 수 있는 것 과 폰에서 즐길 만한 것 은 다른 문제다. 폭 420px 화면에서 13×13 의 칸은 30px 이다. 안드로이드가 권하는 터치 크기 48dp 에 한참 못 미친다. 그래서 13×13 은 드물게만 나오게 했다.

차수 모드 — “3차를 깼다” 가 모두에게 같은 뜻이어야 한다

폰에서 무작위로 판을 만들면 사람마다 다른 판을 푼다. “12차가 어렵더라” 는 말이 성립하려면 모두가 같은 판 을 풀어야 한다. 그래서 1~300차 판은 빌드할 때 미리 만들어 JSON 팩으로 앱에 넣었다(세 파일, 합쳐 약 80KB). 301차부터는 팩 빌더와 같은 절차, 같은 시드 로 폰에서 만든다. 그러니 그 뒤도 모두에게 같은 판이다.

판 크기는 차수에 따라 커진다. 1~~5차 6×6, 6~~10차 7×7, 11~20차 8×8, 21차부터 9×9, 50차 10×10, 120차 11×11, 300차 12×12. 13×13 은 300차부터 8%, 600차부터 22% 확률로만 섞인다. 드물어야 큰 판이 사건이 된다.

21차부터는 일곱 판 단위로 난이도가 파도처럼 오르내린다. 추론 횟수의 하한을 바닥 + (정점 − 바닥) × [0, ⅓, ⅔, 1, ⅔, ⅓, 0] 으로 움직인다. 정점은 크기별로 실측해서 정했다(9×9 는 15, 10×10 은 21, 12×12 이상은 24). 계속 어렵기만 하면 지친다.

조용히 깨져 있던 “모두가 같은 판”

나중에 보니 팩 빌더와 앱이 재시도할 때 시드를 늘리는 폭이 서로 달랐다(104,729 와 7,919). 팩이 있는 300차까지는 문제가 없었지만, 301차부터는 빌더와 앱이 다른 판 을 만들고 있었다. 테스트에도 안 걸렸다. 재시도 루프를 함수 하나로 합쳐서 두 쪽이 같은 코드를 타게 했다.

한 판 깼는데 차수가 둘 오르던 버그

“2차로” 를 누르면 차수 번호는 바로 2가 되는데, 판 교체는 비동기라 한 프레임 늦게 일어난다. 그 한 프레임 동안 (차수 = 2, 판 = 아직 1차, 풀림 = 참) 이라는 상태가 존재했고, 그 프레임에 “2차 클리어” 가 저장됐다. 차수 번호 대신 풀린 퍼즐 자체 를 보고 잠그게 고쳤다.

힌트: 답을 주지 말고 이유를 보여 준다

처음 힌트는 정답 칸에 호랑이를 놓아 주는 방식이었다. 무제한이면 힌트만 눌러 판이 풀린다. 그래서 판당 5회로 막았다. 그런데 힌트 → 되돌리기 → 손으로 같은 자리에 놓기 로 무한히 쓸 수 있었다. 그것도 막았다. 막을수록 깨달았다. 이 힌트는 답 을 알려 줄 뿐 왜 를 알려 주지 않는다. 퍼즐 앱의 힌트가 해야 할 일은 다음에 같은 상황에서 혼자 풀게 만드는 것이다.

1.4.9 에서 힌트를 새로 만들었다. 지금 판에서 사람이 둘 수 있는 다음 한 수 를 찾아, 판 위에 1~4장의 설명으로 보여 준다. 근거가 되는 칸만 밝게 남기고, 가정한 호랑이에는 ①②③ 번호를 붙인다.

길잡이 힌트 화면

찾는 순서는 이렇다. 잘못 친 ✕ → 막힌 빈칸 → 하나 남은 자리 → 한 줄에 몰린 칸 → “여기 놓으면?” (놓자마자 어딘가 텅 비면 2장, 강제로 이어지는 배치 뒤에 비면 3~4장) → 줄을 차지한 영역 → 그래도 없으면 정답 공개.

설계 원칙은 하나다. “판의 ✕ 는 믿되, 정답 칸에 친 ✕ 만은 안 믿는다.” 사람이 잘못 친 ✕ 를 그대로 믿고 추론하면 힌트가 틀린 걸 가르친다. 그래서 잘못 친 ✕ 를 가장 먼저 찾는다. 그리고 같은 이유로 지워지는 칸이 여럿이면 한 번에 다 ✕ 를 친다. 같은 설명에 힌트를 여러 번 쓰게 만들지 않기 위해서다.

검증은 힌트만 눌러서 210판을 끝까지 푸는 스크립트로 했다. 틀린 걸 가르친 횟수 0, 정답 공개까지 떨어진 횟수 0.

조작은 두 번 바꿨다가 처음으로 돌아왔다

칸을 어떻게 누르게 할지는 의외로 오래 걸렸다.

시기	방식	왜 바꿨나
8월 29일	한 번 탭할 때마다 빈칸 → ✕ → 호랑이 → 빈칸	처음 만든 방식
같은 날	한 번 탭 = ✕, 두 번 탭 = 호랑이, 끌기 = ✕ 칠하기	경쟁 앱들의 관례를 따름
1.1	두 번 탭을 직접 센다 (400ms 안에 같은 칸)	모바일에서 `dblclick` 이 아예 안 왔다
9월 5일	다시 한 탭 순환으로	Queens 방식을 따라 해 봄
9월 10일	확정 호랑이는 탭으로 못 지우게	순환 때문에 맞게 놓은 호랑이가 지워짐
10월 19일	두 번 탭으로 복귀	✕ 를 지우려고 한 번 더 누르면 호랑이가 놓여 하트를 잃음

9월 10일 커밋 메시지에 이유가 잘 적혀 있다. Queens 는 다 놓은 뒤에 검증하지만 이 게임은 놓는 순간 판정한다. 전제가 다른 패턴을 그대로 옮긴 자리다. 다른 게임에서 잘 되는 조작이 여기서도 잘 된다는 보장은 없다. 틀린 호랑이를 놓으면 하트가 깎이는 게임에서 한 번 더 누르면 호랑이 는 함정이었다.

가정 모드

경쟁 앱 세 곳 모두에 없던 기능이다. 연필 버튼을 켜면 놓는 호랑이와 ✕ 가 점선으로 표시되고, 틀려도 하트가 깎이지 않는다. 리뷰에 있던 “스크린샷 찍어서 따로 그려가며 푼다” 를 앱 안으로 들인 것이다.

첫 구현에는 구멍이 있었다. 가정 모드에서 친 ✕ 가 확정 ✕ 로 남아 판을 더럽혔다. 1.4 에서 가정 ✕ 를 별도 상태로 분리했다. 모드를 나가면 가정한 호랑이와 ✕ 가 같이 걷히고, 그 전체가 되돌리기 한 번으로 복구된다. 예전 구현은 나갈 때 기록을 지워 버려서 실수로 나가면 되살릴 수 없었다.

덤: 칸 크기는 기기마다 다르다

같은 9×9 판이라도 폰의 폭과 화면 배율에 따라 칸 하나가 실제 화소로 80px 도 되고 110px 도 된다. 호랑이 그림 한 장을 늘이고 줄이면 픽셀아트가 뭉개진다. 그래서 16~320 화소용 그림을 97장 미리 구워 두고, 칸 크기에 꼭 맞는 장을 1:1 로 그린다.

그래도 뿌옜다. 화면 배율이 2.625 인 폰에서는 60px 그림이 59.96px 로 그려진다. 브라우저는 이 0.999배에도 부드러운 보간을 건다. image-rendering: pixelated 한 줄로 막았다.

다음 편은 이 앱을 실제로 Google Play 에 내놓는 과정 이다. 서명키, 비공개 테스트, 데이터 보안 양식, 광고 위치가 안 맞던 문제, 16일 걸린 프로덕션 심사, 그리고 145개국 출시까지.