모두에게 같은 퍼즐을: 시드 결정적 생성기와 유일해 풀이기

STARLINK의 DAILY는 서버 없이 돌아간다. 퍼즐 데이터를 내려받지 않고, 각 기기가 날짜 문자열을 시드로 삼아 직접 퍼즐을 만든다. 그러려면 같은 시드가 어느 브라우저에서나 같은 퍼즐을 내야 하고, 그 퍼즐은 답이 하나뿐이어야 좋다. 이 글은 그 두 조건을 맞춘 생성기와 풀이기의 구조, 그리고 직접 돌려 본 수치를 다룬다.

결정성의 조건: 난수와 부동소수점

시드가 같으면 결과가 같아야 한다는 조건은 두 군데서 깨질 수 있다. 첫째는 난수다. Math.random()은 시드를 줄 수 없으므로 정수 연산만으로 동작하는 mulberry32를 쓰고, 시드 문자열은 32비트 해시로 바꿔 넣는다. DAILY의 시드는 starlink-daily-YYYY-MM-DD 형식이다.

둘째는 부동소수점 계산이다. 덧셈·곱셈·제곱근은 IEEE 754가 정확한 반올림을 요구하므로 어느 엔진에서도 같은 값을 낸다. 반면 Math.cos나 Math.atan2 같은 초월 함수는 명세가 결과를 비트 단위로 정하지 않아 브라우저마다 마지막 자리가 다를 수 있다. 각도 하나가 경계값 근처에서 미세하게 달라지면 어떤 기기에서는 후보 선이고 다른 기기에서는 아닌 상황이 생기고, 그 뒤의 난수 소비 순서가 전부 어긋난다. 그래서 기하 함수는 외적과 내적, 제곱근만으로 짰다. 중력 별의 꺾임 각도 검사조차 각도를 구하지 않고 코사인 값을 내적으로 직접 비교한다.

// js/rng.js 발췌
function mulberry32(a){
  return function(){ a|=0; a=a+0x6D2B79F5|0;
    let t=Math.imul(a^a>>>15,1|a); t=t+Math.imul(t^t>>>7,61|t)^t;
    return ((t^t>>>14)>>>0)/4294967296; };
}

생성 파이프라인

생성은 네 단계로 이뤄진다. 첫 단계는 배치다. 격자 칸 목록을 섞어 앞에서부터 별을 하나씩 놓되, 칸 중심에서 조금씩 흔들고 다른 별과 1칸 이상 떨어지게 한다. 중력 별은 판 중심에 가까운 별 가운데서 고른다. 가장자리에 있는 중력 별은 주변에 중계할 별이 적어 쓸모가 없기 때문이다.

두 번째 단계에서 후보 선을 만든다. 길이 3.2칸 이하이면서 다른 별에 가려지지 않는 별 쌍이 직선 후보가 되고, 중력 별마다 휘는 선 후보를 따로 구한다. 이어서 모든 후보 쌍의 충돌 여부를 미리 계산해 충돌 표를 만든다.

세 번째가 정답 만들기다. 직선 후보를 섞어 순서대로 보면서 서로 다른 덩어리를 잇는 선만 고르면 교차 없는 신장 트리가 된다(유니온 파인드 사용). 여기에 중력 별마다 휘는 선을 하나 또는 둘(40% 확률로 둘) 붙이고, 남은 후보를 난이도별 확률(EASY .15부터 EXPERT .35까지)로 더해 밀도를 높인다. 모든 단계에서 교차와 최대 숫자를 검사한다. 별이 하나라도 고립되거나 휘는 선을 하나도 못 받은 중력 별이 생기면 배치부터 다시 한다.

마지막으로 정답에서 각 별의 차수를 세어 숫자로 적는다. 숫자를 먼저 정하고 답을 찾는 방식보다 답을 먼저 만들고 숫자를 역산하는 쪽이 "풀 수 있는 퍼즐"을 보장하기 훨씬 쉽다.

풀이기: 전파 두 줄과 분기

답이 존재하는 것과 답이 하나뿐인 것은 다른 문제다. 숫자만 보고 논리로 풀어 가는 퍼즐에서 답이 둘이면, 어딘가에서 근거 없이 찍어야 하는 순간이 생긴다. 그래서 생성할 때마다 풀이기로 해의 수를 센다.

풀이기는 각 후보 선을 "놓음/안 놓음" 변수로 본다. 전파 규칙은 두 줄이다. 별의 남은 필요 수가 0이면 그 별의 미정 후보를 모두 지우고, 남은 후보 수가 남은 필요 수와 같으면 모두 놓는다. 선을 하나 놓으면 충돌 표에 걸린 후보가 함께 지워지고, 그 결과가 다시 전파를 일으킨다. 전파가 멈추면 "남은 후보 수 − 필요 수"가 가장 작은 별, 즉 선택지가 가장 좁은 별의 후보 하나로 분기한다. 잎에 도달하면 모든 숫자가 0인지, 별이 하나로 이어졌는지 확인한다.

해를 전부 셀 필요는 없다. 두 번째 해를 찾는 순간 "유일하지 않음"이 확정되므로 거기서 멈춘다. 탐색 노드가 15만 개를 넘으면 중단하고 그 퍼즐은 유일하다고 보지 않는다. 전파 규칙이 사람이 쓰는 추론과 같다는 점도 의도한 부분이다. 공략 가이드의 "숫자와 이웃 수가 같으면 전부 잇기" 팁은 이 전파 규칙을 그대로 풀어 쓴 것이다.

실측: 얼마나 자주 유일해가 나오나

저장소의 puzzle.js를 Node에서 그대로 불러 난이도마다 시드 60개로 생성해 봤다. 측정 환경은 개발 PC 한 대라 시간은 참고용이다. 아래 표는 1.0.0 풀이기가 스스로 보고한 값인데, 뒤에 적은 풀이기 버그 때문에 HARD·EXPERT의 유일해 비율은 실제보다 크게 부풀려져 있었다. 고친 뒤의 값은 "1.0.1에서 고친 것"에 있다.

유일해가 아니면 같은 난수 흐름에서 배치부터 다시 뽑는데, 최대 30번까지 시도한다. 1.0.0은 30번 안에 찾지 못하면 첫 번째로 만들어진 퍼즐을 그대로 썼다(1.0.1부터는 해가 가장 적은 후보를 쓴다). 설계 문서 초안에는 "40회, 시간 예산 1.5초"라고 적혀 있었지만 구현은 30회·노드 15만 개 한도로 정리됐고 시간 예산은 들어가지 않았다. 설계 문서도 1.0.1에서 이 값으로 고쳤다. 시간 대신 노드 수로 끊어야 기기 속도와 무관하게 같은 퍼즐이 나온다. 위 표처럼 EXPERT도 한 번 생성에 수십 밀리초가 걸리지 않으니 시간 제한 없이도 체감 지연이 없다.

재시도가 같은 난수 흐름을 이어 쓴다는 점도 중요하다. 매번 시드를 새로 파생하지 않고 하나의 RNG를 계속 소비하므로, 몇 번째 시도에서 성공하든 그 과정 전체가 시드에 의해 결정된다. 기기마다 성공한 시도 번호가 달라질 일이 없다.

다중해를 허용한 이유와 그 부작용

30번 안에 유일해를 못 찾으면 생성을 실패로 처리하는 방법도 있었다. 하지만 DAILY는 그날 퍼즐이 반드시 나와야 하고, 무한 재시도는 저사양 기기에서 멈춤으로 이어질 수 있다. 그래서 유일성은 품질 목표로만 두고, 승리 판정은 정답과의 비교가 아닌 규칙 검사로 했다. 다중해 퍼즐이 나와도 규칙대로 푼 사람은 완성 처리된다. FREE PLAY에서는 상단에 "유일해/다중해"를 표시해 숨기지 않았다.

부작용도 하나 있다. 힌트는 생성기의 정답을 기준으로 동작해서, 놓인 선 가운데 정답에 없는 선을 먼저 지운다. 다중해 퍼즐에서는 다른 해에서는 맞는 선이 지워질 수 있다. 측정상 이런 퍼즐은 HARD·EXPERT의 몇 퍼센트 수준이라고 봤지만, 실제로는 그보다 훨씬 많았다. 아래에서 고친 내용을 적는다.

1.0.1에서 고친 것

풀이기 버그. 힌트를 고치려고 "다른 해"를 찾다가, 생성기가 만든 정답이 있는데도 풀이기가 해를 0개로 보고하는 퍼즐을 발견했다. 원인은 되돌리기였다. 선을 놓거나 지울 때 끝점 별의 필요 수·남은 후보 수를 하나씩 줄이다가 모순이 보이면 바로 실패를 돌려줬는데, 되돌리기는 그 선의 끝점 전부를 복구했다. 줄이지 않은 끝점까지 늘려 놓으니 필요 수가 부풀었고, 이후 탐색에서 실제 해가 잘려 나갔다. 해를 놓치는 풀이기는 두 번째 해도 놓치므로 "유일해"를 과대 보고한다. 같은 시드 60개를 고친 풀이기로 다시 세어 보니 1.0.0의 실제 유일해는 EASY 58/60, NORMAL 56/60, HARD 32/60, EXPERT 25/60이었고, 다중해 퍼즐 중에는 해가 수백 개인 것도 있었다. 끝점을 모두 갱신한 뒤에 검사하도록 바꿨다.

대체 퍼즐 선택. 30번 안에 유일해가 없을 때 첫 번째 후보 대신, 시도마다 해를 64개까지 세어 가장 적은 후보를 쓴다. 노드 한도에 걸린 후보는 꼴찌, 동률이면 앞선 시도라서 결과는 여전히 시드만으로 정해진다. 마지막 후보를 쓰는 안도 비교했는데, 시드 300개 기준 다중해 퍼즐의 평균 해 개수가 HARD 첫 번째 25.0·마지막 20.8·최소 2.1, EXPERT 첫 번째 70.9·마지막 93.5·최소 2.1이었다. 첫 번째와 마지막은 어차피 무작위 후보 하나라 나을 게 없었다.

유일해가 아닌 경우에도 해는 2~4개뿐이다. 생성기가 바뀌었으므로 2026-10-14부터 90일 가운데 34일의 DAILY 퍼즐이 달라졌다. 저장된 진행은 선 번호로 기록되므로, 퍼즐 서명을 함께 저장해 다른 퍼즐에 엉뚱한 선이 복원되지 않게 했다.

힌트. 풀이기에 "반드시 넣을 선" 목록을 받는 옵션을 더해, 지금 놓인 선을 모두 포함하는 해를 찾아 그 해 기준으로 빠진 선을 보여 준다. 그런 해가 없으면 어떤 해에도 들어갈 수 없는 선부터 지우고, 선 하나하나는 가능하지만 함께 쓸 수 없는 경우에는 생성기 정답의 선부터 차례로 쌓아 처음 모순을 일으키는 선을 지운다. 탐색은 노드 4만 개와 250ms 안에서 끝나야 하고, 넘기면 힌트를 쓰지 않은 채 안내만 띄운다. 다중해 퍼즐 209개에서 두 해의 선을 섞어 놓고 시험했을 때 지운 선은 모두 실제로 모순을 일으키는 선이었고, 다른 해의 선만 놓은 39개 상태에서는 한 번도 선을 지우지 않았다. 힌트 한 번 계산은 가장 오래 걸린 경우 0.5ms였다.

정리

서버 없이 "모두에게 같은 퍼즐"을 주려면 난수와 기하 계산 양쪽에서 기기 차이가 끼어들 틈을 없애야 했다. 정수 기반 RNG, 초월 함수를 쓰지 않는 기하, 하나의 RNG를 이어 쓰는 재시도가 그 역할을 한다. 유일성은 전파 두 줄과 최소 선택지 분기로 된 작은 풀이기가 검사하고, 1.0.1에서 그 풀이기의 되돌리기 버그를 고친 뒤 측정하니 HARD 90%, EXPERT 77%가 유일해이고, 나머지도 해가 2~4개다. 힌트는 이제 현재 배치와 양립하는 해를 기준으로 한다. EXPERT의 유일해 비율을 더 올리는 일은 생성 단계(추가 선 확률, 재시도 횟수) 조정으로 남겨 둔다.

글: ROGA GAME 개발팀 · 이 글은 실제 개발 기록(설계 문서·변경 이력)을 바탕으로 작성했습니다.