Hi there.
I’m a math and computer science teacher in sunny Thailand. During the school holidays, instead of my usual trips around Asia, I decided to entertain myself by diving into JavaScript syntax.
Once upon a time, my wonderful (now ex) wife and I were huge fans of non-standard Sudoku with “greater-than/less-than” signs. We used to print unique grids for ourselves, and sometimes I even drew them by hand from templates I found online.
In this article I want to tell the story of how my mathematical Sudoku grid generator evolved, from naive array shuffling to strict combinatorics and a full factorial number system.
Version 1. Naive shuffling
The idea behind the first version was ridiculously simple. Why generate a grid from scratch by solving an NP-complete backtracking problem when you can just take one ready-made, 100 % valid grid and shuffle it really well?
The rules of classic Sudoku allow several geometric transformations that don’t break the logic:
- Swap any two rows inside the same 3×3 horizontal band
- Swap any two columns inside the same 3×3 vertical stack
- Swap entire 3×9 row bands and 9×3 column stacks
From the very beginning it felt elegant to work with a seed in the form of 3 blocks of 6 hexadecimal characters each. Such a seed could be easily unpacked into a binary string of flags that would trigger or skip the shuffling operations.
I wrote a simple hash that took an 18-character seed, turned it into an array of bits, and used those 0s and 1s to apply (or skip) the shuffling functions on the base matrix.
javascript
// Base grid for shuffling
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]
];
// MATHEMATICAL ENGINE AND GRID GENERATION LOGIC v1
const Utils = {
// Mulberry32 pseudorandom number generator
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;
};
},
// Convert hexadecimal string to bit array
hexToBits: (hex) => {
return [...hex].flatMap(char => {
const v = parseInt(char, 16);
return [(v >> 3) & 1, (v >> 2) & 1, (v >> 1) & 1, v & 1];
});
},
// Set of valid Sudoku grid transformation functions
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); }
}
};
// Array of available transformations triggered by bits from the seed
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) {
// ... seed validation and initialization ...
const grid = BASE_GRID.map(row => [...row]);
// First pass, apply basic mathematical transformations to create a solution
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);
});
}
// Second pass to give more influence to the end of the seed (with offset)
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;
// ... rendering ...
}
Version 2. Fighting patterns
Very quickly I discovered a serious flaw in version 1. Because the set of swaps was limited to rows and columns only, the groups of digits stayed the same. A clear pattern appeared that the human eye could easily spot: in every 3×3 block there was always a row that contained the first three digits of the top-left block, just in a different order. The geometry changed, but the mathematical underwear was still showing.
To fix this I added a global digit substitution. Swapping all 1s with 9s (and vice versa) across the entire grid still produces a valid Sudoku. I extended the PROCEDURES array with eight more swaps that globally exchange pairs of digits (e.g. 3 <-> 5).
javascript
// MATHEMATICAL ENGINE AND GRID GENERATION LOGIC v2
const Utils = {
// ... previous utilities ...
transforms: {
// ... previous row/column swaps ...
// Global swap of two digits throughout the grid
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;
}
}
}
}
};
// Array of available transformations (with mathematical non-commutativity)
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), // NEW TRANSFORMATION
// ...
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);
// Three passes with different offsets for maximum chaos
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;
// ...
}
Version 3. Bijection and factorials
The engine worked, patterns disappeared. But then I started thinking seriously about seed uniqueness. With sequential transformations (especially with bit masks and random offsets) collisions were inevitable. Two different seeds could produce the same grid, and some transformations could still cancel each other out. I needed a hard bijection: 1 seed = 1 unique grid.
I decided to stop physically moving array elements in memory and calculate everything mathematically instead. How many unique grids can we actually get from one base template using these operations?
- Permutation of 9 digits: 9!
- Permutation of 3 row bands: 3!
- Permutation of 3 column stacks: 3!
- Permutation of lines inside each of the 3 row bands: (3!)^3
- Permutation of lines inside each of the 3 column stacks: (3!)^3
Multiplying all that gives 609,492,049,920 unique combinations from a single base grid.
Instead of shuffling arrays, we can turn the 18-character hex seed into a huge BigInt, take it modulo 609,492,049,920 to stay safely inside the range, and then unpack the resulting number N using the factorial number system.
Now we don’t shuffle anything. In a single O(N) pass we calculate exactly which digit should be in each cell for the given permutation.
javascript
// MATHEMATICAL ENGINE AND GRID GENERATION LOGIC v3
/*
The algorithm generates 609,492,049,920 unique combinations from a single base template,
efficiently using the mathematical symmetries of Sudoku. The total number of variants
is the product of all independent transformations: permutation of 9 digits (9!),
shuffling of 3 large bands (3! × 3!), and rotation of lines inside each of them
((3!)^3 × (3!)^3). Thanks to this cascading system, an 18-character seed provides
enormous variety, guaranteeing that the player will almost never see two identical grids
despite using only one source matrix.
*/
const Utils = {
// Returns the k-th permutation of an array (factorial number system algorithm)
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) {
// ... seed cleaning and preparation ...
// MATHEMATICAL BIJECTION (1 seed = 1 unique grid)
const MAX_PERMUTATIONS = 609492049920n;
const seedBigInt = BigInt("0x" + clean);
let N = Number(seedBigInt % MAX_PERMUTATIONS);
// Unpack number N into remainders for each permutation group
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];
// Build the final grid directly from BASE_GRID without any “physical” swaps
const grid = [];
for (let r = 0; r < 9; r++) {
const rowArr = [];
for (let c = 0; c < 9; c++) {
// Find the original cell coordinates taking into account band and line permutations
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];
// Get the original value and apply the global digit permutation
const oldVal = BASE_GRID[oldR][oldC];
rowArr.push(pDigits[oldVal - 1]);
}
grid.push(rowArr);
}
GameState.solutionGrid = grid;
// ... rendering ...
}
Conclusions
This journey clearly showed me how important it is to sometimes step away from the code editor and look at the problem through the lens of mathematics. The final algorithm not only eliminated collisions and patterns, it became much more elegant.
Instead of an afterword
The magic of bijection inspired me so much that I polished the code into a ready-to-use product “for one user”. The whole application runs from a single HTML file with no extra libraries - exactly what I was missing in all those app stores. Here’s how it looks on the screen:
Top comments (0)