STILLCODING

STILL CODING / NOTES

숫자합 퍼즐: 판을 거꾸로 만들면 시작하자마자 막히지 않는다

JH Kim

숫자합 퍼즐은 19가 적힌 타일을 눌러 합이 목표 숫자가 되면 그 타일이 사라지는 게임입니다. 방장이 목표(530)와 타일 개수(16, 25, 36, 49)를 정하고, 모든 참가자가 같은 판을 받아 누가 더 많이 비우는지 겨룹니다.

두 번째로 추가한 게임이라 방 만들기, P2P 자원 전달, 타이머, 결과 공유는 이미 있는 것을 그대로 썼습니다. 게임 자체가 새로 한 일은 세 가지입니다. 판을 만들고, 더 이상 못 만드는 순간을 알아내고, 힌트를 주는 것입니다.

판을 무작위로 채우면 생기는 문제

1~9를 무작위로 깔면 목표 합을 만드는 조합이 하나도 없는 판이 나올 수 있습니다. 목표가 30이고 타일이 16개일 때 이런 판이 얼마나 자주 나오는지는 재 보지 않았습니다. 다만 시작하자마자 “조합 없음”으로 끝나는 판이 한 번이라도 나오면 방 전체가 어색해지므로, 확률을 따지기보다 그런 판이 나올 수 없는 방법을 골랐습니다.

조합을 먼저 만들고 그 숫자들로 판을 채우는 것입니다.

// 합이 target인 1~9 숫자 length개를 무작위로 만든다.
function randomCombo(target, length) {
  const digits = [];
  let rest = target;
  for (let slots = length; slots >= 1; slots -= 1) {
    const remainSlots = slots - 1;
    const low = Math.max(1, rest - MAX_DIGIT * remainSlots);
    const high = Math.min(MAX_DIGIT, rest - remainSlots);
    const value = low + randomInt(high - low + 1);
    digits.push(value);
    rest -= value;
  }
  return digits;
}

한 자리씩 뽑되, 뽑은 뒤에 남은 자리들이 채울 수 있는 범위 안에서만 고릅니다. 목표 10을 3개로 나눌 때 첫 자리는 최소 10 - 9×2 → 1, 최대 10 - 2 = 8입니다. 첫 자리에서 9를 뽑으면 나머지 두 자리가 합 1을 만들어야 하는데 최소가 2라 불가능하기 때문입니다.

짧은 조합을 자주

const roll = Math.random();
const extra = roll < 0.5 ? 0 : roll < 0.8 ? 1 : 2;
const len = Math.min(minLen + extra, maxLen);

조합의 길이는 ceil(목표/9)(가장 짧을 수 있는 길이)부터 2개 더 긴 길이까지 정하는데, 짧은 쪽에 무게를 둡니다. 50%는 최소 길이, 30%는 하나 더, 20%는 둘 더입니다. 긴 조합은 작은 숫자가 많이 나오는데 판이 1로 가득 차는 것을 피하려는 것입니다.

이렇게 조합을 이어 붙이고, 남는 칸이 최소 조합 길이보다 작아지면 그 칸은 1~9 무작위로 채웁니다. 마지막에 전체를 섞습니다.

완벽한 클리어는 보장되지 않는다

판이 조합으로 딱 나눠떨어질 필요는 없다고 봤습니다. 칸 수와 조합 길이가 맞아떨어지지 않으면 마지막에 조합이 못 되는 칸이 남고, 그 칸은 무작위 숫자로 채웁니다. 그런 판은 처음부터 다 비우는 것이 불가능할 수 있습니다.

또 하나, 만들 때의 조합대로 지워야만 다 비울 수 있는 것은 아닙니다. 어떤 타일 묶음이든 합이 목표면 지워지므로, 플레이어가 다른 조합을 고르면 원래 계획된 조합이 깨지고 끝에 타일이 남을 수 있습니다. 시작할 때 조합이 존재한다는 것만 보장되고, 끝까지 비울 수 있는 경로가 있다는 보장은 아닙니다.

언제 끝나는가: 부분집합 합

게임은 “남은 타일 중 합이 목표인 부분집합이 있는가”가 거짓이 되는 순간 끝납니다. 가능한 조합을 하나씩 세는 대신 부분집합 합 DP로 확인합니다.

export function findCombination(tiles, target) {
  const from = new Array(target + 1).fill(null);
  from[0] = { prev: -1, index: -1 };
  for (let i = 0; i < tiles.length; i += 1) {
    const value = tiles[i];
    if (!value || value > target) continue;
    for (let sum = target; sum >= value; sum -= 1) {
      if (!from[sum] && from[sum - value]) {
        from[sum] = { prev: sum - value, index: i };
      }
    }
    if (from[target]) break;
  }
  if (!from[target]) return null;
  const combo = [];
  let sum = target;
  while (sum > 0) {
    combo.push(from[sum].index);
    sum = from[sum].prev;
  }
  return combo;
}

from[s]는 “합 s를 만들 수 있다면, 마지막에 어떤 타일을 더해서 만들었는가”를 담습니다. 타일을 하나씩 훑으면서 합을 큰 쪽부터 갱신하는데, 큰 쪽부터 돌기 때문에 같은 타일을 두 번 쓰지 않습니다. 이미 지워진 타일은 null이라 건너뜁니다. 합 target에 닿으면 prev를 따라가며 사용한 타일 번호를 복원합니다.

타일이 최대 49개, 목표가 최대 30이라 많아야 1,470번 정도 도는 작은 계산입니다.

같은 함수 하나를 두 곳에 씁니다.

플레이어가 이 조합을 알고 있는지와 상관없이 판정은 정확합니다. 사람이 놓친 조합이 남아 있다면 게임은 끝나지 않습니다.

선택하는 손맛

한 번 잘못 누르면 처음부터 다시 골라야 하는 방식은 모바일에서 답답하다고 생각해서, 마지막 한 개만 거부하도록 했습니다.

이어 하기와 결과

저장하는 상태는 타일 배열(지워진 곳은 null로 자리를 보존), 선택한 번호, 성공 횟수, 힌트 사용입니다. 지워진 자리를 null로 두는 이유는 새로고침한 뒤에도 남은 타일이 같은 칸에 있어야 하기 때문입니다.

결과에는 남은 타일 수가 붙습니다. 결과 화면에서 0개이면 “퍼펙트”, 아니면 “남은 타일 K개”로 표시합니다. 이 값이 이 게임의 실력 지표라서 P2P로 공유되는 결과에 포함했습니다.

남은 일

참고