The Schworak Site | Log In | Up One Level

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;

	// 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; }


	// 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;

		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);

		if (this.randRange(0, 7) == 3) {
			// some special layouts exist
			switch (this.#level) {
				case 0:
					switch (this.randRange(0, 1)) {
						case 0:
							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]) {
												this.#removeOne(false, removedDigits, r, c, rotation);
											}
										}
									}
								}
							}
							break;
						case 1:
							for (i = 0; i < 3; ++i) {
								for (j = 0; j < 3; ++j) {
									r = i * 3;
									c = j * 3;
									this.#removeOne(false, removedDigits, r, c, rotation);
									this.#removeOne(false, removedDigits, r + 1, c, rotation);
									this.#removeOne(false, removedDigits, r, c + 1, rotation);
								}
							}
							break;
					}
					break;
				case 1:
					switch (this.randRange(0, 0)) {
						case 0:
							var odd = this.randRange(0, 1);
							for (i = 0; i < 3; ++i) {
								for (j = 0; j < 3; ++j) {
									odd = 1 - 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) {
												this.#removeOne(false, removedDigits, r, c, rotation);
											}
										}
									}
								}
							}
							break;
					}
					break;
				case 2:
					switch (this.randRange(0, 0)) {
						case 0:
							var x = this.randRange(8, 15);
							for (r = 0; r < 9; ++r) {
								for (c = 8 - r; c < 9; ++c) {
									if (r + c > x) {
										this.#removeOne(false, removedDigits, r, c, rotation);
									} else {
										this.#removeOne(false, removedDigits, r, c, (rotation + 2) % 4);
									}
								}
							}
							break;
					}
					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;
			}
		}

		// can't be solved without guessing so reset
		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-2022 and is not to be reproduced without prior permission.