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.