Sudoku Generator Source Javascript Code
// Sudoku Generator Class by Glenn J. Schworak
//
// This software is shared under GPLv3 license.
// Please credit me if you use it in your product
// or as a model for a derivative work.
//
// This class is used to generate a Sudoku game
// board that includes a puzzle, solution and
// some other key values.
//
// To use this as a class, you can create the object
// with or without parameters (with is recommended)
// where board is any integer 0 or higher (zero = random)
// and level is 0-4 to indicate the numerical level
//
// sudoku = new Sudoku(board, level);
//
//
// To generate a new game without creating a new instance
// of the Sudoku object, call the initialize
//
// sudoku.initialize(board, level);
//
//
// Access the entire game object as a stand aline object
//
// game = sudoku.game();
//
//
// You can also access any of the exposed elements individually
//
// variable = sudoku.{element_name};
//
// status always "ok" unless there was an error
// board the board number used to generate the solution
// level the level number used to generate the puzzle
// levels an array of level names
// jitter data about how the solution was generated
// timing how lont it took to generate the solution in seconds
// puzzle the puzzle array
// solution the solution array
//
//
class Sudoku {
#level;
#levels;
#levelStart;
#board;
#rand;
#randCount;
#jitter;
#status;
#timing;
#solution;
#puzzle;
#emptyGrid;
#usedPattern;
// call the initialization when constructed
constructor(board = -1, level = -1) {
this.#levels = ["Easy", "Medium", "Hard", "Expert", "Evil"];
this.#levelStart = [35, 40, 45, 50, 55];
this.#emptyGrid = [
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
];
if (board >= 0 && level >= 0) {
this.initialize(board, level);
}
}
// return the individual game elements
status() { return this.#status; }
board() { return this.#board; }
level() { return this.#level; }
levels() { return this.#levels; }
levelStart() { return this.#levelStart; }
jitter() { return this.#jitter; }
timing() { return this.#timing; }
puzzle() { return this.#puzzle; }
solution() { return this.#solution; }
randCount() { return this.#randCount; }
usedPattern() { return this.#usedPattern; }
// initialize the class
initialize(board = 0, level = 1) {
var start = window.performance.now();
this.#level = Math.max(0, Math.min(this.#levels.length - 1, isNaN(level) ? 0 : Math.floor(level)));
this.#board = Math.max(0, isNaN(board) ? 0 : Math.floor(board));
this.#board = (this.#board == 0 ? Math.floor(10000000 + (Math.random() * 89999999)) : this.#board); // pick a fully random board if zero
this.randSeed(this.#board);
this.#jitter = 0;
this.#timing = 0;
this.#solution = this.#clone(this.#emptyGrid);
this.#puzzle = this.#clone(this.#emptyGrid);
this.#fillSolution();
this.#makePuzzle();
this.#status = (this.#jitter >= 0 ? 'ok' : 'too complex');
this.#timing = (window.performance.now() - start) / 1000;
}
// return the entire game object
game() {
return {
'status': this.#status,
'board': this.#board,
'level': this.#level,
'levels': this.#levels,
'levelStart': this.#levelStart,
'jitter': this.#jitter,
'timing': this.#timing,
'puzzle': this.#puzzle,
'solution': this.#solution,
};
}
// initialize the grid and fill the cells
// to create a solution
#fillSolution() {
var start = window.performance.now();
var steps = 0;
var goBack = 0;
this.#jitter = 0;
// move through each cell from 0 to 80
// filling them as we go and backing up
// when we get stuck
for (var x = 0; x < 81; ++x) {
if (window.performance.now() - start > 2000) {
// took more than 2 seconds so exit
// with a negative jitter to indicate
// the error.
this.#jitter = 0 - (1 + this.#jitter);
return;
}
var row = Math.floor(x / 9);
var col = x % 9;
var safe = this.#safeDigit(this.#solution, row, col);
if (safe > 0) {
// we have a safe digit so write it to the
// grid and reduce the amount we go back
// the next time we get stuck
++steps;
this.#solution[row][col] = safe;
goBack = Math.max(0, goBack - 1);
}
else {
// hit a bad cell so we need to go back
// several cells setting them to ZERO
// so we can try them again
++this.#jitter;
goBack += 3;
var y = Math.max(0, x - this.randRange(1, goBack));
for (var i = y; i <= x; ++i) {
row = parseInt(i / 9);
col = i % 9;
this.#solution[row][col] = 0;
}
x = y - 1;
}
}
this.#jitter = parseFloat(this.#jitter + "." + steps);
}
#removeOne(mirror, removedDigits, r, c, rotation = 0) {
var removed = 1;
var row = 0;
var col = 0;
switch (rotation) {
case 1:
row = c;
col = 8 - r;
break;
case 2:
row = 8 - r;
col = 8 - c;
break;
case 3:
row = 8 - c;
col = r;
break;
default:
row = r;
col = c;
}
removedDigits.push(this.#puzzle[row][col]);
this.#puzzle[row][col] = 0;
if (mirror && this.#puzzle[8 - row][8 - col] > 0) {
++removed;
removedDigits.push(this.#puzzle[8 - row][8 - col]);
this.#puzzle[8 - row][8 - col] = 0;
}
return removed;
}
// remove cells to make the solution
// into a puzzle based on the level
#makePuzzle() {
var removedDigits = [0];
var remove = this.#levelStart[this.#level];
var start = window.performance.now();
var row;
var col;
var oldRow;
var oldCol;
var dig;
var fail;
var r;
var c;
var i;
var j;
var full;
var found;
var possible;
var mirror = (this.randRange(0, 8 - this.#level) == 2);
var rotation = this.randRange(0, 3);
if (this.#jitter < 0) {
return; // the solution couldn't be created so exit now
}
this.#puzzle = this.#clone(this.#solution);
this.#usedPattern = false;
console.log("make " + (this.#usedPattern ? "pat" : "non") + " " + this.#level);
r = this.randRange(0, [7, 5, 2][this.#level]);
if (r == 0) {
// some special layouts exist
var g = this.#clone(this.#emptyGrid);
switch (this.#level) {
case 0:
this.#usedPattern = 1 + this.randRange(0, 1)
switch (this.#usedPattern) {
case 1:
for (i = 0; i < 3; ++i) {
for (j = 0; j < 3; ++j) {
var xo = this.randRange(0, 1);
var yo = this.randRange(0, 1);
for (var x = 0; x < 2; ++x) {
for (var y = 0; y < 2; ++y) {
r = i * 3 + y + yo;
c = j * 3 + x + xo;
if (removedDigits.length <= this.#levelStart[this.#level]) {
g[r][c] = 1;
}
}
}
}
}
break;
case 2:
for (i = 0; i < 3; ++i) {
for (j = 0; j < 3; ++j) {
r = i * 3;
c = j * 3;
g[r][c] = 1;
g[r + 1][c] = 1;
g[r][c + 1] = 1;
}
}
break;
}
for (r = 0; r < 9; ++r) {
for (c = 0; c < 9; ++c) {
if (g[r][c] == 1) {
this.#removeOne(false, removedDigits, r, c, rotation);
}
}
}
break;
case 1:
this.#usedPattern = 1 + this.randRange(0, 1);
switch (this.#usedPattern) {
case 1:
var odd = (this.randRange(0, 1) == 1);
for (i = 0; i < 3; ++i) {
for (j = 0; j < 3; ++j) {
odd = !odd;
for (var x = 0; x < 3; ++x) {
for (var y = 0; y < 3; ++y) {
r = i * 3 + y;
c = j * 3 + x;
if (((x + y) / 2 == parseInt((x + y) / 2) ? 0 : 1) == odd) {
g[r][c] = 1;
}
}
}
}
}
break;
case 2:
var odd = false;
var offset = this.randRange(0, 4);
for (i = 0; i < 9; ++i) {
for (j = 0; j < (odd ? 5 : 4); ++j) {
r = i;
c = (odd ? 8 - j : j);
g[r][(offset + c) % 9] = 1;
}
odd = !odd;
}
break;
}
for (r = 0; r < 9; ++r) {
for (c = 0; c < 9; ++c) {
if (g[r][c] == 1) {
this.#removeOne(false, removedDigits, r, c, rotation);
}
}
}
break;
case 2:
var t = 0;
var s = 0;
var p = this.randRange(0, 9);
while (s == 0 && t < 3) {
++t;
++p;
this.#puzzle = this.#clone(this.#solution);
this.#usedPattern = 1 + (p % 3);
switch (this.#usedPattern) {
case 1:
var x = this.randRange(8, 15);
for (r = 0; r < 9; ++r) {
for (c = 8 - r; c < 9; ++c) {
if (r + c > x) {
g[r][c] = 1;
} else {
g[8 - r][8 - c] = 1;
}
}
}
break;
case 2:
for (r = 0; r < 9; ++r) {
g[r][0] = 1;
g[r][8] = 1;
if (r > 1 && r < 7) {
g[r][2] = 1;
g[r][6] = 1;
}
if (r > 2 && r < 6) {
g[r][4] = 1;
}
}
for (c = 1; c < 8; ++c) {
g[0][c] = 1;
g[8][c] = 1;
}
break;
case 3:
g = [
[0, 0, 1, 1, 1, 1, 1, 0, 0],
[0, 1, 1, 1, 0, 1, 1, 1, 0],
[1, 1, 1, 0, 0, 0, 1, 1, 1],
[1, 1, 0, 0, 0, 0, 0, 1, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 1],
[1, 1, 0, 0, 0, 0, 0, 1, 1],
[1, 1, 1, 0, 0, 0, 1, 1, 1],
[0, 1, 1, 1, 0, 1, 1, 1, 0],
[0, 0, 1, 1, 1, 1, 1, 0, 0],
];
break;
}
for (r = 0; r < 9; ++r) {
for (c = 0; c < 9; ++c) {
if (g[r][c] == 1) {
this.#removeOne(false, removedDigits, r, c, rotation);
}
}
}
s = this.getSolution(this.#puzzle).length;
}
break;
}
remove = this.#levelStart[this.#level] + 1 - removedDigits.length;
while (remove > 0) {
// remove random blocks as needed
r = this.randRange(0, 8);
c = this.randRange(0, 8);
dig = this.#puzzle[r][c];
if (dig > 0) {
remove -= this.#removeOne(false, removedDigits, r, c, 0);
}
}
if (this.getSolution(this.#puzzle).length > 0) {
// can be solved so we are done
return;
}
}
console.log("after " + (this.#usedPattern ? "pat" : "non"));
// can't be solved without guessing so reset
this.#usedPattern = false;
this.#puzzle = this.#clone(this.#solution);
removedDigits = [0];
remove = this.#levelStart[this.#level];
// make sure one entire nonet (3x3 box) is empty
if (this.#level > 2 && this.randRange(0, 6) == 3) {
r = this.randRange(0, 2);
c = this.randRange(0, 2);
for (i = 0; i < 3; ++i) {
for (j = 0; j < 3; ++j) {
row = 3 * r + j;
col = 3 * c + i;
remove -= this.#removeOne(mirror, removedDigits, row, col);
}
}
}
// make sure one item is missing from each row
for (row = 0; row < 9 && this.#level < 3; ++row) {
col = this.randRange(0, 8);
remove -= this.#removeOne(mirror, removedDigits, row, col);
}
// make sure one item is missing from each column
for (col = 0; col < 9 && this.#level < 3; ++col) {
full = true;
for (row = 0; row < 9 && full; ++row) {
if (this.#puzzle[row][col] == 0) {
full = false;
}
}
if (full) {
row = this.randRange(0, 8);
remove -= this.#removeOne(mirror, removedDigits, row, col);
}
}
// make sure one item is missing from each nonet (box of 3x3)
for (r = 0; r < 3 && this.#level < 3; ++r) {
for (c = 0; c < 3; ++c) {
full = true;
for (i = 0; i < 3 && full; ++i) {
for (j = 0; j < 3 && full; ++j) {
row = 3 * r + i;
col = 3 * c + j;
if (this.#puzzle[row][col] == 0) {
full = false;
}
}
}
if (full) {
row = 3 * r + this.randRange(0, 2);
col = 3 * c + this.randRange(0, 2);
remove -= this.#removeOne(mirror, removedDigits, row, col);
}
}
}
// make sure one of each digit are missing
removedDigits = removedDigits.filter(function (value, index, self) {
return self.indexOf(value) === index;
});
while (removedDigits.length < 10) {
row = this.randRange(0, 8);
col = this.randRange(0, 8);
if (removedDigits.indexOf(this.#puzzle[row][col]) < 0) {
remove -= this.#removeOne(mirror, removedDigits, row, col);
}
}
// remove the rest randomly
while (remove > 0) {
if (window.performance.now() - start > 5000) {
// took more than 5 seconds so exit
// with a negative jitter to indicate
// the error.
this.#jitter = 0 - (1 + this.#jitter);
return;
}
row = this.randRange(0, 8);
col = this.randRange(0, 8);
dig = this.#puzzle[row][col];
if (dig > 0) {
this.#puzzle[row][col] = 0;
possible = this.#safeDigit(this.#puzzle, row, col, true);
if (possible.length == 1) {
// this cell can be removed
--remove;
fail = 0;
}
else if (!this.#canBeElsewhere(this.#puzzle, row, col, dig)) {
// this cell can be removed
--remove;
fail = 0;
}
else if (this.getSolution(this.#puzzle).length > 0) {
// this cell can be removed
--remove;
fail = 0;
}
else {
// this cell cannot be removed
++fail;
oldRow = row;
oldCol = col;
this.#puzzle[row][col] = dig;
if (fail > 5) {
found = false;
for (row = 0; !found && row < 9; ++row) {
for (col = 0; !found && col < 9; ++col) {
if (this.#puzzle[row][col] > 0) {
dig = this.#puzzle[row][col];
this.#puzzle[row][col] = 0;
if (this.getSolution(this.#puzzle).length > 0) {
// this cell can be removed
--remove;
fail = 0;
found = true;
}
else {
// put it back
this.#puzzle[row][col] = dig;
}
}
}
}
if (!found && this.#level >= 3) {
// clear the cell anyway on high levels
this.#puzzle[oldRow][oldCol] = 0;
--remove;
fail = 0;
}
}
}
}
}
}
// return a safe digit for the specified cell
// and -1 if no safe digits exist
#safeDigit(grid, row, col, returnAll = false) {
var digits = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
// copy the row
var used = this.#clone(grid[row]);
// copy the column
for (r = 0; r < 9; ++r) {
used.push(grid[r][col]);
}
// copy the nonet
var r = Math.floor(row / 3) * 3;
var c = Math.floor(col / 3) * 3;
for (var i = 0; i < 3; ++i) {
for (var j = 0; j < 3; ++j) {
used.push(grid[r + i][c + j]);
}
}
// zero any digits that have been used
for (var d = 0; d < used.length; ++d) {
digits[used[d]] = 0;
}
// copy the non-zero digits to a safe list
var safe = [];
for (c = 0; c < digits.length; ++c) {
if (digits[c] > 0) safe.push(digits[c]);
}
// if returning all, just return the array
if (returnAll) {
return safe;
}
// shuffle and return the first safe digit (if any)
this.#arrayShuffle(safe);
return safe.length > 0 ? safe[0] : -1;
}
randSeed(seed) {
this.#rand = seed % 23752890;
this.#randCount = 0;
}
randRange(low, high) {
if (low > high) {
var t = low;
low = high;
high = t;
}
++this.#randCount;
var rnd = this.#rand / 23752890;
var r = Math.floor(low + ((high - low + 1) * rnd));
this.#rand = (this.#rand * 938301 + 493297) % 23752890; // set the next random ticker
return r;
}
#arrayShuffle(array) {
var randomIndex;
var arrayMax = array.length - 1;
// While there remain elements to shuffle.
for (var currentIndex = 0; currentIndex <= arrayMax; ++currentIndex) {
// Pick a remaining element.
randomIndex = this.randRange(0, arrayMax);
// And swap it with the current element.
[array[currentIndex], array[randomIndex]] = [array[randomIndex], array[currentIndex]];
//
}
}
getSolution(origGrid, ret = "solution", depth = 0, bruitForce = false) {
// solve the puzzle and return an array of solution steps
var solution = [];
var newSolution = [];
var filled = 1;
var i;
var p;
var row;
var col;
var dig;
var grid = this.#clone(origGrid);
var openCell = this.getOpenCells(grid);
// fill all the easy ones first
while (filled > 0) {
filled = 0;
for (i = 0; i < openCell.length; ++i) {
row = openCell[i][0];
col = openCell[i][1];
for (p = 0; p < openCell[i][2].length; ++p) {
dig = openCell[i][2][p];
if (openCell[i][2].length == 1 || !this.#canBeElsewhere(grid, row, col, dig)) {
++filled;
grid[row][col] = dig;
solution.push({ 'row': row, 'col': col, 'digit': dig });
break;
}
}
}
openCell = this.getOpenCells(grid);
}
for (i = 0; filled == 0 && bruitForce && depth < 3 && i < openCell.length; ++i) {
// we still have open cells so now we need to
// try each option in every cell to see if
// one will complete the puzzle but we stop
// on the first one we fill to reduce the cost
row = openCell[i][0];
col = openCell[i][1];
for (p = 0; p < openCell[i][2].length; ++p) {
dig = openCell[i][2][p];
grid[row][col] = dig;
newSolution = this.getSolution(grid, "solution", depth + 1);
if (newSolution.length > 0) {
++filled;
solution = newSolution;
openCell = [];
break;
}
grid[row][col] = 0;
}
}
switch (ret) {
case "grid":
return grid;
case "open":
return openCell;
case "raw":
return solution;
default:
return openCell.length > 0 ? [] : solution;
}
}
#canBeElsewhere(grid, row, col, dig) {
// can the specified digit be used in any other location
// besides the specified row/column
var c;
var r;
var x;
var y;
var i;
var j;
var dig;
// check the row
for (c = 0; c < 9; ++c) {
if (c != col) {
if (grid[row][c] == dig) {
return true;
}
else if (grid[row][c] == 0 && this.#safeDigit(grid, row, c, true).includes(dig)) {
return true;
}
}
}
// check the column
for (r = 0; r < 9; ++r) {
if (r != row) {
if (grid[r][col] == dig) {
return true;
}
else if (grid[r][col] == 0 && this.#safeDigit(grid, r, col, true).includes(dig)) {
return true;
}
}
}
// check the nonet
x = Math.floor(row / 3) * 3;
y = Math.floor(col / 3) * 3;
for (i = 0; i < 3; ++i) {
for (j = 0; j < 3; ++j) {
r = x + i;
c = y + j;
if (r != row || c != col) {
if (grid[r][c] == dig) {
return true;
}
else if (grid[r][c] == 0 && this.#safeDigit(grid, r, c, true).includes(dig)) {
return true;
}
}
}
}
return false;
}
getOpenCells(grid) {
// find all the possible digits that can go into each
// of the open cells (if any)
var openCell = [];
var r;
var c;
var i;
var j;
var sorted;
var last;
for (r = 0; r < 9; ++r) {
for (c = 0; c < 9; ++c) {
if (grid[r][c] == 0) {
openCell.push([r, c, this.#safeDigit(grid, r, c, true)]);
}
}
}
// sort the list based on the number of possibilities
last = openCell.length - 1;
sorted = false;
while (!sorted) {
sorted = true;
for (i = 0; i < last; ++i) {
j = i + 1;
if (openCell[i][2].length > openCell[j][2].length) {
sorted = false;
[openCell[i], openCell[j]] = [openCell[j], openCell[i]];
}
}
--last; // we know the last one is sorted
}
return openCell;
}
// count the number of blank cells (zero) in the grid
countBlank(grid) {
blank = 0;
for (a = 0; a < 9; ++a) {
for (b = 0; b < 9; ++b) {
if (grid[a][b] == 0) {
++blank;
}
}
}
return blank;
}
dumpGrid(grid) {
var out = "";
var r;
var c;
for (r = 0; r < 9; ++r) {
out += (r == 3 || r == 6 ? "-------+-------+-------\n" : '') + ' ';
for (c = 0; c < 9; ++c) {
out += (c == 3 || c == 6 ? '| ' : '') + (grid[r][c] == 0 ? '-' : grid[r][c]) + ' ';
}
out += "\n";
}
return out;
}
// because javascript can't clone an object/array on its own
// we need to push the object/array to a string and pull it
// back. costly and rather stupid but js has no clone operation
#clone(obj) {
return JSON.parse(JSON.stringify(obj));
}
}
All content on this site is copyright ©2004-2023 and is not to be reproduced without prior permission.