randomfox (randomfox) wrote,
randomfox
randomfox

Sudoku Solver in Javascript


<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
    "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">

<head>
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1" />
<meta http-equiv="Content-Language" content="en-us" />
<meta http-equiv="imagetoolbar" content="false" />
<meta name="MSSmartTagsPreventParsing" content="true" />
<meta name="author" content="Po Shan Cheah" />

<title>Sudoku Solver</title>

<script type="text/javascript">

function clearOutput() {
    var output = document.getElementById("output");
    while (output.firstChild)
	output.removeChild(output.firstChild);
}

// Write a string to the output area.
function write(str) {
    var output = document.getElementById("output");
    var txt = document.createTextNode(str);
    output.appendChild(txt);
}

// Write a string with a newline to the output area.
function writeln(str) {
    var output = document.getElementById("output");
    var txt = document.createTextNode(str);
    var newline = document.createElement("br");
    output.appendChild(txt);
    output.appendChild(newline);
}

// Write a string in red to signify an error.
function errorln(str) {
    var output = document.getElementById("output");
    var txt = document.createTextNode(str);
    var newline = document.createElement("br");
    var span = document.createElement("span");
    // setAttribute("class" ...) does not work in IE.
    span.className = "error";
    span.appendChild(txt);
    span.appendChild(newline);
    output.appendChild(span);
}

// Display the board.
function printboard(board) {
    for (var i = 0; i < 9; ++i)
	writeln(board[i].join(""));
}

// Parse the board info from the text area.
function processinput(board) {
    var input = document.getElementById("input");
    
    var lineno = 0;
    var lines = input.value.split("\n", 100);
    for (var i = 0; i < lines.length; ++i) {
	var line = lines[i].replace(/\s+/g, "");
	if (line.length > 0) {
	    if (line.length < 9) {
		errorln("line " + lineno + " '" + line + "' is too short.");
		return false;
	    }
//	    writeln(line);
	    var row = new Array();
	    for (var j = 0; j < 9; ++j) {
		var tmp = parseInt(line.charAt(j));
		row[j] = isNaN(tmp) ? 0 : tmp;
	    }
	    board[lineno++] = row;
	}
    }
    if (lineno < 9) {
	errorln("not enough rows. only " + lineno + " found.");
	return false;
    }
    return true;
}

// Return a list of numbers that could go into cell row, col on the board.
function getpossible(board, row, col) {
    var used = [];

// Check row and column.
    for (var i = 0; i < 9; ++i) {
	used[board[row][i]] = true;
	used[board[i][col]] = true;
    }

// Check the 3x3 block containing this cell.
    var blockrow = row - row % 3;
    var blockcol = col - col % 3;
    for (var i = blockrow; i < blockrow + 3; ++i) {
	for (var j = blockcol; j < blockcol + 3; ++j)
	    used[board[i][j]] = true;
    }

    var possible = [];
    for (var i = 1; i <= 9; ++i)
	if (!used[i])
	    possible.push(i);
    return possible;
}

var nodecount;

// Recursive function to find a solution by exhaustive search.
function tryboard(board, row, col) {
    if (row >= 9 || col >= 9) {
	writeln("");
	writeln("Found a solution:");
	printboard(board);
	return true;
    }
    
    ++nodecount;

    var nextrow = row;
    var nextcol = col + 1;
    if (nextcol >= 9) {
	nextrow = row + 1;
	nextcol = 0;
    }

// Skip over cells that are already filled.
    if (board[row][col] != 0)
	return tryboard(board, nextrow, nextcol);

    var possible = getpossible(board, row, col);
    while (possible.length > 0) {
	var cell = possible.shift();
	board[row][col] = cell;
	if (tryboard(board, nextrow, nextcol))
	    return true;
    }
    board[row][col] = 0;
    return false;
}

function main() {
    clearOutput();
    var board = [];
    if (processinput(board)) {
	writeln("Puzzle:");
	printboard(board);
	nodecount = 0;
	var start = new Date();
	if (!tryboard(board, 0, 0))
	    writeln("No solution found");
	var end = new Date();
	var elapsed = (end.getTime() - start.getTime()) / 1000;
	writeln(nodecount + " nodes examined");
	writeln("Elapsed time: " + elapsed + " seconds");
    }
}

</script>

<style type="text/css">
body {
    background: #fff none;
    color: #000;
    font: normal 14px Tahoma, Verdana, Arial, Helvetica, sans-serif;
}

.error {
    color: red;
}

#output {
    white-space: pre;
    font: normal 14px monospace;
}
</style>
</head>

<body>
    <h1>Sudoku Solver</h1>
    <noscript>
	<span class="error">
	    The Sudoku Solver requires a browser that supports Javascript.<br />
	    Your browser either does not support Javascript or it has Javascript disabled. If you wish to run the solver, please upgrade your browser or enable Javascript support.<br />&nbsp;<br />
	</span>
    </noscript>

    <script type="text/javascript">
<!--
// Test for W3C DOM API.
if (document.getElementById) {
}
else {
    document.write('<span class="error">The Sudoku Solver requires a browser that supports the W3C DOM API.<br \/>Your browser does not support this API. If you wish to run the solver, please upgrade your browser. The latest versions of Mozilla Firefox, Opera, and Internet Explorer have support for this API.<br \/>&nbsp;<br \/><\/span>');
}
// -->
    </script>

    <form action="#">
	Enter the puzzle below:<br />
	<textarea id="input" rows="15" cols="40">xxx 6xx 9x2
xx6 1xx x87
2x7 5xx xx1

xxx xx8 7xx
4x2 xxx 1x6
xx9 2xx xxx

6xx xx3 5x8
59x xx1 2xx
8x4 xx7 xxx</textarea><br />
	<input type="submit" value="Solve it!" onclick="main(); return false;" />
    </form>
    <hr />
    <div id="output">
    </div>
</body>

</html>
<!--
Last updated: March 28, 2006
-->
<!-- vim:set tw=0: -->

Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 0 comments