PlayTalk에 혼자 하는 스도쿠를 붙였습니다. 문제를 어디서 받아올까 잠깐 고민했는데, 스도쿠는 생성 알고리즘 자체가 잘 알려져 있어서 직접 만들기로 했어요. 결과적으로 로직 파일은 150줄이 됐고, 외부 라이브러리도 서버 통신도 없습니다. 브라우저에서 즉석으로 만들어 냅니다.
과정을 정리해 봤습니다.
1단계: 완성판부터 만든다
스도쿠 문제를 만드는 순서는 직관과 반대입니다. 빈칸이 있는 문제를 만드는 게 아니라, 꽉 찬 정답판을 먼저 만들고 거기서 칸을 지웁니다.
완성판 생성은 평범한 백트래킹입니다. 0번 칸부터 81번 칸까지 순서대로, 규칙에 맞는 숫자를 넣어보고 막히면 되돌아가요.
function fill(board, pos, rand) {
if (pos === 81) return true;
const r = Math.floor(pos / 9), c = pos % 9;
const nums = shuffle([1,2,3,4,5,6,7,8,9], rand); // ← 이 한 줄이 랜덤성을 만든다
for (const v of nums) {
if (isValid(board, r, c, v)) {
board[r][c] = v;
if (fill(board, pos + 1, rand)) return true;
board[r][c] = 0; // 되돌리기
}
}
return false;
}포인트는 shuffle입니다. 1부터 9까지 순서대로 시도하면 매번 똑같은 완성판이 나옵니다. 시도 순서를 섞는 것만으로 매번 다른 판이 나와요. 별도의 랜덤화 단계가 필요 없습니다.
2단계: 유일해를 세되, 2개째에서 멈춘다
이제 칸을 지워야 하는데, 아무 칸이나 지우면 안 됩니다. 답이 두 개 이상 나오는 문제는 스도쿠가 아니거든요. 그래서 칸을 지울 때마다 "이 문제의 답이 여전히 하나뿐인가"를 확인해야 합니다.
여기서 흔한 실수가 해를 전부 세는 것입니다. 답이 1000개인 판을 만나면 1000개를 다 세고 앉아 있게 돼요. 우리한테 필요한 정보는 "1개냐, 2개 이상이냐" 뿐입니다.
// 해의 개수를 최대 limit까지만 센다(유일해 판정은 limit=2). 2개째를 찾는 즉시 중단.
export function countSolutions(board, limit = 2) {
...
for (let v = 1; v <= 9; v++) {
if (isValid(work, r, c, v)) {
work[r][c] = v;
solve();
work[r][c] = 0;
if (count >= limit) return; // 한계 도달 시 조기 종료
}
}
}limit = 2로 두고 2개째를 찾는 순간 탐색을 접습니다. 이 한 줄이 생성 속도를 좌우합니다. 유일해가 깨진 판일수록 해가 폭발적으로 많은데, 그런 판을 만났을 때 바로 손절하니까요.
3단계: 한 패스만 훑고 끝낸다 — 여기가 진짜 결정
칸 제거는 이렇습니다.
export function makePuzzle(difficulty, rand = Math.random) {
const solution = generateSolved(rand);
const puzzle = solution.map(row => row.slice());
const target = DIFFICULTY_CLUES[difficulty] ?? DIFFICULTY_CLUES.medium;
let clues = 81;
const order = shuffle([...Array(81).keys()], rand); // 81칸을 랜덤 순서로
for (const idx of order) {
if (clues <= target) break; // 하한 도달 → 정지
const r = Math.floor(idx / 9), c = idx % 9;
const saved = puzzle[r][c];
puzzle[r][c] = 0;
if (countSolutions(puzzle, 2) === 1) {
clues--; // 유일해 유지 → 제거 확정
} else {
puzzle[r][c] = saved; // 유일해 깨짐 → 복원
}
}
return { puzzle, solution, clues };
}여기서 제가 의도적으로 넣지 않은 것이 있습니다. 재시도와 반복 패스입니다.
보통 스도쿠 생성기 예제를 보면 이런 구조가 많습니다. "목표 힌트 수(예: 정확히 26개)에 도달할 때까지 반복하고, 한 패스로 안 되면 완성판부터 다시 만든다." 이러면 정확한 난이도를 보장할 수 있어요.
대신 생성 시간이 들쭉날쭉해집니다. 운 나쁘면 완성판을 몇 번씩 다시 만들고, 그 사이 화면은 멈춰 있습니다. 이건 브라우저에서 동기로 도는 코드예요. 사용자가 난이도를 누른 뒤 얼마나 기다릴지 예측할 수 없다는 뜻입니다.
그래서 반대로 갔습니다. 81칸을 랜덤 순서로 딱 한 번만 훑고 끝냅니다. 대신 난이도 값의 의미를 "정확한 힌트 수"가 아니라 "하한" 으로 정의했어요.
// 난이도별 "하한 힌트 수" — 정확한 개수 보장이 아니라, 남은 힌트가 이 값 이하로
// 내려가지 않도록 멈추는 기준. 실제 힌트 수는 이 값 이상(대개 조금 많음).
export const DIFFICULTY_CLUES = { easy: 50, medium: 42, hard: 36 };즉 "어려움은 힌트가 정확히 36개"가 아니라 "36개보다 적어지지는 않는다"입니다. 실제로는 대개 그보다 몇 개 많이 나와요. 난이도 정확도를 약간 포기하고 생성 시간의 예측 가능성을 샀습니다. 게임을 시작하는 순간의 체감이 훨씬 중요하다고 봤거든요.
이런 트레이드오프는 알고리즘 자체의 문제가 아니라 어디에 쓰는 알고리즘인가의 문제인 것 같습니다. 서버에서 미리 문제를 만들어 캐싱하는 구조였다면 저는 반대로 골랐을 겁니다.
난이도 하한을 나중에 올린 이야기
처음 배포한 값은 { easy: 40, medium: 32, hard: 26 }이었습니다. 일반적인 스도쿠 기준으로는 타당한 숫자예요.
직접 해보니 너무 어려웠습니다. PlayTalk은 채팅하다가 심심할 때 잠깐 하는 미니게임 모음이지, 스도쿠 앱이 아니거든요. '쉬움'을 골랐는데 한참 노려봐야 하면 그 화면을 다시 안 열게 됩니다.
그래서 세 난이도 모두 +10을 해서 { 50, 42, 36 }으로 올렸습니다. 상수 한 줄 수정이지만 게임의 성격을 바꾸는 결정이었어요.
같이 넣은 게 도움(힌트) 기능입니다. 난이도별로 횟수를 주고(쉬움 12 / 보통 9 / 어려움 6), 누르면 빈칸 하나가 정답으로 채워집니다. 정답판(solution)을 이미 들고 있으니 구현은 간단했어요. 막혔을 때 포기하고 나가는 대신 계속하게 만드는 장치입니다.
(참고로 이 도움 기능의 "숫자가 날아가는 애니메이션"이 PC에서만 안 보이는 버그가 있었는데, 그건 따로 글로 정리했습니다.)
판정 로직: 빨강 > 연두
플레이 중 피드백은 두 가지입니다.
- 규칙 위반(같은 행/열/박스에 중복): 반투명 빨강
- 완성된 유닛(1~9가 빠짐없이 채워진 행/열/박스): 반투명 연두
둘 다 매 입력마다 전체 보드를 다시 계산합니다. 81칸짜리라 부담이 없어서 증분 갱신 같은 최적화는 넣지 않았어요. 겹칠 때는 빨강이 이깁니다. 잘못된 걸 알려주는 게 잘한 걸 칭찬하는 것보다 급하니까요.
const bg = conflict ? 'rgba(239,68,68,0.38)' // 오류 우선
: done ? 'rgba(34,197,94,0.30)'
: fixed ? '#f1f5f9'
: '#ffffff';로직과 렌더를 분리해 둔 것
sudokuLogic.js에는 React가 한 글자도 없습니다. 순수 함수만 있어요. PlayTalk의 다른 게임들(오목의 renju.js, 체스의 chessLogic.js)과 같은 구조입니다.
이렇게 해두면 좋은 점이 확실합니다. 생성기가 이상하게 동작할 때 컴포넌트를 띄우지 않고 Node에서 바로 돌려볼 수 있어요. 힌트 개수 분포를 보려고 1000번 돌려본 것도 이 덕분이었습니다. 서버·소켓·랭킹과도 완전히 독립이라, 이 게임은 어떤 기록 경로도 호출하지 않습니다.
마치며
스도쿠 생성기는 알고리즘 자체는 교과서에 있는 그대로입니다. 실제로 시간을 쓴 건 "어디까지 정확하게 할 것인가" 를 정하는 쪽이었어요. 유일해는 타협할 수 없지만, 힌트 개수는 타협할 수 있고, 그 타협이 사용자 체감(즉시 시작)을 삽니다.
👉 PlayTalk 에서 직접 풀어보실 수 있습니다.
