Привет, Хабр.

Я работаю учителем математики и информатики в солнечном Таиланде. Во время школьных каникул, вместо регулярных путешествий по Азии я решил развлечь себя изучением синтаксиса JavaScript.

Когда-то, мы с моей замечательной (но ныне бывшей) женой фанатели от нестандартных судоку со знаками «больше-меньше», мы сами печатали себе уникальные сетки, а иногда, я даже рисовал их руками на основе готовых шаблонов из интернета.

В этой статье я хочу рассказать об эволюции моего математического движка генерации сеток судоку: от наивного перетаскивания массивов к строгой комбинаторике и факториальной системе счисления.

Версия 1. Наивное перемешивание

Идея первой версии была до банального проста. Зачем генерировать сетку с нуля, решая NP-полную задачу с бэктрекингом, если можно взять одну готовую, 100% валидную сетку и хорошенько её «перемешать»?

Правила классического судоку позволяют нам делать несколько геометрических преобразований, которые не ломают логику решения:

1.     Менять местами любые две строки внутри одного горизонтального блока 3х3.

2.     Менять местами любые два столбца внутри вертикального блока 3х3.

3.     Менять местами сами крупные блоки строк (3х9) и столбцов (9х3) целиком.

С самого начала элегантным решением казалось работать с сидом вида: 3 блока по 6 шестнадцатеричных символов. Такой можно было бы легко распаковать в бинарный ряд флагов для операций перемешивания.

Я написал простенький хэш, который брал 18-значный сид, превращал его в массив битов, и на основе этих нулей и единиц применял (или пропускал) функции перемешивания к базовой матрице.

// Базовая сетка для перемешивания
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]
];

// МАТЕМАТИЧЕСКИЙ ДВИЖОК И ЛОГИКА ГЕНЕРАЦИИ СЕТКИ v1

const Utils = {
  // Генератор псевдослучайных чисел (алгоритм Mulberry32)
  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, b2 * 3 + i); }
  }
};

// Массив доступных трансформаций, вызываются на основе битов сгенерированных из сида
const PROCEDURES = [
  g => Utils.transforms.swapColBlocks(g, 0, 1),
  g => Utils.transforms.swapCols(g, 0, 1),
  g => Utils.transforms.swapRows(g, 0, 1),
  g => Utils.transforms.swapCols(g, 0, 2),
  g => Utils.transforms.swapRowBlocks(g, 0, 1),
  g => Utils.transforms.swapRows(g, 0, 2),
  g => Utils.transforms.swapCols(g, 1, 2),
  g => Utils.transforms.swapRows(g, 1, 2),
  g => Utils.transforms.swapColBlocks(g, 0, 2),
  g => Utils.transforms.swapCols(g, 3, 4),
  g => Utils.transforms.swapRows(g, 3, 4),
  g => Utils.transforms.swapCols(g, 3, 5),
  g => Utils.transforms.swapRowBlocks(g, 0, 2),
  g => Utils.transforms.swapRows(g, 3, 5),
  g => Utils.transforms.swapCols(g, 4, 5),
  g => Utils.transforms.swapRows(g, 4, 5),
  g => Utils.transforms.swapColBlocks(g, 1, 2),
  g => Utils.transforms.swapCols(g, 6, 7),
  g => Utils.transforms.swapRows(g, 6, 7),
  g => Utils.transforms.swapCols(g, 6, 8),
  g => Utils.transforms.swapRowBlocks(g, 1, 2),
  g => Utils.transforms.swapRows(g, 6, 8),
  g => Utils.transforms.swapCols(g, 7, 8),
  g => Utils.transforms.swapRows(g, 7, 8)
];

async function generate(seedStr) {
  // ... валидация сида и инициализация ...
  const grid = BASE_GRID.map(row => [...row]);
  
  // Первый прогон применяем базовые математические трансформации для создания решения
  for (let i = 0; i < 3; i++) {
    const bits = Utils.hexToBits(clean.slice(i * 6, i * 6 + 6));
    bits.forEach((bit, idx) => { 
      if (bit && PROCEDURES[idx]) PROCEDURES[idx](grid); 
    });
  }
  // Второй прогон для усиления влияния конца сида со смещением
  for (let i = 0; i < 3; i++) {
    const bits = Utils.hexToBits(clean.slice(i * 6, i * 6 + 6));
    bits.forEach((bit, idx) => { 
      const newIdx = (idx + 5) % PROCEDURES.length;
      if (bit && PROCEDURES[newIdx]) PROCEDURES[newIdx](grid); 
    });
  }
  GameState.solutionGrid = grid;
  // ... рендер
}

Версия 2. Борьба с паттернами

Очень быстро я обнаружил существенный изъян генерации в первой версии. Дело в том, что из-за ограниченного набора свопов (только строки и столбцы) состав групп цифр оставался неизменным. Появлялся паттерн, который легко замечал человеческий глаз: в каждом блоке 3х3 всегда находилась строка, в которой в разном порядке повторялись первые три цифры самого первого верхнего левого блока 3х3. Геометрия сетки менялась, но математическое нижнее бельё торчало наружу.

Чтобы решить эту проблему, я добавил глобальную подмену самих цифр. Если мы во всей сетке заменим все единицы на девятки, а девятки на единицы, судоку от этого не перестанет быть правильным. Я добавил в массив PROCEDURES ещё восемь свопов, которые глобально меняли цифры местами (например, тройки с пятерками).

JavaScript

// МАТЕМАТИЧЕСКИЙ ДВИЖОК И ЛОГИКА ГЕНЕРАЦИИ СЕТКИ v2

const Utils = {
  // ... старые утилиты ...
  transforms: {
    // ... старые свопы строк и колонок ...
    // Глобальная замена двух цифр местами
    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;
        }
      }
    }
  }
};

// Массив доступных трансформаций (с математической некоммутативностью)
const PROCEDURES = [
  g => Utils.transforms.swapColBlocks(g, 0, 1),
  g => Utils.transforms.swapCols(g, 0, 1),
  g => Utils.transforms.swapRows(g, 0, 1),
  g => Utils.transforms.swapDigits(g, 1, 9), // НОВАЯ ТРАНСФОРМАЦИЯ
  // ...
  g => Utils.transforms.swapDigits(g, 2, 8),
  // ...
  g => Utils.transforms.swapDigits(g, 3, 7),
  // ...
  g => Utils.transforms.swapDigits(g, 4, 6),
  // ...
];

async function generate(seedStr) {
  // ...
  const grid = BASE_GRID.map(row => [...row]);
  const allBits = Utils.hexToBits(clean); 
  
  // Три прогона с разными смещениями для максимальной хаотичности
  allBits.forEach((bit, idx) => { if (bit) PROCEDURES[idx % PROCEDURES.length](grid); });
  allBits.forEach((bit, idx) => { if (bit) PROCEDURES[(idx + 13) % PROCEDURES.length](grid); });
  allBits.forEach((bit, idx) => { if (bit) PROCEDURES[(idx + 29) % PROCEDURES.length](grid); });
  
  GameState.solutionGrid = grid;
  // ...
}

Версия 3. Биекция и факториалы

Движок работал, паттерны исчезли. Но затем, я серьезно задумался об уникальности сида. При последовательном применении трансформаций (тем более с битовыми масками и случайными смещениями) мы неизбежно сталкиваемся с коллизиями. Два разных сида могли сгенерировать одинаковую сетку, а некоторые трансформации всё ещё могли отменять друг друга. Мне нужна была жесткая связь: 1 сид = 1 уникальная сетка.

Я решил отказаться от физического перетаскивания элементов массива в памяти и посчитать всё математически. Сколько вообще уникальных сеток можно получить из одного базового шаблона с помощью этих операций?

Перестановка 9 цифр: 9! вариантов.

Перестановка 3 крупных блоков строк: 3!

Перестановка 3 крупных блоков столбцов: 3!

Перестановка линий внутри каждого из 3 блоков строк: (3!)^3

Перестановка линий внутри каждого из 3 блоков столбцов: (3!)^3

Перемножив это, мы получаем 609,492,049,920 уникальных комбинаций из одной базовой сетки.

Вместо того чтобы «двигать» массивы, мы можем превратить 18-значный hex-сид в огромное число BigInt. Берем остаток от деления этого числа на 609,492,049,920, чтобы безопасно закольцевать диапазон. А затем просто распаковываем полученное число N через остатки от деления на индексы для алгоритма факториальной системы счисления.

Теперь мы не перемешиваем массив. Мы за один проход O(N) вычисляем, какая цифра должна стоять в конкретной ячейке для данной перестановки.

JavaScript

// МАТЕМАТИЧЕСКИЙ ДВИЖОК И ЛОГИКА ГЕНЕРАЦИИ СЕТКИ v3
/*
алгоритм генерирует 609 492 049 920 уникальных комбинаций из одного базового шаблона,
эффективно используя математические свойства симметрии судоку. Общий объем вариантов складывается
из перемножения всех независимых трансформаций: перестановки 9 цифр (9!), перемешивания 3 крупных
блоков (3! * 3!) и ротации линий внутри каждого из них ((3!)^3 * (3!)^3). Благодаря такой
каскадной системе, 18-значный сид обеспечивает огромное разнообразие сеток, гарантируя, что игрок
практически никогда не встретит две одинаковые сетки, несмотря на использование всего одной исходной матрицы
*/

const Utils = {
  // Возвращает k-тую перестановку элементов массива (Алгоритм факториальной системы счисления)
  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;
  }
};

async function generate(seedStr) {
  // ... очистка и подготовка сида ...
  
  // МАТЕМАТИЧЕСКАЯ БИЕКЦИЯ (1 сид = 1 уникальная сетка)
  const MAX_PERMUTATIONS = 609492049920n;
  const seedBigInt = BigInt("0x" + clean);
  let N = Number(seedBigInt % MAX_PERMUTATIONS);
  
  // Распаковываем число N на составляющие остатки от деления для каждой группы перестановок
  const pDigits = Utils.getPermutation([1,2,3,4,5,6,7,8,9], N % 362880); N = Math.floor(N / 362880);
  const pRowBlocks = Utils.getPermutation([0,1,2], N % 6); N = Math.floor(N / 6);
  const pColBlocks = Utils.getPermutation([0,1,2], N % 6); N = Math.floor(N / 6);
  const pR0 = Utils.getPermutation([0,1,2], N % 6); N = Math.floor(N / 6);
  const pR1 = Utils.getPermutation([0,1,2], N % 6); N = Math.floor(N / 6);
  const pR2 = Utils.getPermutation([0,1,2], N % 6); N = Math.floor(N / 6);
  const pC0 = Utils.getPermutation([0,1,2], N % 6); N = Math.floor(N / 6);
  const pC1 = Utils.getPermutation([0,1,2], N % 6); N = Math.floor(N / 6);
  const pC2 = Utils.getPermutation([0,1,2], N % 6);
  const pRows = [pR0, pR1, pR2];
  const pCols = [pC0, pC1, pC2];
  
  // Собираем итоговую сетку напрямую из BASE_GRID без "физических" свопов
  const grid = [];
  for (let r = 0; r < 9; r++) {
    const rowArr = [];
    for (let c = 0; c < 9; c++) {
      // Находим координаты оригинальной ячейки с учетом перестановки блоков и линий внутри них
      const oldR = pRowBlocks[Math.floor(r / 3)] * 3 + pRows[Math.floor(r / 3)][r % 3];
      const oldC = pColBlocks[Math.floor(c / 3)] * 3 + pCols[Math.floor(c / 3)][c % 3];
      
      // Получаем старое значение ячейки и применяем к нему глобальную перестановку цифр
      const oldVal = BASE_GRID[oldR][oldC];
      rowArr.push(pDigits[oldVal - 1]);
    }
    grid.push(rowArr);
  }
  
  GameState.solutionGrid = grid;
  // ... рендер
}

Итоги

Этот путь наглядно показал мне, как важно иногда оторваться от редактора кода и посмотреть на задачу через призму математики. Итоговый алгоритм не просто избавился от коллизий и паттернов, но и стал работать элегантнее.

Вместо послесловия

Магия биекции настолько меня вдохновила, что я довел код до состояния готового продукта «для одного пользователя». Приложение работает прямо из одного HTML-файла без лишних библиотек, то чего мне не хватало во всех магазинах приложений. Вот так это выглядит на экране: