GM 오락실
← 프로젝트 회고 · Algorithm
RETROSPECTIVE · 회고

오늘의 용의자: 찍지 않고 풀리는 퍼즐만 만드는 생성기

Algorithm

오늘의 용의자는 격자에 앉은 사람들 중 누가 범인이고 누가 무고한지 가려내는 논리 퍼즐이다. 처음엔 한 명만 정체가 밝혀져 있고, 밝혀진 사람은 '내 이웃 중 범인은 2명' 같은 단서를 하나씩 말한다. 날짜와 난이도로 시드를 만들어, 같은 날 같은 난이도는 누구나 같은 퍼즐을 받는다.

퍼즐은 미리 만들어 두지 않고 생성기가 만든다. 그러려면 생성기가 지켜야 할 조건이 있었다. 답이 하나뿐이어야 하고, 처음부터 끝까지 찍지 않고 풀 수 있어야 한다.

모든 단서를 한 가지 꼴로

단서 종류는 이웃, 줄, 열, 방향, 직업, 가장자리, 짝수·홀수 등 열 가지가 넘는다. 솔버가 종류마다 따로 처리하면 단서를 늘릴 때마다 솔버를 고쳐야 한다. 그래서 모든 단서를 한 가지 꼴로 바꿨다.

// 집합 S 안의 범인 수가 허용 목록 A 안에 있다
"내 이웃 중 범인 2명" → S = 이웃 칸들, A = {2}
"B열 범인 수는 홀수" → S = B열, A = {1, 3, 5}

솔버는 이 꼴만 안다. 부분 배정에서 S 안의 확정된 범인 수 k와 모르는 칸 수 u를 세고, k부터 k+u 사이에 A에 든 값이 하나라도 있으면 아직 가능하다. 이 검사로 가지를 치며 백트래킹한다.

'확정된다'의 정의

게임 규칙은 '지금까지 밝혀진 단서로 한쪽으로만 가능한 사람만 지목할 수 있다'이다. 어떤 사람이 확정되는지는 이렇게 판단한다. 단서를 모두 만족하는 배정을 하나 찾고, 그 사람만 반대로 뒤집어도 배정이 있는지 본다. 없으면 확정이다.

플레이할 때도 이 정의를 쓴다. 지목하면 정답과 바로 비교하지 않고, 먼저 솔버로 지금 확정되는 사람인지를 본다. 오늘의 사건에서는 맞는 쪽을 골라도 아직 근거가 없으면 '근거 부족' 실수(+2분)가 되고, 정답이었는지는 알려 주지 않는다. 찍어서 맞히는 길을 막은 것이다.

생성기는 풀이 순서를 따라 만든다

  1. 정답(누가 범인인지)을 먼저 정하고, 무고한 사람 하나를 처음부터 공개한다.
  2. 새로 밝혀진 사람들이 각자 단서를 하나씩 말한다. 단서는 정답에서 참인 것만 만든다.
  3. 지금까지의 단서로 새로 확정되는 사람을 솔버로 찾는다. 하나도 없으면 단서를 다시 뽑는다.
  4. 확정된 사람들이 다음 단서를 말하고, 모두 확정될 때까지 반복한다.

끝까지 가면 모든 사람이 '그 시점의 단서로 확정'된 상태다. 답이 하나라는 것과 찍을 필요가 없다는 것이 만드는 과정에서 같이 보장된다. 다 만든 퍼즐을 검사하는 게 아니라 풀리는 순서대로 만든다. 중간에 막히면 그 시도는 버리고 다시 만든다.

난이도도 솔버로 잰다

난이도를 사람 수만으로 정하면 큰 판이 늘 어려운 판이 된다. 그래서 솔버가 잰 값으로 나눴다.

  1. 한 단계에 새로 확정되는 사람 수: 적을수록 어렵다.
  2. 단서 하나로는 안 풀리고 여러 단서를 같이 봐야 하는 '조합 추론' 단계 수
  3. 나오는 단서 종류와 비율

단서 후보를 여러 번 뽑아 목표에 가장 가까운 걸 고르고, 쉬운 난이도에서 조합 추론이 필요한 단계가 나오면 그 후보를 버린다. 조건을 다 맞추는 퍼즐이 안 나오면 가장 가까운 퍼즐을 쓴다. 지옥 난이도는 조건에 맞는 퍼즐을 찾느라 1~5초 걸려서, 화면이 멈추지 않게 Web Worker에서 만든다.

힌트도 같은 솔버에서

힌트는 두 단계다. 먼저 단서 하나만으로 확정되는 사람이 있으면 그 단서를 다시 보라고 짚고, 한 번 더 누르면 이유를 문장으로 보여 준다('범인이 1명 더 있어야 하는데 아직 모르는 사람이 딱 1명이에요'). 단서 하나로 되는 사람이 없으면 여러 단서를 엮어야 확정되는 사람을 반짝여 준다. 둘 다 생성에 쓴 솔버를 그대로 쓴다.

배운 점

  1. '답이 하나'는 다 만든 뒤 검사하기보다, 만드는 과정이 풀이 순서를 따라가게 하는 게 확실하다.
  2. 단서를 한 가지 꼴로 통일하니 솔버, 힌트, 난이도 측정이 같은 코드를 쓴다. 단서 종류를 늘려도 솔버는 그대로다.
  3. '찍기 금지'는 생성 규칙이면서 채점 규칙이기도 하다. 정답과 비교하기 전에 근거가 있는지부터 본다.
Gunmo Lee
since 2021.07
오늘의 용의자: 찍지 않고 풀리는 퍼즐만 만드는 생성기 | GM 오락실