Skip to content

Instantly share code, notes, and snippets.

@mcordingley

mcordingley/Solver.js

Last active August 29, 2015 14:20
Show Gist options
  • Save mcordingley/0c945653d148d3ff3639 to your computer and use it in GitHub Desktop.
Save mcordingley/0c945653d148d3ff3639 to your computer and use it in GitHub Desktop.
Download ZIP
Algorithmic Sudoku Solver
Raw
index.html
<!DOCTYPE html>
<html>
<head>
<title>TODO supply a title</title>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<style>
.board__input--is-error {
background-color: #faa;
}
</style>
</head>
<body>
<div class="board"></div>
<input type="button" class="js-solve" value="Solve" />
<script src="Sudoku.js"></script>
<script src="Solver.js"></script>
<script src="page.js"></script>
</body>
</html>
Raw
page.js
(function() {
'use strict';
var board = document.querySelector('.board');
// Build the board, because doing it in raw HTML is too repetitive.
(function(){
var fragment = document.createDocumentFragment(),
row, input, i, j;
for (i = 0; i < 9; i++) {
row = document.createElement('div');
for (j = 0; j < 9; j++) {
input = document.createElement('input');
input.setAttribute('name', 'board[' + i + '][' + j + ']');
input.setAttribute('maxlength', 1);
input.setAttribute('size', 1);
input.setAttribute('type', 'text');
row.appendChild(input);
}
fragment.appendChild(row);
}
board.appendChild(fragment);
})();
var sudoku = new Sudoku(),
positionExtractor = /\w+\[(\d+)\]\[(\d+)\]/;
board.addEventListener('change', function(event) {
var target = event.target;
if (!target.matches('input')) {
return;
}
var name = target.getAttribute('name'),
coords = name.match(positionExtractor).slice(1);
sudoku.set(coords[0], coords[1], target.value);
if (sudoku.checkValid(coords[0], coords[1])) {
target.classList.remove('board__input--is-error');
} else {
target.classList.add('board__input--is-error');
}
});
document.querySelector('.js-solve').addEventListener('click', function(event) {
var solution = solveBoard(sudoku),
i, j;
for (i = 0; i < 9; i++) {
for (j = 0; j < 9; j++) {
document.querySelector('input[name="board[' + i + '][' + j + ']"]').value = solution.get(i, j);
}
}
})
})();
Raw
Solver.js
(function(root, Sudoku) {
'use strict';
/*
* Depth-first search tree of the Sudoku board. Should be as good as A*,
* since there's no real heuristic to direct the search and give A* an
* advantage.
*/
root.solveBoard = function(board) {
var open = [],
closed = {},
current, next, coords, i;
open.push(board.toArray());
while (open.length) {
// Grab the next board state and add it to the closed set.
current = new Sudoku(open.pop());
closed[current.toString()] = current.toArray();
// Iterate over the set of possible changes to this board state by
// going through the possible values in the next empty cell.
next = new Sudoku(current.toArray());
coords = next.getEmptyCell();
// Valid states
for (i = 1; i < 10; i++) {
next.set(coords[0], coords[1], i);
// If If this is an invalid board state, skip this branch of possibility.
if (closed[next.toString()] || !next.checkValid(coords[0], coords[1])) {
continue;
}
// Check for a complete board.
if (!next.getEmptyCell()) {
return next;
}
open.push(next.toArray());
}
}
// No solution found.
return null;
};
})(this, Sudoku);
Raw
Sudoku.js
(function(root) {
'use strict';
// Helper to safely extract values from an array.
var valueGetter = function(state, i, j) {
if (i < 0 || i > 8 || j < 0 || j > 8) {
return null;
}
if (!Array.isArray(state) || !Array.isArray(state[i])) {
return null;
}
return state[i][j] || null;
};
var toInt = function(value) {
return parseInt(value, 10);
};
root.Sudoku = function(state) {
this._internal = [];
// Build internal board representation
var i, j;
for (i = 0; i < 9; i++) {
this._internal[i] = [];
for (j = 0; j < 9; j++) {
this._internal[i][j] = valueGetter(state, i, j);
}
}
};
var proto = root.Sudoku.prototype;
/**
* checkValid
*
* Checks to see if the value at the specified row and column is valid for
* the current board state.
*
* @param {int} row
* @param {int} column
* @returns {Boolean}
*/
proto.checkValid = function(row, column) {
row = toInt(row);
column = toInt(column);
var value = this.get(row, column),
i, j;
// Short-cut out if no value is set.
if (value === null) {
return true;
}
// Check Lines
for (i = 0; i < 9; i++) {
// Row
if (i !== row && value === this.get(i, column)) {
return false;
}
// Column
if (i !== column && value === this.get(row, i)) {
return false;
}
}
// Check Square
var horizontalMin = column - (column % 3),
horizontalMax = horizontalMin + 3,
verticalMin = row - (row % 3),
verticalMax = verticalMin + 3;
for (i = verticalMin; i < verticalMax; i++) {
for (j = horizontalMin; j < horizontalMax; j++) {
if (i !== row && j !== column && value === this.get(i, j)) {
return false;
}
}
}
// Hasn't failed anything, must be good.
return true;
};
/**
* get
*
* @param {int} row
* @param {int} column
* @returns {int|null}
*/
proto.get = function(row, column) {
row = toInt(row);
column = toInt(column);
return valueGetter(this._internal, row, column);
};
/**
* getEmptyCell
*
* Returns the next empty cell, if one exists.
*
* @returns {Array|null}
*/
proto.getEmptyCell = function() {
for (var i = 0; i < 9; i++) {
for (var j = 0; j < 9; j++) {
if (!this.get(i, j)) {
return [i, j];
}
}
}
return null;
};
/**
* set
*
* @param {int} row
* @param {int} column
* @param {int} value
* @returns {Board}
*/
proto.set = function(row, column, value) {
row = toInt(row);
column = toInt(column);
value = toInt(value);
if (row > -1 && row < 9 && column > -1 && column < 9) {
this._internal[row][column] = value;
}
return this;
};
/**
* toArray
*
* @returns {Array}
*/
proto.toArray = function() {
var copy = [], i, j;
for (i = 0; i < 9; i++) {
copy[i] = [];
for (j = 0; j < 9; j++) {
copy[i][j] = this._internal[i][j];
}
}
return copy;
};
/**
* toString
*
* @returns {string}
*/
proto.toString = function() {
return '[' + this._internal.map(function(row) { return '[' + row.join(',') + ']'; }).join(',') + ']';
};
})(this);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment