/* An Adobe Illustrator Sudoku Generator + Solver for use with Scriptographer Sudoku generating algorithm borrowed from: http://blog.fourthwoods.com/2011/02/05/sudoku-in-javascript/ by David J. Rager I've stripped the */ var version = '1.0', scriptName = 'Sudoku' + ' ' + version var values = { DIFF: 'Medium', GO_BUTTON: 'Generate Sudoku!' } var comps = { MONOVEKTOR:{ type: 'text', value: 'Sudoku Code by\nDavid J. Rager 2010\n\nGUI by MONOVEKTOR 2013\n\n ', fullSize: true }, DIFF:{ type: 'list', label: 'Difficulty', options: ['Easy', 'Medium', 'Hard', 'Expert'] }, GO_BUTTON:{ type: 'button', fullSize: true, onClick: function(){ var newPuzzle = new Sudoku() newPuzzle.level = comps.DIFF.selectedIndex newPuzzle._newGame() var hints = newPuzzle.matrix.toString().replace(/,/g, '') newPuzzle.solveGame() var solution = newPuzzle.matrix.toString().replace(/,/g, '') var cell = 30, cellSize = new Size(cell, cell), group = new Group(), hintGroup = new Group(), solutionGroup = new Group(), gameBoard = new Group() group.name = 'Sudoku: ' + comps.DIFF.value hintGroup.name = 'Hints' group.appendTop(hintGroup) solutionGroup.name = 'Solution' group.appendBottom(solutionGroup) solutionGroup.visible = false gameBoard.name = 'Cells' group.appendBottom(gameBoard) var path = new Path.Rectangle(new Point(0, 0), cellSize * 9) path.strokeWidth = cell / 7 path.strokeColor = '#000000' path.fillColor = null gameBoard.appendTop(path) for(var i = 0; i < 9; i++){ for(var j = 0; j < 9; j++){ var path = new Path.Rectangle(new Point(j, i) * cellSize, cellSize) path.strokeWidth = cell / 20 path.strokeColor = '#000000' path.fillColor = null gameBoard.appendTop(path) var bottomCenter = path.bounds.bottomCenter, hintNumber = new PointText(bottomCenter) hints.charAt(i * 9 + j) == '0' ? solutionGroup.appendBottom(hintNumber) : hintGroup.appendBottom(hintNumber) hintNumber.characterStyle.fontSize = cell hintNumber.content = solution.charAt(i * 9 + j) hintNumber.bounds.center = path.bounds.center if(i % 3 == 0 && j % 3 == 0){ var path = new Path.Rectangle(new Point(j, i) * cellSize, cellSize * 3) path.strokeWidth = cell / 9.9 path.strokeColor = '#000000' path.fillColor = null gameBoard.appendTop(path) } } } } } } var palette = new Palette(scriptName, comps, values) /* * Sudoku Generator * v0.2 * * Copyright (c) 2010, David J. Rager * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: * * * Redistributions of source code must retain the above copyright notice, * this list of conditions and the following disclaimer. * * Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * Neither the name of Fourth Woods Media nor the names of its * contributors may be used to endorse or promote products derived from * this software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * * This is a sudoku puzzle generator and solver. This program provides two * generation algorithms, a solver and methods to update and check the state of * the puzzle. This program does not provide any user interface controls. * * To create a new puzzle just instantiate the Sudoku object: * * var thePuzzle = new Sudoku(); * * The puzzle is represented as a 9x9 matrix of numbers 0-9. A cell value of zero * indicates a cell that has been masked from view for the user to discover. A * user interface should display all the non-zero values to the user and blank * cells for any cell containing a zero. * * The puzzle uses either a simple shuffle algorithm or the backtracking solver * (the default) to create the puzzle. * * To start a new game call: * * thePuzzle.newGame(); * * This class includes a solver that will solve the sudoku using a backtracking * algorithm. To solve the puzzle call the solve() method: * * thePuzzle.solve(); * * If there is more than one solution to the sudoku puzzle, the solver will show * only one of them at random. The solver does not know if there is more than one * solution. * * The enumSolutions() method is a modified version of the solver that will count * all possible solutions for * * Have fun. Send any comments, bugs, contribs to rageratwork@gmail.com */ // The Array class doesn't have a contains() method. We create one to make the // code cleaner and more readable. // Note, it seems that the decreasing while loop is the fastest way to iterate // over a collection in javascript: // http://blogs.sun.com/greimer/entry/best_way_to_code_a // // This method takes one parameter: // obj - the object to search for in the array. the object must be of the // same type as the objects stored in the array. Array.prototype.contains = function(obj) { var i = this.length; while (i--) { if (this[i] === obj) { return true; } } return false; } // This clear method resets the values in the array to zero. Array.prototype.clear = function() { var i = this.length; while (i--) { this[i] = 0; } } // The timeDiff object is used for debugging, calculating the execution time for // the board generation algorithm. It may in the future be used to measure the // time it takes for the user to solve the puzzle. var timeDiff = { // this method marks the beginning of an event. start:function (){ d = new Date(); time = d.getTime(); }, // this method returns the time elapsed in milliseconds since the // beginning of an event. end:function (){ d = new Date(); return (d.getTime()-time); } } // The Sudoku class stores the matrix array and implements the game logic. // Instantiation of this class will automatically generate a new puzzle. function Sudoku() { // 'private' methods... // stores the 9x9 game data. the puzzle data is stored with revealed // numbers as 1-9 and hidden numbers for the user to discover as zeros. this.matrix = new Array(81); // initial puzzle is all zeros. this.matrix.clear(); // stores the difficulty level of the puzzle 0 is easiest. this.level = 0; // this method initializes the sudoku puzzle beginning with a root // solution and randomly shuffling rows, columns and values. the result // of this method will be a completely solved sudoku board. the shuffle // is similar to that used by the sudoku puzzle at: // // http://www.dhtmlgoodies.com/scripts/game_sudoku/game_sudoku.html // // this method takes one parameter: // matrix - the 9x9 array to store the puzzle data. the array // contents will be overwritten by this method. this.shuffle = function(matrix) { // create the root sudoku solution. this produces the following // sudoku: // // 1 2 3 | 4 5 6 | 7 8 9 // 4 5 6 | 7 8 9 | 1 2 3 // 7 8 9 | 1 2 3 | 4 5 6 // --------------------- // 2 3 4 | 5 6 7 | 8 9 1 // 5 6 7 | 8 9 1 | 2 3 4 // 8 9 1 | 2 3 4 | 5 6 7 // --------------------- // 3 4 5 | 6 7 8 | 9 1 2 // 6 7 8 | 9 1 2 | 3 4 5 // 9 1 2 | 3 4 5 | 6 7 8 for (var i = 0; i < 9; i++) for (var j = 0; j < 9; j++) matrix[i * 9 + j] = (i*3 + Math.floor(i/3) + j) % 9 + 1; // randomly shuffle the numbers in the root sudoku. pick two // numbers n1 and n2 at random. scan the board and for each // occurence of n1, replace it with n2 and vice-versa. repeat // several times. we pick 42 to make Douglas Adams happy. for(var i = 0; i < 42; i++) { var n1 = Math.ceil(Math.random() * 9); var n2; do { n2 = Math.ceil(Math.random() * 9); } while(n1 == n2); for(var row = 0; row < 9; row++) { for(var col = 0; col < col; k++) { if(matrix[row * 9 + col] == n1) matrix[row * 9 + col] = n2; else if(matrix[row * 9 + col] == n2) matrix[row * 9 + col] = n1; } } } // randomly swap corresponding columns from each column of // subsquares // // | | | // | | | // V V V // . . . | . . . | . . . // . . . | . . . | . . . // . . . | . . . | . . . //---------------------- // . . . | . . . | . . . // . . . | . . . | . . . // . . . | . . . | . . . //---------------------- // . . . | . . . | . . . // . . . | . . . | . . . // . . . | . . . | . . . // // note that we cannot swap corresponding rows from each row of // subsquares. for (var c = 0; c < 42; c++) { var s1 = Math.floor(Math.random() * 3); var s2 = Math.floor(Math.random() * 3); for(var row = 0; row < 9; row++) { var tmp = this.matrix[row * 9 + (s1 * 3 + c % 3)]; this.matrix[row * 9 + (s1 * 3 + c % 3)] = this.matrix[row * 9 + (s2 * 3 + c % 3)]; this.matrix[row * 9 + (s2 * 3 + c % 3)] = tmp; } } // randomly swap columns within each column of subsquares // // | | | // | | | // V V V // . . . | . . . | . . . // . . . | . . . | . . . // . . . | . . . | . . . //---------------------- // . . . | . . . | . . . // . . . | . . . | . . . // . . . | . . . | . . . //---------------------- // . . . | . . . | . . . // . . . | . . . | . . . // . . . | . . . | . . . for (var s = 0; s < 42; s++) { var c1 = Math.floor(Math.random() * 3); var c2 = Math.floor(Math.random() * 3); for(var row = 0; row < 9; row++) { var tmp = this.matrix[row * 9 + (s % 3 * 3 + c1)]; this.matrix[row * 9 + (s % 3 * 3 + c1)] = this.matrix[row * 9 + (s % 3 * 3 + c2)]; this.matrix[row * 9 + (s % 3 * 3 + c2)] = tmp; } } // randomly swap rows within each row of subsquares // // . . . | . . . | . . . // . . . | . . . | . . . // . . . | . . . | . . . //---------------------- // . . . | . . . | . . . <--- // . . . | . . . | . . . <--- // . . . | . . . | . . . <--- //---------------------- // . . . | . . . | . . . // . . . | . . . | . . . // . . . | . . . | . . . for (var s = 0; s < 42; s++) { var r1 = Math.floor(Math.random() * 3); var r2 = Math.floor(Math.random() * 3); for(var col = 0; col < 9; col++) { var tmp = this.matrix[(s % 3 * 3 + r1) * 9 + col]; this.matrix[(s % 3 * 3 + r1) * 9 + col] = this.matrix[(s % 3 * 3 + r2) * 9 + col]; this.matrix[(s % 3 * 3 + r2) * 9 + col] = tmp; } } // we could also randomly swap rows and columns of subsquares // // | | | // | | | // /---\ /---\ /---\ // . . . | . . . | . . . \ // . . . | . . . | . . . | <--- // . . . | . . . | . . . / //---------------------- // . . . | . . . | . . . \ // . . . | . . . | . . . | <--- // . . . | . . . | . . . / //---------------------- // . . . | . . . | . . . \ // . . . | . . . | . . . | <--- // . . . | . . . | . . . / // // we could also rotate the board 90, 180 or 270 degrees and // mirror left to right and/or top to bottom. } // this method randomly masks values in a solved sudoku board. for the // easiest level it will hide 5 cells from each 3x3 subsquare. // // this method makes no attempt to ensure a unique solution and simply // (naively) just masks random values. usually there will be only one // solution however, there may be two or more. i've seen boards with as // many as 6 or 7 solutions using this function, though that is pretty // rare. // // this method takes two parameters: // matrix - the game array completely initialized with the game // data. // mask - an array to store the 9x9 mask data. the mask array will // contain the board that will be presented to the user. this.maskBoardEasy = function(matrix, mask) { var i, j, k; for(i = 0; i < 81; i++) mask[i] = matrix[i]; for (var i = 0; i < 3; i++) { for (var j = 0; j < 3; j++) { // for each 3x3 subsquare, pick 5 random cells // and mask them. for (var k = 0; k < 5; k++) { var c; do { c = Math.floor(Math.random() * 9); } while(mask[(i * 3 + Math.floor(c / 3)) * 9 + j * 3 + c % 3] == 0); mask[(i * 3 + Math.floor(c / 3)) * 9 + j * 3 + c % 3] = 0; } } } } // this method scans all three zones that contains the specified cell // and populates an array with values that have not already been used in // one of the zones. the order of the values in the array are randomized // so the solver may simply iterate linearly through the array to try // the values in a random order rather than sequentially. // // this method takes three parameters: // matrix - the array containing the current state of the puzzle. // cell - the cell for which to retrieve available values. // avail - the array to receive the available values. if this // parameter is null, this method simply counts the number // of available values without returning them. // // this method returns the length of the data in the available array. this.getAvailable = function(matrix, cell, avail) { var i, j, row, col, r, c; var arr = new Array(9); arr.clear(); row = Math.floor(cell / 9); col = cell % 9; // row for(i = 0; i < 9; i++) { j = row * 9 + i; if(matrix[j] > 0) arr[matrix[j] - 1] = 1; } // col for(i = 0; i < 9; i++) { j = i * 9 + col; if(matrix[j] > 0) { arr[matrix[j] - 1] = 1; } } // square r = row - row % 3; c = col - col % 3; for(i = r; i < r + 3; i++) for(j = c; j < c + 3; j++) if(matrix[i * 9 + j] > 0) arr[matrix[i * 9 + j] - 1] = 1; j = 0; if(avail != null) { for(i = 0; i < 9; i++) if(arr[i] == 0) avail[j++] = i + 1; } else { for(i = 0; i < 9; i++) if(arr[i] == 0) j++; return j; } if(j == 0) return 0; for(i = 0; i < 18; i++) { r = Math.floor(Math.random() * j); c = Math.floor(Math.random() * j); row = avail[r]; avail[r] = avail[c]; avail[c] = row; } return j; } // this method is used by the solver to find the next cell to be filled. // the cell is chosen by finding a cell with the least amount of // available values to try. // // this method takes one parameter: // matrix - the array containing the current state of the puzzle. // // this method returns the next cell, or -1 if there are no cells left // to choose. this.getCell = function(matrix) { var cell = -1, n = 10, i, j; var avail = new Array(9); avail.clear(); for(i = 0; i < 81; i++) { if(matrix[i] == 0) { j = this.getAvailable(matrix, i, null); if(j < n) { n = j; cell = i; } if (n == 1) break; } } return cell; } // this is the actual solver. it implements a backtracking algorithm in // which it randomly selects numbers to try in each cell. it starts // with the first cell and picks a random number. if the number works in // the cell, it recursively chooses the next cell and starts again. if // all the numbers for a cell have been tried and none work, a number // chosen for a previous cell cannot be part of the solution so we have // to back up to the last cell and choose another number. if all the // numbers for that cell have also been tried, we back up again. this // continues until a value is chosen for all 81 cells. // // this method takes one parameter: // matrix - the array containing the current state of the puzzle. // // this method returns 1 if a solution has been found or 0 if there was // not a solution. this.solve = function(matrix) { var i, j, ret = 0; var cell = this.getCell(matrix); // since this is the solver that is following the sudoku rules, // if getCell returns -1 we are guaranteed to have found a valid // solution. in this case we just return 1 (for 1 solution, see // enumSolutions for more information). if(cell == -1) return 1; var avail = new Array(9); avail.clear(); j = this.getAvailable(matrix, cell, avail); for(i = 0; i < j; i++) { matrix[cell] = avail[i]; // if we found a solution, return 1 to the caller. if(this.solve(matrix) == 1) return 1; // if we haven't found a solution yet, try the next // value in the available array. } // we've tried all the values in the available array without // finding a solution. reset the cell value back to zero and // return zero to the caller. matrix[cell] = 0; return 0; } // this method counts the number of possible solutions for a given // puzzle. this uses the same algorithm as the solver but tries all // the available values for all the cells incrementing a count every // time a new solution is found. this method is used by the mask // function to ensure there is only one solution to the puzzle. // // this method performs well for a puzzle with 20 or so hints. do not // try this function on a blank puzzle (zero hints). there is not enough // time remaining in the physical universe to enumerate all the possible // sudoku boards. when this method returns, the puzzle passed in is // restored to its original state. // // this method takes one parameter: // matrix - the array containing the current state of the puzzle. // // this method returns the number of solutions found or 0 if there was // not a solution. this.enumSolutions = function(matrix) { var i, j, ret = 0; var cell = this.getCell(matrix); // if getCell returns -1 the board is completely filled which // means we found a solution. return 1 for this solution. if(cell == -1) return 1; var avail = new Array(9); avail.clear(); j = this.getAvailable(matrix, cell, avail); for(i = 0; i < j; i++) { // we try each available value in the array and count // how many solutions are produced. matrix[cell] = avail[i]; ret += this.enumSolutions(matrix); // for the purposes of the mask function, if we found // more than one solution, we can quit searching now // so the mask algorithm can try a different value. if(ret > 1) break; } matrix[cell] = 0; return ret; } // this method generates a minimal sudoku puzzle. minimal means that no // remaining hints on the board may be removed and still generate a // unique solution. when this method returns the resulting puzzle will // contain about 20 to 25 hints that describe a puzzle with only one // solution. // // this method takes two parameters: // matrix - the game array completely initialized with the game // data. // mask - an array to store the 9x9 mask data. the mask array will // contain the board that will be presented to the user. this.maskBoard = function(matrix, mask) { var i, j, k, r, c, n = 0, a, hints = 0, cell, val; var avail = new Array(9); avail.clear(); var tried = new Array(81); tried.clear(); // start with a cleared out board mask.clear(); // randomly add values from the solved board to the masked // board, picking only cells that cannot be deduced by existing // values in the masked board. // // the following rules are used to determine the cells to // populate: // 1. based on the three zones to which the cell belongs, if // more than one value can go in the cell (i.e. the selected // cell value and at least one other value), check rule two. // 2. for each zone, if the selected value could go in another // free cell in the zone then the cell may be selected as a // hint. this rule must be satisfied by all three zones. // // both rules must pass for a cell to be selected. once all 81 // cells have been checked, the masked board will represent a // puzzle with a single solution. do { // choose a cell at random. do { cell = Math.floor(Math.random() * 81); } while((mask[cell] != 0) || (tried[cell] != 0)); val = matrix[cell]; // see how many values can go in the cell. i = this.getAvailable(mask, cell, null); if(i > 1) { // two or more values can go in the cell based // on values used in each zone. // // check each zone and make sure the selected // value can also be used in at least one other // cell in the zone. var cnt, row = Math.floor(cell / 9), col = cell % 9; cnt = 0; // count the cells in which the value // may be used. // look at each cell in the same row as the // selected cell. for(i = 0; i < 9; i++) { // don't bother looking at the selected // cell. we already know the value will // work. if(i == col) continue; j = row * 9 + i; // j stores the cell index // if the value is already filled, skip // to the next. if(mask[j] > 0) continue; // get the values that can be used in // the cell. a = this.getAvailable(mask, j, avail); // see if our value is in the available // value list. for(j = 0; j < a; j++) { if(avail[j] == val) { cnt++; break; } avail[j] = 0; } } // if the count is greater than zero, the // selected value could also be used in another // cell in that zone. we repeat the process with // the other two zones. if(cnt > 0) { // col cnt = 0; for(i = 0; i < 9; i++) { if(i == row) continue; j = i * 9 + col; if(mask[j] > 0) continue; a = this.getAvailable(mask, j, avail); for(j = 0; j < a; j++) { if(avail[j] == val) { cnt++; break; } avail[j] = 0; } } // if the count is greater than zero, // the selected value could also be used // in another cell in that zone. we // repeat the process with the last // zone. if(cnt > 0) { // square cnt = 0; r = row - row % 3; c = col - col % 3; for(i = r; i < r + 3; i++) { for(j = c; j < c + 3; j++) { if((i == row) && (j == col)) continue; k = i * 9 + j; if(mask[k] > 0) continue; a = this.getAvailable(mask, k, avail); for(k = 0; k < a; k++) { if(avail[k] == val) { cnt++; break; } avail[k] = 0; } } } if(cnt > 0) { mask[cell] = val; hints++; } } } } tried[cell] = 1; n++; } while(n < 81); // at this point we should have a masked board with about 40 to // 50 hints. randomly select hints and remove them. for each // removed hint, see if there is still a single solution. if so, // select another hint and repeat. if not, replace the hint and // try another. do { do { cell = Math.floor(Math.random() * 81); } while((mask[cell] == 0) || (tried[cell] == 0)); val = mask[cell]; var t = this; var solutions = 0; mask[cell] = 0; solutions = this.enumSolutions(mask); if(solutions > 1) mask[cell] = val; tried[cell] = 0; hints--; } while(hints > 0); // at this point we have a board with about 20 to 25 hints and a // single solution. } // this method checks whether a value will work in a given cell. it // checks each zone to ensure the value is not already used. // // this method takes three parameters: // row - the row of the cell // col - the column of the cell // val - the value to try in the cell // // this method returns true if the value can be used in the cell, false // otherwise. this._checkVal = function(matrix, row, col, val) { var i, j, r, c; // check each cell in the row to see if the value already // exists in the row. do not look at the value of the cell in // the column we are trying. repeat for each zone. for(i = 0; i < 9; i++) { if((i != col) && (matrix[row * 9 + i] == val)) return false; } // check col for(i = 0; i < 9; i++) { if((i != row) && (matrix[i * 9 + col] == val)) return false; } // check square r = row - row % 3; c = col - col % 3; for(i = r; i < r + 3; i++) for(j = c; j < c + 3; j++) if(((i != row) || (j != col)) && (matrix[i * 9 + j] == val)) return false; return true; } // 'public' methods // this method checks whether a value will work in a given cell. it // checks each zone to ensure the value is not already used. // // this method takes three parameters: // row - the row of the cell // col - the column of the cell // val - the value to try in the cell // // this method returns true if the value can be used in the cell, false // otherwise. this.checkVal = function(row, col, val) { return this._checkVal(this.matrix, row, col, val); } // this method sets the value for a particular cell. this is called by // the user interface when the user enters a value. // // this method takes three parameters: // row - the row of the cell // col - the column of the cell // val - the value to enter in the cell this.setVal = function(row, col, val) { this.matrix[row * 9 + col] = val; } // this method gets the value for a particular cell. this is called by // the user interface for displaying the contents of a cell. // // this method takes two parameters: // row - the row of the cell // col - the column of the cell // // this method returns the value of the cell at the specified location. this.getVal = function(row, col) { return this.matrix[row * 9 + col]; } // this method initializes a new game using the solver to generate the // board. this._newGame = function() { var i, hints = 0; var mask = new Array(81); // clear out the game matrix. this.matrix.clear(); // call the solver on a completely empty matrix. this will // generate random values for cells resulting in a solved board. this.solve(this.matrix); // generate hints for the solved board. if the level is easy, // use the easy mask function. if(this.level == 0) { this.maskBoardEasy(this.matrix, mask); } else { // the level is medium or greater. use the advanced mask // function to generate a minimal sudoku puzzle with a // single solution. this.maskBoard(this.matrix, mask); // if the level is medium, randomly add 4 extra hints. if(this.level == 1) { for(i = 0; i < 4; i++) { do { var cell = Math.floor(Math.random() * 81); } while(mask[cell] != 0); mask[cell] = this.matrix[cell]; } } } // save the solved matrix. this.save = this.matrix; // set the masked matrix as the puzzle. this.matrix = mask; timeDiff.start(); } this.done; this._doHints = function(matrix, mask, tried, hints) { // at this point we should have a masked board with about 40 to // 50 hints. randomly select hints and remove them. for each // removed hint, see if there is still a single solution. if so, // select another hint and repeat. if not, replace the hint and // try another. if(hints > 0) { do { cell = Math.floor(Math.random() * 81); } while((mask[cell] == 0) || (tried[cell] == 0)); val = mask[cell]; var t = this; var solutions = 0; mask[cell] = 0; solutions = this.enumSolutions(mask); //console.log("timeout"); if(solutions > 1) mask[cell] = val; tried[cell] = 0; hints--; var t = this; setTimeout(function(){t._doHints(matrix, mask, tried, hints);}, 50); } else { this.save = this.matrix; this.matrix = mask; // this.done(); } //console.log(hints); // at this point we have a board with about 20 to 25 hints and a // single solution. } this._doMask = function(matrix, mask) { var i, j, k, r, c, n = 0, a, hints = 0, cell, val; var avail = new Array(9); avail.clear(); var tried = new Array(81); tried.clear(); // start with a cleared out board mask.clear(); // randomly add values from the solved board to the masked // board, picking only cells that cannot be deduced by existing // values in the masked board. // // the following rules are used to determine the cells to // populate: // 1. based on the three zones to which the cell belongs, if // more than one value can go in the cell (i.e. the selected // cell value and at least one other value), check rule two. // 2. for each zone, if the selected value could go in another // free cell in the zone then the cell may be selected as a // hint. this rule must be satisfied by all three zones. // // both rules must pass for a cell to be selected. once all 81 // cells have been checked, the masked board will represent a // puzzle with a single solution. do { // choose a cell at random. do { cell = Math.floor(Math.random() * 81); } while((mask[cell] != 0) || (tried[cell] != 0)); val = matrix[cell]; // see how many values can go in the cell. i = this.getAvailable(mask, cell, null); if(i > 1) { // two or more values can go in the cell based // on values used in each zone. // // check each zone and make sure the selected // value can also be used in at least one other // cell in the zone. var cnt, row = Math.floor(cell / 9), col = cell % 9; cnt = 0; // count the cells in which the value // may be used. // look at each cell in the same row as the // selected cell. for(i = 0; i < 9; i++) { // don't bother looking at the selected // cell. we already know the value will // work. if(i == col) continue; j = row * 9 + i; // j stores the cell index // if the value is already filled, skip // to the next. if(mask[j] > 0) continue; // get the values that can be used in // the cell. a = this.getAvailable(mask, j, avail); // see if our value is in the available // value list. for(j = 0; j < a; j++) { if(avail[j] == val) { cnt++; break; } avail[j] = 0; } } // if the count is greater than zero, the // selected value could also be used in another // cell in that zone. we repeat the process with // the other two zones. if(cnt > 0) { // col cnt = 0; for(i = 0; i < 9; i++) { if(i == row) continue; j = i * 9 + col; if(mask[j] > 0) continue; a = this.getAvailable(mask, j, avail); for(j = 0; j < a; j++) { if(avail[j] == val) { cnt++; break; } avail[j] = 0; } } // if the count is greater than zero, // the selected value could also be used // in another cell in that zone. we // repeat the process with the last // zone. if(cnt > 0) { // square cnt = 0; r = row - row % 3; c = col - col % 3; for(i = r; i < r + 3; i++) { for(j = c; j < c + 3; j++) { if((i == row) && (j == col)) continue; k = i * 9 + j; if(mask[k] > 0) continue; a = this.getAvailable(mask, k, avail); for(k = 0; k < a; k++) { if(avail[k] == val) { cnt++; break; } avail[k] = 0; } } } if(cnt > 0) { mask[cell] = val; hints++; } } } } tried[cell] = 1; n++; } while(n < 81); var t = this; setTimeout(function(){t._doHints(matrix, mask, tried, hints);}, 50); } this.newGame = function() { var i, hints = 0; var mask = new Array(81); // clear out the game matrix. this.matrix.clear(); // call the solver on a completely empty matrix. this will // generate random values for cells resulting in a solved board. this.solve(this.matrix); // generate hints for the solved board. if the level is easy, // use the easy mask function. if(this.level == 0) { this.maskBoardEasy(this.matrix, mask); // save the solved matrix. this.save = this.matrix; // set the masked matrix as the puzzle. this.matrix = mask; timeDiff.start(); // this.done(); } else { // the level is medium or greater. use the advanced mask // function to generate a minimal sudoku puzzle with a // single solution. this._doMask(this.matrix, mask); // if the level is medium, randomly add 4 extra hints. if(this.level == 1) { for(i = 0; i < 4; i++) { do { var cell = Math.floor(Math.random() * 81); } while(mask[cell] != 0); mask[cell] = this.matrix[cell]; } } } } // this method solves the current game by restoring the solved matrix. // if the original unmodified masked matrix was saved, this function // could call the solve method which would undo any wrong player guesses // and actually solve the game. this.solveGame = function() { this.matrix = this.save; } // this method determines wether or not the game has been completed. it // looks at each cell and determines whether or not a value has been // entered. if not, the game is not done. if a value has been entered, // it calls checkVal() to make sure the value does not violate the // sudoku rules. if both checks are passed for each cell in the board // the game is complete. this.gameFinished = function() { for(var i = 0; i < 9; i++) { for(var j = 0; j < 9; j++) { var val = this.matrix[i * 9 + j]; if((val == 0) || (this._checkVal(this.matrix, i, j, val) == false)) return 0; } } return timeDiff.end(); } }