-
-
Save kaosat-dev/153967eb7e10302587b4 to your computer and use it in GitHub Desktop.
sudoku solver
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#grid { | |
border: 1px solid #000; | |
border-spacing:0; | |
} | |
#grid tr:nth-child(3) td, | |
#grid tr:nth-child(6) td { | |
border-bottom: 1px solid #000; | |
} | |
#grid td { | |
width: 24px; | |
height: 24px; | |
vertical-align: middle; | |
text-align: center; | |
border: 1px solid #eee; | |
} | |
#grid td:nth-child(3), | |
#grid td:nth-child(6) { | |
border-right: 1px solid #000; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(function(R, solver) { | |
// stoyan stefanov's `sleep` function | |
function sleep(milliseconds) { | |
var start = new Date().getTime(); | |
for (var i = 0; i < 1e7; i++) { | |
if ((new Date().getTime() - start) > milliseconds){ | |
break; | |
} | |
} | |
} | |
var render = function(g) { | |
var grid = document.getElementById('grid'); | |
var htmlStr = R.reduce(function(acc, row) { | |
return acc += '<tr>' + | |
R.reduce(function(acc, cell) { | |
return acc + '<td>' + cell + '</td>'; | |
}, '', row) + | |
'</tr>'; | |
}, '', g); | |
grid.innerHTML = htmlStr; | |
sleep(500); | |
}; | |
solver.setRenderer(render); | |
}(ramda, solver)); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
var solver = (function(R) { | |
var EMPTY = 0; | |
var defaultGrid = [ | |
[5, 0, 0, 1, 0, 0, 9, 3, 0], | |
[6, 4, 0, 0, 7, 3, 0, 8, 0], | |
[0, 0, 1, 8, 0, 5, 0, 0, 0], | |
[8, 0, 0, 3, 4, 0, 0, 1, 0], | |
[0, 0, 0, 5, 2, 1, 0, 0, 0], | |
[0, 2, 0, 0, 8, 9, 0, 0, 6], | |
[0, 0, 0, 6, 0, 7, 8, 0, 0], | |
[0, 8, 0, 9, 3, 0, 0, 7, 1], | |
[0, 1, 3, 0, 0, 8, 0, 0, 9] | |
]; | |
function constrain(g, cell) { | |
var rowWise = R.difference(R.range(1,10), g[cell.y]); | |
var colWise = R.difference(rowWise, colToArray(g, cell.x)); | |
var boxWise = R.difference(colWise, boxToArray(g, cell)); | |
return boxWise; | |
} | |
function render(g) { | |
console.log("solved"); | |
g.forEach(function(r) { | |
console.log(r); | |
}); | |
} | |
function update(g, cell, value) { | |
g[cell.y][cell.x] = value; | |
} | |
function solve(g, x, y) { | |
g = g || defaultGrid; | |
var cell = findEmptyCell(g, x || 0, y || 0); | |
var i = 0; | |
if (!cell) { | |
render(g); | |
return true; | |
} | |
var domain = constrain(g, cell); | |
while (i < domain.length) { | |
update(g, cell, domain[i]); | |
if (solve(g, cell.x, cell.y)) { | |
return true; | |
} | |
// mark cell as empty and backtrack | |
update(g, cell, EMPTY); | |
i += 1; | |
} | |
return false; | |
} | |
function findEmptyCell(g, x, y) { | |
var cell = {}; | |
cell.y = R.findIndex(function(r) { return R.contains(EMPTY, r); }, g); | |
if (cell.y !== false) { | |
cell.x = R.findIndex(function(c) { return c === EMPTY; }, g[cell.y]); | |
} | |
return (cell.y !== false && cell.x !== false) ? cell : false; | |
} | |
function colToArray(g, x) { | |
return R.pluck(x, g); | |
} | |
function boxToArray(g, cell) { | |
var boxCol = Math.floor(cell.x/3) * 3; | |
var boxRow = Math.floor(cell.y/3) * 3; | |
return R.reduce(function(acc, row) { | |
return acc.concat(R.map(R.I, row.slice(boxCol, 3))); | |
}, [], g.slice(boxRow, 3)); | |
} | |
return { | |
solve: solve, | |
setRenderer: function(fn) { render = fn; } | |
}; | |
}(ramda)); | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<!doctype html> | |
<html> | |
<head> | |
<title>Sudoku solver</title> | |
<link rel="stylesheet" href="gridstyle.css" /> | |
</head> | |
<body> | |
<h1>Solver</h1> | |
<table id="grid"> | |
</table> | |
<button onclick="solver.solve()">Solve</solve> | |
<script src="ramda.js"></script> | |
<script src="solver.js"></script> | |
<script src="render.js"></script> | |
</body> | |
</html> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment