Skip to content

Instantly share code, notes, and snippets.

@Zazcallabah

Zazcallabah/sudokuSolve.user.js

Last active February 29, 2020 08:39
Show Gist options
  • Save Zazcallabah/2136f65dd9c9823befadc76c89088086 to your computer and use it in GitHub Desktop.
Save Zazcallabah/2136f65dd9c9823befadc76c89088086 to your computer and use it in GitHub Desktop.
Download ZIP
sudoku solver for websudoku
Raw
sudokuSolve.user.js
// ==UserScript==
// @name Sudokusolve
// @version 0.1
// @match https://nine.websudoku.com/*
// @grant none
// ==/UserScript==
(function () {
function cplxReduce(input, groupix) {
for (var i = 0; i < 8; i++) {
if (input[groupix[i]].length == 2) {
for (var j = i + 1; j < 9; j++) {
if (input[groupix[j]] == input[groupix[i]]) {
var exit = false;
var r1 = input[groupix[i]][0];
var r2 = input[groupix[i]][1];
for (var n = 0; n < 9; n++) {
if (n != i && n != j) {
if (input[groupix[n]].indexOf(r1) != -1) {
input[groupix[n]] = input[groupix[n]].replace(r1, "");
exit = true;
}
if (input[groupix[n]].indexOf(r2) != -1) {
input[groupix[n]] = input[groupix[n]].replace(r2, "");
exit = true;
}
}
}
if (exit)
return true;
}
}
}
}
return false;
}
function countInCell(input, cell, lookup) {
var cellstart = [0, 3, 6, 27, 30, 33, 54, 57, 60];
var celldiff = [0, 1, 2, 9, 10, 11, 18, 19, 20]
var hits = 0;
var hitix = -1;
for (var ix = 0; ix < 9; ix++) {
var arrix = cellstart[cell] + celldiff[ix];
var em = input[arrix];
if (em.length > 1 && em.indexOf(lookup) != -1) {
hitix = arrix;
hits++;
}
if (hits > 1)
break;
}
return {
hits: hits,
ix: hitix
};
}
function countInRow(input, row, lookup) {
var start = row * 9;
var hits = 0;
var hitix = -1;
for (var ix = 0; ix < 9; ix++) {
var arrix = start + ix;
var em = input[arrix];
if (em.length > 1 && em.indexOf(lookup) != -1) {
hitix = arrix;
hits++;
}
if (hits > 1)
break;
}
return {
hits: hits,
ix: hitix
};
}
var testresult = countInRow(
["6", "8", "5", "2", "3", "1", "4", "7", "9",
"3", "2", "4", "9", "7", "8", "1", "356", "2356",
"1", "9", "237", "4", "6", "5", "38", "238", "238",
"78", "4", "678", "67", "9", "2", "5", "3", "1",
"2", "5", "68", "1", "7", "3", "68", "9", "4",
"9", "3", "1", "5", "4", "68", "7", "2", "68",
"4", "67", "2678", "3", "5", "67", "9", "1", "68",
"78", "67", "9", "67", "1", "4", "2", "3568", "3568",
"5", "1", "36", "8", "2", "9", "36", "4", "7"],
2, 3)
console.assert(testresult.hits === 2, "fault in countInRow");
console.assert(testresult.ix === 24, "fault in countInRow index lookup");
function countInCol(input, col, lookup) {
var hits = 0;
var hitix = -1;
for (var ix = 0; ix < 9; ix++) {
var arrix = col + (ix * 9);
var em = input[arrix];
if (em.length > 1 && em.indexOf(lookup) != -1) {
hits++;
hitix = arrix;
}
if (hits > 1)
break;
}
return {
hits: hits,
ix: hitix
};
}
var testresult = countInCol(
["6", "8", "5", "2", "3", "1", "4", "7", "9",
"3", "2", "4", "9", "7", "8", "1", "356", "2356",
"1", "9", "237", "4", "6", "5", "38", "238", "238",
"78", "4", "678", "67", "9", "2", "5", "3", "1",
"2", "5", "68", "1", "7", "3", "68", "9", "4",
"9", "3", "1", "5", "4", "68", "7", "2", "68",
"4", "67", "2678", "3", "5", "67", "9", "1", "68",
"78", "67", "9", "67", "1", "4", "2", "3568", "3568",
"5", "1", "36", "8", "2", "9", "36", "4", "7"],
0, 1);
console.assert(testresult.hits === 0, "countInCol does not ignore solved squares");
var testresult = countInCol(
["6", "8", "5", "2", "3", "1", "4", "7", "9",
"3", "2", "4", "9", "7", "8", "1", "356", "2356",
"1", "9", "237", "4", "6", "5", "38", "238", "238",
"78", "4", "678", "67", "9", "2", "5", "3", "1",
"2", "5", "68", "1", "7", "3", "68", "9", "4",
"9", "3", "1", "5", "4", "68", "7", "2", "68",
"4", "67", "2678", "3", "5", "67", "9", "1", "68",
"78", "67", "9", "67", "1", "4", "2", "3568", "3568",
"5", "1", "36", "8", "2", "9", "36", "4", "7"],
2, 2);
console.assert(testresult.hits === 2, "countInCol hit error");
console.assert(testresult.ix === 56, "countInCol index error");
function uncleanSingle(input, i) {
var remove = input[i];
var row = Math.floor(i / 9);
var col = i % 9;
var cell = Math.floor(col / 3) + Math.floor(row / 3) * 3;
var unclean = false;
var cellstart = [0, 3, 6, 27, 30, 33, 54, 57, 60];
var celldiff = [0, 1, 2, 9, 10, 11, 18, 19, 20]
for (var ix = 0; ix < 9; ix++) {
var rowix = row * 9 + ix;
var colix = ix * 9 + col;
var cellix = cellstart[cell] + celldiff[ix];
if (rowix != i && input[rowix].length > 1) {
input[rowix] = input[rowix].replace(remove, "");
if (input[rowix].length == 1)
unclean = true;
}
if (colix != i && input[colix].length > 1) {
input[colix] = input[colix].replace(remove, "");
if (input[colix].length == 1)
unclean = true;
}
if (cellix != i && input[cellix].length > 1) {
input[cellix] = input[cellix].replace(remove, "");
if (input[cellix].length == 1)
unclean = true;
}
}
return unclean;
}
var inptest = ["6", "8", "5", "2", "3", "1", "4", "7", "9",
"3", "2", "4", "9", "7", "8", "1", "356", "2356",
"1", "9", "23", "4", "6", "5", "38", "238", "238",
"78", "4", "678", "67", "9", "2", "5", "3", "1",
"2", "5", "68", "1", "7", "3", "68", "9", "4",
"9", "3", "1", "5", "4", "68", "7", "2", "68",
"4", "67", "2678", "3", "5", "67", "9", "1", "68",
"78", "67", "9", "67", "1", "4", "2", "3568", "3568",
"5", "1", "36", "8", "2", "9", "36", "4", "7"];
console.assert(uncleanSingle(inptest, 10), "uncleanSingle not detecting dirty");
console.assert(inptest[20] === "3", "uncleanSingle not clearing cell");
function uncleanLine(input) {
for (var i = 0; i < 9; i++) {
for (var nr = 1; nr <= 9; nr++) {
var testr = countInRow(input, i, nr);
if (testr.hits == 1) {
input[testr.ix] = nr.toString();
return true;
}
var testr = countInCol(input, i, nr);
if (testr.hits == 1) {
input[testr.ix] = nr.toString();
return true;
}
var testr = countInCell(input, i, nr);
if (testr.hits == 1) {
input[testr.ix] = nr.toString();
return true;
}
}
}
return false;
}
var inptest =
["6", "8", "5", "2", "3", "1", "4", "7", "9",
"3", "2", "4", "9", "7", "8", "1", "356", "356",
"1", "9", "23", "4", "6", "5", "38", "238", "238",
"78", "4", "678", "67", "789", "2", "5", "3", "1",
"2", "5", "68", "1", "7", "3", "68", "9", "4",
"9", "3", "1", "5", "4", "68", "7", "2", "68",
"4", "67", "2678", "3", "5", "67", "9", "1", "68",
"78", "67", "9", "67", "1", "4", "2", "3568", "3568",
"5", "1", "36", "8", "2", "9", "36", "4", "7"];
console.assert(uncleanLine(inptest), "dirty not flagged");
console.assert(inptest[20] === "2", "single on line not detected");
function getInputData(indata) {
var input = new Array(81);
for (var i = 0; i < 81; i++) {
if (indata[i].childNodes[0].className == "s0" || indata[i].childNodes[0].value != "") {
input[i] = indata[i].childNodes[0].value;
}
else {
input[i] = "123456789";
}
}
return input;
}
function setResult(indata, input) {
var logstr = "";
for (var i = 0; i < 81; i++) {
logstr += `"${input[i]}",`;
if (i % 9 == 8) logstr += "\n";
if (indata[i].childNodes[0].className != "s0") {
var f = indata[i].childNodes[0];
f.maxlength = "9";
f.value = input[i];
if (f.value.length > 3) {
f.className = 'v' + f.className.substr(1, 10);
} else if (f.value.length > 1) {
f.className = 'w' + f.className.substr(1, 10);
} else {
f.className = 'd' + f.className.substr(1, 10);
}
}
}
console.log(logstr);
}
function innerSeek(input) {
for (var i = 0; i < 9; i++) {
var rowgroupix = [...Array(9).keys()].map(function (n) { return n + (9 * i) });
if (cplxReduce(input, rowgroupix)) {
break;
}
var colgroupix = [...Array(9).keys()].map(function (n) { return i + (9 * n) });
if (cplxReduce(input, colgroupix)) {
break;
}
var cellstart = [0, 3, 6, 27, 30, 33, 54, 57, 60];
var celldiff = [0, 1, 2, 9, 10, 11, 18, 19, 20]
var cellgroupix = [...Array(9).keys()].map(function (n) { return cellstart[i] + celldiff[n] });
if (cplxReduce(input, cellgroupix)) {
break;
}
}
}
var testinp = ["4", "2368", "5", "1", "9", "28", "46", "7", "2346",
"149", "12369", "236", "23457", "2345", "257", "8", "234569", "23469",
"7", "2389", "238", "6", "23458", "258", "1", "23459", "2349",
"6", "12379", "237", "23579", "1235", "4", "59", "8", "29",
"8", "279", "4", "2579", "256", "25679", "3", "2569", "1",
"19", "5", "23", "8", "1236", "269", "469", "2469", "7",
"2", "678", "1", "49", "468", "3", "4679", "469", "5",
"35", "3678", "9", "245", "24568", "2568", "467", "1346", "3468",
"35", "4", "368", "59", "7", "1", "2", "369", "3689"]
var result = innerSeek(testinp);
console.assert(JSON.stringify(testinp) === JSON.stringify(["4", "2368", "5", "1", "9", "28", "46", "7", "2346",
"149", "12369", "236", "23457", "2345", "257", "8", "234569", "23469",
"7", "2389", "238", "6", "23458", "258", "1", "23459", "2349",
"6", "12379", "237", "23579", "1235", "4", "59", "8", "29",
"8", "279", "4", "2579", "256", "25679", "3", "2569", "1",
"19", "5", "23", "8", "1236", "269", "469", "2469", "7",
"2", "678", "1", "49", "468", "3", "4679", "469", "5",
"35", "678", "9", "245", "24568", "2568", "467", "1346", "3468",
"35", "4", "68", "59", "7", "1", "2", "369", "3689"]), "fault in cplxReduce");
function _go() {
var indata = document.getElementById("puzzle_grid").getElementsByTagName("td");
var input = getInputData(indata);
do {
for (var i = 0; i < 81; i++) {
if (input[i].length == 1) {
if (uncleanSingle(input, i)) {
i = -1;
}
}
}
} while (uncleanLine(input));
setResult(indata, input);
return false;
}
function _seek() {
var indata = document.getElementById("puzzle_grid").getElementsByTagName("td");
var input = getInputData(indata);
innerSeek(input);
setResult(indata, input);
return false;
}
function _edit() {
var indata = document.getElementById("puzzle_grid").getElementsByTagName("td");
for (var i = 0; i < 81; i++) {
if (indata[i].childNodes[0].className == "s0") {
indata[i].childNodes[0].className = "d0"
indata[i].childNodes[0].readOnly = false;
}
}
return false;
}
function _step() {
var indata = document.getElementById("puzzle_grid").getElementsByTagName("td");
var input = getInputData(indata);
var initlist = [];
for (var i = 0; i < 81; i++) {
if (input[i].length == 1) {
initlist.push(i)
}
}
for (var i = 0; i < initlist.length; i++) {
uncleanSingle(input, initlist[i])
}
setResult(indata, input);
return false;
}
if (typeof document !== 'undefined') {
document.getElementById('puzzle_container').innerHTML += "<button type='button' id='editbutton'>Edit</button><button type='button' id='stepbutton'>Step</button><button type='button' id='seekbutton'>Seek</button><button type='button' id='gobutton'>Go</button>";
document.getElementById('gobutton').onclick = _go;
document.getElementById('stepbutton').onclick = _step;
document.getElementById('seekbutton').onclick = _seek;
document.getElementById('editbutton').onclick = _edit;
}
})();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment