Rust와 WebAssembly를 이용한 Slitherlink 퍼즐 엔진 구축

Source: Dev.to

왜 Rust인가?

Slitherlink 생성은 계산 비용이 많이 듭니다. 10×10 격자에는 가능한 가장자리가 220개 있습니다. 엔진은 다음을 수행해야 합니다:

• 유효한 폐쇄 루프 생성
• 숫자 힌트 배치
• 퍼즐에 정확히 하나의 해가 있는지 검증
• 필요한 풀이 기법에 기반한 난이도 평가

JavaScript로는 이를 효율적으로 처리할 수 없었습니다. Java가 첫 시도였으며(작동했지만), Rust를 사용하면 10~50배의 속도 향상을 얻었고 클라이언트 측 해결을 위해 WebAssembly로 컴파일할 수 있는 옵션도 얻었습니다.

Source: …

아키텍처

단계 1: 루프 생성

빈 격자에서 시작합니다. 하나의 닫힌 루프를 형성하는 무작위 해밀턴‑유사 경로를 구축합니다:

·───·   ·───·───·
│       │       │
·   ·───·   ·   ·
│   │       │   │
·   ·   ·───·   ·
│   │   │       │
·───·   ·───·───·

알고리즘은 백트래킹을 포함한 무작위 DFS를 사용합니다. 핵심 제약: 루프가 지나가는 모든 정점은 정확히 차수 2(진입선 1개, 탈출선 1개)를 가져야 합니다.

단계 2: 힌트 배치

각 셀 주변의 변을 세어 숫자를 생성합니다:

·───·   ·───·───·
│ 2   1 │ 2   3 │
·   ·───·   ·   ·
│ 2 │ 2     2 │ 2
·   ·   ·───·   ·
│ 1 │ 1 │ 2   2 │
·───·   ·───·───·

그런 다음 일부 숫자를 선택적으로 제거하여 퍼즐을 만듭니다. 더 많은 숫자를 제거하면 퍼즐이 어려워질 수 있지만, 난이도는 몇 개가 남았는지가 아니라 어떤 숫자가 남았는지에 따라 달라집니다.

단계 3: 유일성 검증

이 단계가 가장 비용이 많이 듭니다. 풀이 프로그램은 정확히 하나의 해만 존재함을 확인해야 합니다:

• 제약 전파 – 알려진 모든 패턴(코너 규칙, 인접 3‑3, 정점 차수)을 완전히 적용합니다.
• 백트래킹 – 전파가 멈추면, 결정되지 않은 변을 선택하고 두 상태(선 있음 / 선 없음)를 시도하며 각각을 전파합니다.
• 유일성 검사 – 두 분기 모두 유효한 해를 만든다면 퍼즐은 다중 해를 갖는 것이므로 폐기합니다.

fn solve(puzzle: &Puzzle) -> usize {
    propagate_all_constraints(puzzle);
    if puzzle.is_contradictory() {
        return 0; // no solution
    }
    if puzzle.is_fully_decided() {
        return 1; // one solution found
    }
    let e = puzzle.pick_undecided_edge();
    let mut count = 0;
    // try edge = line
    let mut p1 = puzzle.clone();
    p1.set_edge(e, true);
    count += solve(&p1);
    // try edge = no line
    let mut p2 = puzzle.clone();
    p2.set_edge(e, false);
    count += solve(&p2);
    count // total solutions
}

전체 해의 수가 1을 초과하면 퍼즐은 모호하므로 버려집니다.

단계 4: 난이도 평가 (10 단계)

우리는 단순히 힌트 개수를 세는 것이 아니라 해결에 필요한 기법을 측정합니다:

평가 엔진은 인간 풀이자를 시뮬레이션합니다: 복잡도 순서대로 기법을 적용하고, 진행에 필요한 최고 레벨의 기법을 추적합니다. 사용된 가장 높은 기법 레벨이 퍼즐의 난이도가 됩니다.

fn rate_puzzle(puzzle: &Puzzle) -> u8 {
    let mut max_level = 1;
    let mut state = SolverState::new(puzzle);

    loop {
        if state.apply_corner_rules() { max_level = max(max_level, 1); continue; }
        if state.apply_adjacent_patterns() { max_level = max(max_level, 3); continue; }
        if state.apply_vertex_degree() { max_level = max(max_level, 5); continue; }
        if state.apply_loop_closure() { max_level = max(max_level, 7); continue; }
        if state.apply_bifurcation() { max_level = max(max_level, 9); continue; }
        break;
    }
    max_level
}

WebAssembly 로 컴파일하기

Rust 엔진은 wasm-pack을 사용해 WASM으로 컴파일합니다:

wasm-pack build --target web --release

생성된 .wasm 바이너리는 약 200 KB 크기로, 브라우저에서 다음 용도로 실행됩니다:

• 클라이언트‑사이드 퍼즐 검증 (안티‑치트)
• 힌트 생성
• 솔루션 검증

배치 생성(3000개 이상의 퍼즐을 미리 생성)에는 네이티브 바이너리를 사용합니다:

./slitherlink-engine gen --grid-size 10 --level 6 --count 100

이 명령은 표준 출력에 JSON을 출력합니다 — 각 줄마다 하나의 퍼즐이 grid_size, clues, solution, 그리고 difficulty 등급을 포함합니다.

Production Pipeline

Rust engine (batch generate)
    → JSON puzzles
    → Import to Cloudflare D1 database
    → CF Worker API serves puzzles
    → Next.js frontend renders with Phaser 3

데이터베이스에는 5가지 그리드 크기(5×5, 7×7, 8×8, 10×10, 12×12)와 10개의 난이도 수준을 아우르는 3000개 이상의 퍼즐이 저장되어 있습니다. API는 크기와 난이도로 필터링된 무작위 퍼즐 선택, 일일 챌린지, 그리고 리더보드를 지원합니다.

숫자

• 생성 속도: 10×10 레벨 5‑6 기준으로 분당 약 50개 퍼즐
• WASM 번들: gzipped 200 KB
• 해결 시간 (WASM, 10×10): . 난이도 평점은 실제입니다: 레벨 1은 부드럽게 느껴지고; 레벨 8은 땀을 흘리게 합니다.