// // sudoku_jpg.js // // Logic-only (no guessing) Sudoku helper // // Written by J.P. Grossman (jpg@alum.mit.edu) // // January 3, 2006 // //======================================================================================================= // // UI // //======================================================================================================= //////////////////////////////////////////////////////////////////////// // // UI global variables // //////////////////////////////////////////////////////////////////////// KEY_LEFT = 37; KEY_UP = 38; KEY_RIGHT = 39; KEY_DOWN = 40; KEY_DEL = 46; KEY_BACKSPACE = 8; KEY_TAB = 9; changed = true; changedByJavascript = false; examples = [ ["", "---- www.scanraid.com/sudoku.htm ----"], ["97.3.4.65.2.5.6.8............58.29....2.4.3....87.51............6.2.8.3.84.1.9.27", "Easiest"], [".985..2..1.......4.5.....3...26431.....9.8.....71526...7.....8.2.......7..6..152.", "Gentle"], ["3.2.7.5.4...........6254....9....6....89651....5....2....1978...........5.7.8.2.6", "Moderate"], ["..54.16......6.....94..7.2.37..2..4.....1.....1..4..56.5.8..26.....9......23.69..", "Tough"], ["..1..38...4.....6.7..9.65.16..5....2.........8....7..93.61.8..4.9.....8...87..2..", "Diabolical"], ["5.4.....1..64...7....6.8.......5..13.........83..2.......9.4....4...76..2.....8.9", "22 clues"], ["...............157.8.725.6...5.4.7..79.2.6.15..4.9.8...4.168.3.321...............", "Weird 1 (gentle)"], ["...............91.13.6.4.52.8.2.3.465.......861.5.7.3.89.4.5.67.52...............", "Weird 2 (tough)"], ["9..4.5..1.7.....3...4...9....35.41....7...4....89.15....9...6...8.....2.4..2.8..9", "Evil (with.x-wings)"], ["..17.48...8.....4.5...9..2...85.31..1...4...8..39.12...9..6...3.1.....5...61.97..", "Evil (with.SF)"], ["2581.4.3793682751447153.28.7152.3.4.84967532136241..751249..753593742168687351492", "Remote Pairs Test 1"], [".8....4955.18493.292435.8.1.3.5.16...15...7....94..51..9672415.1426.59.775....246", "Remote Pairs Test 2"], ["43..2..96..79.61.4...4.5....4.....12.........96.....4....1.7...5.83.47..17..9..63", "Triples Example"], ["5........4.1.7..569.84.5...21...3.98..52.96...498...25..26.45737.3.2..64..4...2.9", "Hidden Triple Example"], ["..7........45.92..5...43..19..1.8..3..1...6..3..7.5..86..98...4..83.75........8..", "Hidden Quad Example (but no quad)"], ["..54.781....1.27....1.56..21.7...4.84.2..1..98.6...2.16...1.....139.8.....47.31..", "Hidden Quad Example 2"], [".7.3.2.8...3...1..5..4.1..31.......5.3.2.5.1.2.......96..5.9..7..9...5...5.7.4.2.", "Box/Line Example"], [".51.7.9..928156347..398.5..297465..3536.1.479814739625..952.736.62.97.54..564.29.", "Y-wing (single)"], ["..931.7.48742593163..74.9.5946587231.3.16459...592346.493671852627895143...432679", "Y-wings (several)"], [".4398.25.6..425...2....1.949....4.7.3..6.8...41.2.9..382.5.........4...553489.71.", "X-wing Example"], [".1....8.35...961....4.81.6.9..4.3..6.2..6..1....8.5..7.6..3.4.1...17.6351.36...2.", "Sword-Fish Example"], ["1567.8.2.42961.78.378.4.6.1647...2.8213..7...8954263179.1.7...2534.6.8797.29.41..", "Double Guardian.Example"], ["1..8.2..482794..5...3...8..234798615...4.1283.18.2.479..6.8.9...82..9.4.3912.4.68", "Disruptive.Guardian.Example"], ["", ""], ["", "---- www.sudokusolver.co.uk ----"], [".4398.25.6..425...2....1.949....4.7.3..6.8...41.2.9..382.5.........4...553489.71.", "Cycle.rule.example"], ["2..3.....8.4.62..3.138...........39.5.7...6.1.32...........914.6..25.8.9.....1..2", "Illogical #7 (lots of chains)"], ["8.3.29..6..6.185.............5.4..8.7.9...6.2.6..9.1.............165.8..5..98.4.3", "Illogical #8"], ["34.....16..63..7..8..6.5...5...3.29.....2.....28.9...5...8.1..7..9..36..68.....23", "* Illogical #9"], ["..3.2..7.1.........6..5.4.353..4.....7.2.6.5.....3..489.2.7..1.........2.4..8.7..", "Illogical #10"], [".3.26.1...6.8..324.....1.....1.8..92.........49..2.5.....6.....859..2.6...7.53.8.", "Illogical #11 (long chain of pairs!)"], [".....1..43.2..78...1.....69..1.4...6...1.3...4...8.2..56.....3...93..6.52..9.....", "Illogical #12"], [".....8.319........31.9..6..4.1.6....6.84.97.2....2.1.6..5..1.87........989.7.....", "Illogical #13"], ["..19....86...85.3...7.6.1...34.9.......5.4.......1.42...5.7.9...1.84...77....92..", "Illogical #14"], ["8....5.62...42.......7...14.2.5.....14.3.7.85.....1.9.38...9.......53...45.6....8", "Illogical #15"], ["...41...96.....134..9....8....32...8.2.5.7.9.7...89....9....6..543.....28...35...", "Illogical #16"], [".61.8...7...4...8......791..57..21.....8.3.....47..59..392......1...4...7...3.25.", "Illogical #17 (long generalized chains!)"], ["2..5..61..4......7.5.9.8..41.9...78.....9.....34...1.23..6.2.7.4......3..72..3..8", "Illogical #18"], ["....1....7.....8....3.6.4..31..49.6...8.2.7...5.73..18..9.8.3....4.....2....5....", "Illogical #19"], ["2..1...6..4..5.8..9.7..3.....3.....18.......96.....2.....2..4.7..4.6..5..1...8..6", "Illogical #20"], ["8.......1.3.876.9..9.....6...31.82...6.....5...85.94...4.....8..8.953.4.9.......3", "Illogical #21"], ["5..12...7.3....24..1..76..3.....5..2..7...9..1..2.....6..91..3..45....1.9...54..6", "Illogical #24"], [".96....1..5.6..7....18.....5...94.68.6.....4.97.16...5.....13....5..2.7..1....59.", "Illogical #26"], ["", ""], ["", "---- www.research.att.com/~gsf/sudoku ----"], ["1.34..78.4...8.1.3789123456.143..8...75.18234.38.4.61.3.18.456.54..319.88.7..5341", "puzzle x-1"], ["...4.768.456.8927.78..6.....476915.8.98...7.66..7.8.9..6.9738..8.45169.797.824.6.", "puzzle x-2"], ["123..67.9456..923.789..2.6..1...7.9..679...1.93..1..7.341..59..578.9...66928..3..", "puzzle y-1"], ["4..21..6.....7..82.52.6....5.16.97.467...2.953...578.6....4.253.3..2.94824..93671", "puzzle y-2"], [".2.45..8..5.....23.8912.564215894376..82...5.9...15842..25.169859....217861972435", "puzzle w-1"], ["1....6..9....89.3...9..25...7....49.6..89.2..9.1.....3.9..4.....1..689748.497.3..", "* puzzle m-2"], [".23.567.....7.....7.9.3...4..8...3..6....2.....48....1.....78..5.19....78...456..", "puzzle m-54"], [".2....6.....1.....7...3..5...8.4.9.33.......8....2.4.663.5.......5..9..2.1..84...", "* puzzle m-2-2"], [".....67...5..89....891.....2....7...3.....574...9..23....2...9.84....6.......1.42", "1-constrained#1"], ["..34....94......2378..2..6.21..6..9...8..1.46......5....58......4..9....97.5.....", "* 1-constrained#2"], ["......6894..1..7...8...2...2..5..3...1...8.........251..1.9..36..4.1..72.32.76...", "* 1-constrained#3"], ["12.4....9..6.8.1..78...3.....4..7..........649.8...5..59.63.........53.2....94...", "1-constrained#5"], [".....67...5..89....891.....2....7...3....2574...9..2....12...9.84............1.42", "1-constrained#6 (lots of generalized chains!)"], [".2....6.....1.....7...3..5...8.4.9.33.......8....2.4.663.5.......5..9..2.1..84...", "* 2-constrained#1"], ["", ""], ["", "---- www.sudoku.com/forums ----"], [" 52 68 7 2 6 48 9 2 41 1 8 61 38 9 63 6 1 9", "* An Interesting Puzzle"], ["7 4 2 7 8 3 8 9 5 3 6 2 9 1 7 6 3 9 3 4 6 9 1 5", "* #77 Carcul"], [" 5 16 3 6 2 93 2 4 453 182 8 4 8 512 4 6 1 53 6 9 1 721 46", "* Diabolical"], ["", ""], ["", "---- Minimal Sudokus ----"], [".......1.4.........2...........5.4.7..8...3....1.9....3..4..2...5.1........8.6...", "17 clues #1"], ["..69...7.....1...28.........2......4........1..5..6..........6......2.5..1..43...", "17 clues #2"], [".98..........7........15...1...........2....9...9.6.82.......3.5.1.........4...2.", "17 clues #3"], ["4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......", "17 clues #4"], ["", ""], ["", "* indicates a puzzle that S.H. can't solve"] ]; pos = new Array(81); // Last position entered/selected by the user rowname = ["9", "8", "7", "6", "5", "4", "3", "2", "1"]; colname = ["a", "d", "g", "b", "e", "h", "c", "f", "i"]; colmap = [0, 3, 6, 1, 4, 7, 2, 5, 8]; blockname = [ ["upper left", "upper middle", "upper right"], ["middle left", "center", "middle right"], ["lower left", "lower middle", "lower right"] ]; highlight_grey = '#d8d8d8'; highlight_red = '#ff8080'; highlights = false; doitforme = 0; list = ""; // Used to build strings of the form "a, b, c" trace = true; //////////////////////////////////////////////////////////////////////// // // Trace() // //////////////////////////////////////////////////////////////////////// function Trace (msg) { if (trace) trace &= confirm(msg); } //////////////////////////////////////////////////////////////////////// // // AppendList() // //////////////////////////////////////////////////////////////////////// function AppendList (str) { if (list != "") list += ", "; list += str; } //////////////////////////////////////////////////////////////////////// // // GetList() // //////////////////////////////////////////////////////////////////////// function GetList () { str = list; list = ""; return str; } //////////////////////////////////////////////////////////////////////// // // WriteExamples() // //////////////////////////////////////////////////////////////////////// function WriteExamples () { var i; for (i = 0 ; i < examples.length ; i++) document.writeln(""); } //////////////////////////////////////////////////////////////////////// // // WriteBoard() // // printing: 0 - not printing // 1 - printing board only // 2 - printing state // //////////////////////////////////////////////////////////////////////// function WriteBoard (doc, printing) { var i, j, k, l, m, value; changedByJavascript = true; doc.writeln(""); doc.writeln(""); doc.writeln(""); doc.writeln(""); doc.writeln("
"); for (i = 0 ; i < 9 ; i++) doc.writeln(""); doc.writeln("
" + rowname[i] + "
"); for (i = 0 ; i < 3 ; i++) { doc.writeln(""); for (j = 0 ; j < 3 ; j++) { doc.writeln(""); } doc.writeln(""); } doc.writeln("
"); for (k = 0 ; k < 3 ; k++) { doc.writeln(""); for (l = 0 ; l < 3 ; l++) { var index = (27*i + 9*k + 3*l + j); if (printing) { value = document.sudoku["s" + index].value; if (value == "") { if (printing == 2) { doc.writeln(""); } doc.writeln(""); } doc.writeln("
"); for (m = 0 ; m < 9 ; m++) { if (xpos[index] & (1 << m)) doc.write((m+1) + " "); } } else doc.writeln(" "); } else doc.writeln("" + value); } else { doc.writeln(""); doc.write(""); } doc.writeln("
 
 "); for (i = 0 ; i < 9 ; i++) doc.writeln(""); doc.writeln("
" + colname[colmap[i]] + "
 
"); // Set the focus to the first square if (!printing) document.sudoku["s0"].focus(); } //////////////////////////////////////////////////////////////////////// // // EnterDigit() // //////////////////////////////////////////////////////////////////////// function EnterDigit (index, value) { if (value.length) { if (value.charCodeAt(0) < 49 || value.charCodeAt(0) > 57) value = document.sudoku["s" + index].value = ""; } if (value != pos[index]) { if (highlights) ClearHighlights(); var k; if (changedByJavascript) { for (k = 0 ; k < 81 ; k++) pos[k] = document.sudoku["s" + k].value; changedByJavascript = false; } else pos[index] = document.sudoku["s" + index].value; if (value != "") { for (k = 0 ; k < 20 ; k++) { if (pos[index] == pos[influence[index][k]]) { SetHighlight(index, highlight_red); SetHighlight(influence[index][k], highlight_red); GiveHint(SquareName(index) + " and " + SquareName(influence[index][k]) + " cannot both be " + value); break; } } } } row = Math.floor(index/9); col = index%9; col = (col%3)*3 + Math.floor(col/3); if (event.keyCode == KEY_LEFT) { col--; if (col == -1) { col = 8; row--; } } else if (event.keyCode == KEY_UP) { row--; } else if (event.keyCode == KEY_DOWN) { row++; } else if (event.keyCode != KEY_DEL && event.keyCode != KEY_BACKSPACE && event.keyCode != KEY_TAB) { col++; if (col == 9) { col = 0; row++; } } if (row >= 0 && row <= 8 && col >= 0 && col <= 8) { index = 9*row + (col%3)*3 + Math.floor(col/3); document.sudoku["s" + index].select(); } } //////////////////////////////////////////////////////////////////////// // // LoadPuzzle() // //////////////////////////////////////////////////////////////////////// function LoadPuzzle (k) { if (examples[k][0] != "") { var i; for (i = 0 ; i < 81 ; i++) { var row = Math.floor(i/9); var col = i%9; var index = 9*row + 3*(col%3) + Math.floor(col/3); pos[index] = examples[k][0].charAt(i); if ((pos[index] == " ") || (pos[index] == "0") || (pos[index] == ".")) pos[index] = ""; document.sudoku["s" + index].value = pos[index]; } changed = 1; changedByJavascript = 1; ResetHints(); } } //////////////////////////////////////////////////////////////////////// // // SetHighlight() // //////////////////////////////////////////////////////////////////////// function SetHighlight (index, colour) { document.sudoku["s" + index].style.background = colour; document.getElementById("t" + index).style.background = colour; highlights = true; } //////////////////////////////////////////////////////////////////////// // // ClearHighlights() // //////////////////////////////////////////////////////////////////////// function ClearHighlights () { for (k = 0 ; k < 81 ; k++) SetHighlight(k, '#ffffff'); highlights = false; } //////////////////////////////////////////////////////////////////////// // // SquareName() // //////////////////////////////////////////////////////////////////////// function SquareName (index) { return colname[index%9] + rowname[Math.floor(index/9)]; } //////////////////////////////////////////////////////////////////////// // // GiveHint() // //////////////////////////////////////////////////////////////////////// function GiveHint (hint) { document.getElementById("hint").innerHTML = "" + hint + ""; if (doitforme) document.sudoku["doitforme"].focus(); doitforme = false; stuck = false; } //////////////////////////////////////////////////////////////////////// // // DoItForMe() // //////////////////////////////////////////////////////////////////////// function DoItForMe (n, index) { doitforme = 1; return "

"; } //////////////////////////////////////////////////////////////////////// // // DoHintMove() // //////////////////////////////////////////////////////////////////////// function DoHintMove (n, index) { DoMove(n, index); document.getElementById("hint").innerHTML = ""; ClearHighlights(); document.sudoku["hintButton"].focus(); } //======================================================================================================= // // SUDOKU ENGINE // //======================================================================================================= //////////////////////////////////////////////////////////////////////// // // Global variables // //////////////////////////////////////////////////////////////////////// xpos = new Array(81); // Bitmask of possible digits in location k influence = new Array(81); // influence[k] = list of 20 squares in the same row/column/block as k markPresent = new Array(9); // used to mark squares for graph algorithms markAbsent = new Array(9); // used to mark squares for graph algorithms markCounter = 0; // Square k is marked when mark[k] == markCounter longerChainExists = false; debugInfluence = 0; commonInfluence = new Array(20); // Used to compute common influence of two squares commonSize = 0; // The xpos array encodes the sudoko board in the following order: // // 0 3 6 1 4 7 2 5 8 // // 9 12 15 10 13 16 11 14 17 // // ... // // Use the notation {a,b} for the arithmetic sequence // {a, a+b, ..., a+8b}. Then row k is {0,k}, column k // is {k,9}, and block (i,j) is {27j+i,3}. // buckets = new Array(9); // buckets[3*j + i] = Bitmask of possible bucket optimizations in block (i,j) stuck = false; numSquares = 0; weight = new Array(512); // number of 1's in binary representations of 0-511 hintOnly = false; // Globals used for chain searches firstIndex = 0; searchDigit = 0; searchType = 0; // Inference rule caches influenceCache = new Array(9 * 81 * 20); lockedPairCache = new Array(9 * 81 * 3); //////////////////////////////////////////////////////////////////////// // // Initialization // //////////////////////////////////////////////////////////////////////// function Initialize () { var i, j, k; // Initialize weight table for (i = 0 ; i < 512 ; i++) { weight[i] = 0; for (j = 256 ; j ; j >>= 1) { if (i & j) weight[i]++; } } // Initialize the influence table for (k = 0 ; k < 81 ; k++) { influence[k] = new Array(20); var row = Math.floor(k/9); var col = k%9; var blockx = col%3; var blocky = Math.floor(row/3); j = 0; // Add block var base = blocky * 27 + blockx; for (i = 0 ; i < 9 ; i++) { if (base + 3*i != k) influence[k][j++] = base + 3*i; } // Add row base = row * 9; for (i = 0 ; i < 9 ; i++) { if ((i%3) != blockx) influence[k][j++] = base + i; } // Add column base = col; for (i = 0 ; i < 9 ; i++) { if (Math.floor(i/3) != blocky) influence[k][j++] = base + 9*i; } influence[k].sort(function(a,b) { return a-b; }); } // Initialize the marks for (i = 0 ; i < 9 ; i++) { markPresent[i] = new Array(81); markAbsent[i] = new Array(81); for (k = 0 ; k < 81 ; k++) { markPresent[i][k] = 0; markAbsent[i][k] = 0; } } } Initialize(); //////////////////////////////////////////////////////////////////////// // // GetPos() // //////////////////////////////////////////////////////////////////////// function GetPos () { var i; var n; // Initialize globals for (i = 0 ; i < 81 ; i++) xpos[i] = 0x1ff; for (i = 0 ; i < 9 ; i++) { buckets[i] = 0x1ff; } numSquares = 0; // Import the current position for (i = 0 ; i < 81 ; i++) { value = document.sudoku["s" + i].value; if (value.length) { n = value.charCodeAt(0) - 49; if (n >= 0 && n <= 8) SetSquare(n, i); } } changed = false; } //////////////////////////////////////////////////////////////////////// // // SetSquare() // // Set square[index] with digit (n+1) // //////////////////////////////////////////////////////////////////////// function SetSquare (n, index) { var bit = 1 << n; var irow = 9 * Math.floor(index / 9); var icol = index % 9; var iblock = 27 * Math.floor(index / 27) + (index % 3); var k; document.sudoku["s" + index].value = (n+1); xpos[index] = 0; changedByJavascript = true; for (k = 0 ; k < 9 ; k++) { xpos[irow + k] &= ~bit; xpos[icol + 9*k] &= ~bit; xpos[iblock + 3*k] &= ~bit; } buckets[(icol%3) + 3 * Math.floor(irow/3)] &= ~bit; numSquares++; } //////////////////////////////////////////////////////////////////////// // // DoMove() // // Move digit (n+1) at index // //////////////////////////////////////////////////////////////////////// function DoMove (n, index) { SetSquare(n, index); stuck = false; } //////////////////////////////////////////////////////////////////////// // // GetContext() // //////////////////////////////////////////////////////////////////////// function GetContext (index, stride) { var k; ClearHighlights(); hindex = index; hstride = stride; for (k = 0 ; k < 9 ; k++) SetHighlight(index + k*stride, highlight_grey); if (stride == 1) return "In row " + rowname[Math.floor(index/9)]; else if (stride == 9) return "In column " + colname[index%9]; else return "In the " + blockname[Math.floor(index/27)][index%3] + " block"; } //////////////////////////////////////////////////////////////////////// // // DoHorzBucket() // // The digit (n+1) is in the kth horizontal bucket in block (i,j) // //////////////////////////////////////////////////////////////////////// function DoHorzBucket (n, i, j, k, isBlock) { var bit = 1 << n; var irow = 9 * (3 * j + k); var iblock = 27*j + i; var l; buckets[3*j + i] &= ~bit; // Cleanup for (l = 0 ; l < 9 ; l++, irow++, iblock += 3) { // row if (((l%3) != i) && (xpos[irow] & bit)) { stuck = false; xpos[irow] -= bit; } // block if ((Math.floor(l/3) != k) && (xpos[iblock] & bit)) { stuck = false; xpos[iblock] -= bit; } } if (!stuck && hintOnly) { var index = 27*j + i + 9*k; var hint; if (isBlock) hint = GetContext(27*j + i, 3); else hint = GetContext(27*j + 9*k, 1); hint += ", one of "; for (l = 0 ; l < 9 ; l += 3) { if (xpos[index + l] & bit) { AppendList(SquareName(index + l)); SetHighlight(index + l, highlight_red); } } GiveHint(hint + GetList() + " must be " + (n+1)); } } //////////////////////////////////////////////////////////////////////// // // DoVertBucket() // // The digit (n+1) is in the kth vertical bucket in block (i,j) // //////////////////////////////////////////////////////////////////////// function DoVertBucket (n, i, j, k, isBlock) { var bit = 1 << n; var icol = i + 3*k; var iblock = 27*j + i; var l; buckets[3*j + i] &= ~bit; // Cleanup for (l = 0 ; l < 9 ; l++, icol += 9, iblock += 3) { // col if ((Math.floor(l/3) != j) && (xpos[icol] & bit)) { stuck = false; xpos[icol] -= bit; } // block if (((l%3) != k) && (xpos[iblock] & bit)) { stuck = false; xpos[iblock] -= bit; } } if (!stuck && hintOnly) { var index = 27*j + i + 3*k; var hint; if (isBlock) hint = GetContext(27*j + i, 3); else hint = GetContext(i + 3*k, 9); hint += ", one of "; for (l = 18 ; l >= 0 ; l -= 9) { if (xpos[index + l] & bit) { AppendList(SquareName(index + l)); SetHighlight(index + l, highlight_red); } } GiveHint(hint + GetList() + " must be " + (n+1)); } } //////////////////////////////////////////////////////////////////////// // // Index() // //////////////////////////////////////////////////////////////////////// function Index (bit) { var index = 0; for ( ; !(bit & 1) ; bit >>= 1, index++); return index; } //////////////////////////////////////////////////////////////////////// // // CheckSingletonDigit() // //////////////////////////////////////////////////////////////////////// function CheckSingletonDigit (index, stride) { var one = 0; var two = 0; var i, j; for (i = 0, j = index ; i < 9 ; i++, j += stride) { two |= (one & xpos[j]); one |= xpos[j]; } one &= ~two; while (one && stuck) { var bit = one & -one; one -= bit; for (i = 0 ; i < 9 ; i++) { square = index + i * stride; if (xpos[square] & bit) { if (hintOnly) { GiveHint(GetContext(index, stride) + ", " + SquareName(square) + " must be " + (Index(bit)+1) + DoItForMe(Index(bit), square)); SetHighlight(square, highlight_red); } else DoMove(Index(bit), square); break; } } } } //////////////////////////////////////////////////////////////////////// // // DoPigeonhole() // //////////////////////////////////////////////////////////////////////// function DoPigeonhole (k, x, index, stride, transposed) { var j; // Look for a set of k bitmasks with the same k bits set (or a subset) var i = [0, 1, 2, 3, 4, 5, 6, 7]; while (stuck) { // OR together the current set of bitmasks var bits = 0; for (j = 0 ; j < k ; j++) { if (!x[i[j]]) break; bits |= x[i[j]]; } // If we found a pigeonhole set then see if it simplifies anything if ((j == k) && (weight[bits] == k)) { for (j = 0 ; j < 9 ; j++) { if ((x[j] & bits) && (x[j] & ~bits)) { if (stuck && hintOnly) { var hint = transposed ? ("Found " + k + " digits that can only be in " + k + " squares.
") : ("Found " + k + " squares that can only contain " + k + " digits.
") hint += GetContext(index, stride) + ", the squares "; for (l = 0 ; l < 9 ; l++) { if ((transposed && (bits & (1 << l))) || (!transposed && x[l] && ((x[l] & bits) == x[l]))) { AppendList(SquareName(index + l*stride)); SetHighlight(index + l*stride, highlight_red); } } hint += GetList() + "
must contain the digits "; for (l = 0 ; l < 9 ; l++) { if ((!transposed && (bits & (1 << l))) || (transposed && x[l] && ((x[l] & bits) == x[l]))) AppendList(l+1); } GiveHint(hint + GetList() + "."); } x[j] &= ~bits; stuck = false; } } } // Advance to the next set of indices for (j = 0 ; (j < k) && (i[k-j-1] == 8-j) ; j++); if (j == k) break; i[k-j-1]++; for (j = k-j ; j < k ; j++) i[j] = i[j-1] + 1; } } //////////////////////////////////////////////////////////////////////// // // Transpose() // //////////////////////////////////////////////////////////////////////// function Transpose (x, y) { var i, j; for (i = 0 ; i < 9 ; i++) { var bit = 1 << i; y[i] = 0; for (j = 0 ; j < 9 ; j++) { if (x[j] & bit) y[i] |= 1 << j; } } } //////////////////////////////////////////////////////////////////////// // // CheckPigeonhole() // //////////////////////////////////////////////////////////////////////// function CheckPigeonhole (k, index, stride) { var i, j; var x = new Array(9); var y = new Array(9); // Move the square bitmasks into x for (i = 0, j = index ; i < 9 ; i++, j += stride) x[i] = xpos[j]; // Look for a set of k squares with the same k possible digits DoPigeonhole(k, x, index, stride, 0); // Transpose the bitmasks Transpose(x, y); // Look for a set of k digits with the same k possible squares DoPigeonhole(k, y, index, stride, 1); // Transpose back Transpose(y, x); // Restore the xpos bitmasks for (i = 0, j = index ; i < 9 ; i++, j += stride) xpos[j] = x[i]; } //////////////////////////////////////////////////////////////////////// // // ComputeCommonInfluence() // //////////////////////////////////////////////////////////////////////// function ComputeCommonInfluence (i1, i2) { commonSize = 0; var j1 = 0; var j2 = 0; while ((j1 < 20) && (j2 < 20)) { if (influence[i1][j1] == influence[i2][j2]) { commonInfluence[commonSize++] = influence[i1][j1]; j1++; j2++; } else if (influence[i1][j1] < influence[i2][j2]) j1++; else j2++; } } //////////////////////////////////////////////////////////////////////// // // SimplifyChain() // // Either the first or last square in the chain must be the given digit. // // searchType - 0 = digit (digit is always the same) // 1 = pairs (this should always be called for a square of weight 2) // 2 = generalized (most aggressive) // //////////////////////////////////////////////////////////////////////// function SimplifyChain (chain, digit) { var i; var index = chain[0]; ComputeCommonInfluence(index, firstIndex); var bit = 1 << digit; for (i = 0 ; i < commonSize ; i++) { if (xpos[commonInfluence[i]] & bit) { if (hintOnly && stuck) { var hint = "In chain "; var c = index; var c1 = chain[1]; while (c1 != firstIndex) { c = [c1[0], c]; c1 = c1[1]; } SetHighlight(firstIndex, highlight_red); AppendList(SquareName(firstIndex)); while (c != index) { SetHighlight(c[0], highlight_grey); AppendList(SquareName(c[0])); c = c[1]; } SetHighlight(index, highlight_red); AppendList(SquareName(index)); var context; if (searchType == 0) context = "In chain of " + (digit+1) + "'s ("; else if (searchType == 1) context = "In chain of pairs ("; else context = "In generalized chain ("; GiveHint(context + GetList() + "),
one of " + SquareName(index) + ", " + SquareName(firstIndex) + " must be " + (digit+1)); } xpos[commonInfluence[i]] -= bit; stuck = false; } } } //////////////////////////////////////////////////////////////////////// // // SearchForDigitPresent() // //////////////////////////////////////////////////////////////////////// function SearchForDigitPresent (len, maxlen, chain, digit, base, stride) { if (!stuck || ((len == maxlen) && longerChainExists)) return; var index = -1; var i; var bit = 1 << digit; for (i = 0 ; i < 9 ; i++) { var index2 = base + i*stride; if ((xpos[index2] & bit) && (index2 != chain[0])) { if (index != -1) return; index = index2; } } if ((index != -1) && (markPresent[digit][index] != markCounter)) { if (len < maxlen) SearchChainDigitPresent(len+1, maxlen, [index, chain], digit); else longerChainExists = true; } } //////////////////////////////////////////////////////////////////////// // // SearchChainDigitAbsent() // // Continue a chain search by assuming that 'digit' is absent at // the current location. // // len - length of current chain // maxlen - maximum chain length // chain - [currIndex, rest of chain] // digit - digit assumed to be absent at currIndex // firstIndex - first index in chain // searchDigit - digit that we're looking for to be present // (we started the chain by assuming it's not present at firstIndex) // searchType - 0 = digit (digit is always the same) // 1 = pairs (this should always be called for a square of weight 2) // 2 = generalized (most aggressive) // //////////////////////////////////////////////////////////////////////// function SearchChainDigitAbsent (len, maxlen, chain, digit) { //Trace((digit+1) + " absent in " + chain); var i; var index = chain[0]; markAbsent[digit][index] = markCounter; // See if there's only two possible places for the digit in the same row, column or block if (searchType != 1) { var cacheIndex = 3 * (81 * digit + index); for (i = 0 ; stuck && (i < 3) ; i++) { var index2 = lockedPairCache[cacheIndex++]; if (index2 == -1) break; if (markPresent[digit][index2] != markCounter) { if (len < maxlen) SearchChainDigitPresent(len+1, maxlen, [index2, chain], digit); else longerChainExists = true; } } } // If this is a pair then the other digit must be present if ((searchType != 0) && (weight[xpos[index]] == 2) && (markPresent[digit][index] != markCounter)) SearchChainDigitPresent(len, maxlen, chain, Index(xpos[index] - (1 << digit))); } //////////////////////////////////////////////////////////////////////// // // SearchChainDigitPresent() // // Continue a chain search by assuming that 'digit' is present at // the current location. // // len - length of current chain // maxlen - maximum chain length // chain - [currIndex, rest of chain] // digit - digit assumed to be present at currIndex // firstIndex - first index in chain // searchDigit - digit that we're looking for to be present // (we started the chain by assuming it's not present at firstIndex) // searchType - 0 = digit (digit is always the same) // 1 = pairs // 2 = generalized (most aggressive) // //////////////////////////////////////////////////////////////////////// function SearchChainDigitPresent (len, maxlen, chain, digit) { //Trace((digit+1) + " present in " + chain); var i; var index = chain[0]; markPresent[digit][index] = markCounter; if ((digit == searchDigit) && (index != firstIndex)) SimplifyChain(chain, digit, firstIndex, searchType); if ((len == maxlen) && longerChainExists) return; var cacheIndex = 20 * (81 * digit + index); for (i = 0 ; stuck && (i < 20) ; i++) { var index2 = influenceCache[cacheIndex++]; if (index2 == -1) break; if ((markAbsent[digit][index2] != markCounter) && ((searchType != 1) || (weight[xpos[index2]] == 2))) { if (len < maxlen) SearchChainDigitAbsent(len+1, maxlen, [index2, chain], digit); else longerChainExists = true; } } // All other digits are absent from this square if (searchType == 2) { for (i = 0 ; i < 9 ; i++) { if ((xpos[index] & (1 << i)) && (i != digit) && (markAbsent[i][index] != markCounter)) SearchChainDigitAbsent(len, maxlen, chain, i); } } } //////////////////////////////////////////////////////////////////////// // // SearchChain() // //////////////////////////////////////////////////////////////////////// function SearchChain (maxlen, _firstIndex, _searchDigit, _searchType) { firstIndex = _firstIndex; searchDigit = _searchDigit; searchType = _searchType; markCounter++; //Trace("Searching for " + (_searchDigit+1) + ", searchType = " + _searchType); SearchChainDigitAbsent(1, maxlen, [firstIndex], searchDigit); } //////////////////////////////////////////////////////////////////////// // // FindLockedPair() // //////////////////////////////////////////////////////////////////////// function FindLockedPair (currIndex, digit, base, stride) { var index = -1; var i; var bit = 1 << digit; for (i = 0 ; i < 9 ; i++) { var index2 = base + i*stride; if ((xpos[index2] & bit) && (index2 != currIndex)) { if (index != -1) return -1; index = index2; } } return index; } //////////////////////////////////////////////////////////////////////// // // ComputeCaches() // //////////////////////////////////////////////////////////////////////// function ComputeCaches () { var i, j, k, l, index, bit; for (k = 0 ; k < 9 ; k++) { bit = 1 << k; for (i = 0 ; i < 81 ; i++) { if (xpos[i]) { // influence cache index = 20 * (81 * k + i); l = 0; for (j = 0 ; j < 20 ; j++) { if (xpos[influence[i][j]] & bit) influenceCache[index + l++] = influence[i][j]; } if (l < 20) influenceCache[index + l] = -1; // locked pair cache var row = Math.floor(i / 9); var col = i % 9; index = 3 * (81 * k + i); lockedPairCache[index] = FindLockedPair(i, k, row * 9, 1); lockedPairCache[index + 1] = FindLockedPair(i, k, col, 9); lockedPairCache[index + 2] = FindLockedPair(i, k, 27 * Math.floor(row / 3) + (col % 3), 3); if (lockedPairCache[index + 1] == -1) { lockedPairCache[index + 1] = lockedPairCache[index + 2]; lockedPairCache[index + 2] = - 1; } if (lockedPairCache[index] == -1) { lockedPairCache[index] = lockedPairCache[index + 1]; lockedPairCache[index + 1] = lockedPairCache[index + 2]; lockedPairCache[index + 2] = - 1; } } } } } //////////////////////////////////////////////////////////////////////// // // CheckChain() // //////////////////////////////////////////////////////////////////////// function CheckChain () { ComputeCaches(); var n, k, i; longerChainExists = true; for (n = 3 ; stuck && longerChainExists ; n++) { longerChainExists = false; for (k = 0 ; stuck && (k < 81) ; k++) { // Look for a chain of pairs if (weight[xpos[k]] == 2) { SearchChain(n, k, Index(xpos[k]), 1); if (stuck) SearchChain(n, k, Index(xpos[k] & (xpos[k] - 1)), 1); } // Look for an alternating chain of a single digit if (stuck && xpos[k]) { for (i = 0 ; stuck && (i < 9) ; i++) { if (xpos[k] & (1 << i)) SearchChain(n, k, i, 0); } } } } // Sledgehammer longerChainExists = true; for (n = 3 ; stuck && longerChainExists ; n++) { longerChainExists = false; for (k = 0 ; stuck && (k < 81) ; k++) { for (i = 0 ; stuck && (i < 9) ; i++) { if (xpos[k] & (1 << i)) SearchChain(n, k, i, 2); } } } } //////////////////////////////////////////////////////////////////////// // // SolvePos() // //////////////////////////////////////////////////////////////////////// function SolvePos () { if (changed) GetPos(); var i, j, k, l; stuck = true; // Look for a digit with only one place to go in a row or column or block for (k = 0 ; k < 9 ; k++) { CheckSingletonDigit(9*k, 1); CheckSingletonDigit(k, 9); CheckSingletonDigit(27 * Math.floor(k/3) + (k%3), 3); } // Look for a square with only one possibility for (k = 0 ; (k < 81) && stuck ; k++) { var b = xpos[k]; if (b && !(b & (b-1))) { if (hintOnly) { GiveHint(SquareName(k) + " can only be " + (Index(xpos[k]) + 1) + DoItForMe(Index(xpos[k]), k)); SetHighlight(k, highlight_red); } else DoMove(Index(xpos[k]), k); } } // Bucket strategy: try to isolate a digit in one of three squares for (i = 0 ; (i < 3) && stuck ; i++) { for (j = 0 ; (j < 3) && stuck ; j++) { if (buckets[3*j+i]) { for (k = 0 ; k < 3 ; k++) { var mask1, mask2, mask3; var index1, index2; // Row bucket mask1 = mask2 = 0; index1 = 27 * j + 9 * k; index2 = 27 * j + i; mask3 = xpos[index2 + 9 * k] | xpos[index2 + 9 * k + 3] | xpos[index2 + 9 * k + 6]; for (l = 0 ; l < 9 ; l++, index1++, index2 += 3) { if ((l%3) != i) mask1 |= xpos[index1]; if (Math.floor(l/3) != k) mask2 |= xpos[index2]; } mask1 = mask3 & buckets[3*j+i] & ~(mask1 & mask2); if (mask1) { var isBlock = mask3 & ~mask2; while (mask1 && stuck) { mask2 = mask1 & -mask1; mask1 -= mask2; DoHorzBucket(Index(mask2), i, j, k, isBlock & mask2); } if (!stuck) break; } // Column bucket mask1 = mask2 = 0; index1 = 3 * k + i; index2 = 27 * j + i; mask3 = xpos[index2 + 3 * k] | xpos[index2 + 3 * k + 9] | xpos[index2 + 3 * k + 18]; for (l = 0 ; l < 9 ; l++, index1 += 9, index2 += 3) { if (Math.floor(l/3) != j) mask1 |= xpos[index1]; if ((l%3) != k) mask2 |= xpos[index2]; } mask1 = mask3 & buckets[3*j+i] & ~(mask1 & mask2); if (mask1) { var isBlock = mask3 & ~mask2; while (mask1 && stuck) { mask2 = mask1 & -mask1; mask1 -= mask2; DoVertBucket(Index(mask2), i, j, k, isBlock & mask2); } if (!stuck) break; } } } } } // Pigeonhole strategy: Find k squares that can only contain k digits, or // find k digits that can only be in k squares. for (k = 2 ; stuck && (k < 5) ; k++) { for (i = 0 ; i < 9 ; i++) { CheckPigeonhole(k, 9*i, 1); CheckPigeonhole(k, i, 9); CheckPigeonhole(k, 27 * Math.floor(i/3) + (i%3), 3); } } // Chain strategy: Find a chain of squares each with two possibilities // from which we can derive that one of the endpoints must be a certain // digit. if (stuck) CheckChain(); if (numSquares == 81) GiveHint("Solved!"); else if (stuck) { var count = 0; for (i = 0 ; i < 81 ; i++) { if (xpos[i]) count++; } if (numSquares + count == 81) GiveHint("I'm stumped!"); else GiveHint("No solution!"); } else if (!hintOnly) setTimeout("SolvePos()", 1); } //////////////////////////////////////////////////////////////////////// // // Reset() // //////////////////////////////////////////////////////////////////////// function Reset () { if (confirm("Reset sudoku board to initial position?")) { ResetHints(); var i; for (i = 0 ; i < 81 ; i++) document.sudoku["s" + i].value = pos[i]; changed = true; changedByJavascript = true; document.sudoku["hintButton"].focus(); } } //////////////////////////////////////////////////////////////////////// // // Erase() // //////////////////////////////////////////////////////////////////////// function Erase () { if (confirm("Erase sudoku board?")) { ResetHints(); var i; for (i = 0 ; i < 81 ; i++) pos[i] = document.sudoku["s" + i].value = ""; changed = true; changedByJavascript = true; document.sudoku["s0"].select(); } } //////////////////////////////////////////////////////////////////////// // // Solve() // //////////////////////////////////////////////////////////////////////// function Solve () { ClearHighlights(); GiveHint("Thinking..."); hintOnly = false; setTimeout("SolvePos()", 1); } //////////////////////////////////////////////////////////////////////// // // Hint() // //////////////////////////////////////////////////////////////////////// function Hint () { ClearHighlights(); GiveHint("Thinking..."); hintOnly = true; setTimeout("SolvePos()", 1); // SolvePos(); } //////////////////////////////////////////////////////////////////////// // // ResetHints() // //////////////////////////////////////////////////////////////////////// function ResetHints () { document.getElementById("hint").innerHTML = ""; ClearHighlights(); changed = true; document.sudoku["hintButton"].focus(); } //////////////////////////////////////////////////////////////////////// // // PrintBoard() // //////////////////////////////////////////////////////////////////////// function PrintBoard (print_state) { if (changed) GetPos(); var doc = window.open('',"name",'height=600,width=600').document; doc.writeln(""); doc.writeln(""); doc.writeln("
"); doc.writeln("


"); WriteBoard(doc, print_state ? 2 : 1); doc.writeln("
"); doc.close(); } //////////////////////////////////////////////////////////////////////// // // Fetch() // //////////////////////////////////////////////////////////////////////// function FetchPosition () { var win = window.open('',"loading",'height=75,width=170'); var doc = win.document; // doc.writeln(""); // doc.writeln(""); // doc.writeln(""); // doc.writeln(""); doc.writeln(""); doc.writeln(""); doc.writeln(""); doc.close(); alert(win.document.all[0].all[1].all[0].innerHTML); //win.close(); }