Sudoku JS 생성기: 쌍사와 팩토리얼

자바스크립트로 만드는 수수께끼 게임: 교환에서 계승 일대일 대응까지

게임 및 앱 개발자들은 고유한 수수께끼 그리드를 생성하는 과제에 직면한다. NP-완전 문제인 백트래킹을 해결하는 대신, 기존 유효한 그리드에 기하학적 변환을 적용하는 더 효율적인 방법이 있다. 이 알고리즘은 단순한 배열 섞기에서 시작해, 하나의 템플릿에서 609,492,049,920개의 고유한 구성으로 이어지는 수학적 일대일 대응으로 발전했다.

기본 그리드는 각 행, 열, 3×3 블록에 숫자 1~9가 정확히 한 번씩 포함된다. 유효한 변환은 이 불변성을 유지한다:

• 3×3 블록 내 행 순서 변경
• 3×3 블록 내 열 순서 변경
• 행 블록(3×9) 순서 변경
• 열 블록(9×3) 순서 변경
• 전역 숫자 치환

첫 번째 시도: 시드 기반 섞기

초기 방법은 18자리 16진수 시드를 사용해 교환 순서를 결정하는 비트를 생성했다. Mulberry32 알고리즘이 결정론적 난수 생성기를 제공했다.

const BASE_GRID = [
  [5,3,4, 6,7,8, 9,1,2],
  [6,7,2, 1,9,5, 3,4,8],
  [1,9,8, 3,4,2, 5,6,7],
  [8,5,9, 7,6,1, 4,2,3],
  [4,2,6, 8,5,3, 7,9,1],
  [7,1,3, 9,2,4, 8,5,6],
  [9,6,1, 5,3,7, 2,8,4],
  [2,8,7, 4,1,9, 6,3,5],
  [3,4,5, 2,8,6, 1,7,9]
];

const Utils = {
  seededRandom: (seed) => {
    return () => {
      let t = seed += 0x6D2B79F5;
      t = Math.imul(t ^ t >>> 15, t | 1);
      t ^= t + Math.imul(t ^ t >>> 7, t | 61);
      return ((t ^ t >>> 14) >>> 0) / 4294967296;
    };
  },
  hexToBits: (hex) => {
    return [...hex].flatMap(char => {
      const v = parseInt(char, 16);
      return [(v >> 3) & 1, (v >> 2) & 1, (v >> 1) & 1, v & 1];
    });
  },
  transforms: {
    swapRows: (g, r1, r2) => { [g[r1], g[r2]] = [g[r2], g[r1]]; },
    swapCols: (g, c1, c2) => { 
      for (let r = 0; r < 9; r++) [g[r][c1], g[r][c2]] = [g[r][c2], g[r][c1]]; 
    }, 
    swapRowBlocks: (g, b1, b2) => { 
      for (let i = 0; i < 3; i++) Utils.transforms.swapRows(g, b1 * 3 + i, b2 * 3 + i); 
    },
    swapColBlocks: (g, b1, b2) => { 
      for (let i = 0; i < 3; i++) Utils.transforms.swapCols(g, b1 * 3 + i, b1 * 3 + i); 
    }
  }
};

18개의 교환 절차를 포함한 배열을 시드에서 유도된 비트 마스크를 사용해 세 번 적용했다. 문제점: 블록 내 고정된 숫자 패턴으로 인해 시각적 반복이 발생했다.

두 번째 시도: 전역 숫자 교환 추가

8개의 swapDigits(d1, d2) 변환을 추가해 이러한 패턴을 제거했다. 이 함수는 전체 그리드를 스캔하며 특정 숫자를 다른 숫자와 모두 교환한다:

swapDigits: (g, d1, d2) => {
  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      if (g[r][c] === d1) g[r][c] = d2;
      else if (g[r][c] === d2) g[r][c] = d1;
    }
  }
}

절차 배열 길이에 대해 0, 13, 29를 모듈러 연산한 다양한 오프셋을 사용해 세 번의 통과를 수행했으며, 비가환 연산이 다양성을 보장했다.

세 번째 시도: 계승 일대일 대응

최종 버전은 배열 변환을 포기하고 직접 계산 방식을 채택했다. 총 고유 변환 수는 다음과 같다:

• 9개 숫자 순열: 9! = 362,880
• 3개 행 블록 순열: 3! = 6
• 3개 열 블록 순열: 3! = 6
• 3개 블록 내 행 순열: (3!)^3 = 216
• 3개 블록 내 열 순열: (3!)^3 = 216

총합: 9! × 3! × 3! × (3!)^3 × (3!)^3 = 609,492,049,920

18자리 16진수 시드는 BigInt로 변환 후 MAX_PERMUTATIONS로 나누어 나머지를 구한다. 숫자 N은 계승 수체계로 분해된다:

const Utils = {
  getPermutation: (arr, k) => {
    let available = [...arr];
    let result = [];
    let fact = 1;
    for (let i = 2; i < available.length; i++) fact *= i;
    for (let i = available.length - 1; i > 0; i--) {
      const idx = Math.floor(k / fact);
      result.push(available[idx]);
      available.splice(idx, 1);
      k %= fact;
      fact /= i;
    }
    result.push(available[0]);
    return result;
  }
};

// generate(seedStr) 내부:
const MAX_PERMUTATIONS = 609492049920n;
const seedBigInt = BigInt("0x" + clean);
let N = Number(seedBigInt % MAX_PERMUTATIONS);

const pDigits = Utils.getPermutation([1,2,3,4,5,6,7,8,9], N % 362880); N = Math.floor(N / 362880);
// ... 나머지 블록 및 줄 순열 처리

각 셀 [r][c]에 대해, 블록 및 블록 내 순열 인덱스를 기반으로 원래 좌표를 계산한다. 값은 BASE_GRID[oldR][oldC]에서 가져오며, pDigits를 통해 매핑된다.

주요 장점

• 결정론성: 하나의 시드는 항상 고유한 그리드를 생성한다
• 효율성: 배열 변환 없이 O(N) — 실시간 생성에 최적
• 고유성: 6×10¹¹ 가지 변형으로 18자리 시드와의 충돌을 완전히 제거
• 유효성: 모든 변환이 수수께끼의 불변성을 유지한다
• 이동성: 그리드는 시드만으로 완전히 결정되므로 플레이어 간 공유에 이상적

— Editorial Team