Like many people here in the UK I have been struck down with the Sudoku bug, and as a programmer wondered vaguely how I would go about mechanising the various techniques I’ve figured out for solving the little sods. A couple of days ago, tackling a particularly nasty one, I was forced to do something I normally avoid: picking one of the available options on a particular square and tracing the consequences. Then it struck me: this was the way to get a computer to solve the puzzle. I find it hurts my frontal lobes trying to hold all the possibilities in my head at once, but computers excel at this. Fill in the ones you can, then pick a possibility and go round again. You’ll either hit lucky or hit a brick wall. Recursion, here we come!
So I have developed my idea into a Sudoku solving web page. If you’re not interested in the technical details, but just want to solve a few sudoku puzzles, the sudoku solver is here.
Kind-of Extreme, Object Oriented Programming
I love javascript, and its loose typing is ideal in a scenario where a given square may contain a single number, a list of possibilities, or nothing. But I wanted to do proper OOP javascript. Some people still don’t seem to have got the message that this is possible, but here it is a real boon if not an absolute necessity, as my algorithm is intrinsically recursive.
After knocking up a nice-looking HTML form to gather and display the grid, I wrote my first bit of javascript, to be called by the form’s onsubmit attribute. It wasn’t much different to the final version quoted here:
function solve() {
store = getTableData();
var solution = solveTable(store);
if (solution.getResult() != "solved") {
alert("it appears this puzzle cannot be solved");
return false;
}
populateForm(solution.getTable());
return false; //stop action being called
}
A lot of wishful thinking, there, but I have some sympathy with the Extreme Programming philosophy, which in affect says: "just start coding". That’s how my mates and I used to knock programs together back in our ZX81 days, in any case. It’s the object-orientated part that come less easily to me, having begun with Sinclair BASIC, though I’m finally starting to think along those lines even when it comes to the non-obvious OOP likes of JS.
So what does this solveTable() function do, exactly? Well, the idea is that it scans through a table and returns another table in which every gap has been replaced by a list (javascript array) of possibilities for that square. It also needs a way of indicating whether the table has been solved (hurrah!) or if it led to a blind alley (boo!), as well as the most likely scenario that some but not all of the squares have been filled with a single number.
Classwork
I decided to create two classes (if one can properly call them than in JS, maybe object constructors is a better term): The first was Table - to hold the various intermediate grids and do stuff to them. Here is its constructor:
function Table(a) {
//a is optional 9x9 array
this.it = new Array(9); // (col, row)
for (var k=0; k<9; k++) {
this.it[k] = new Array(9);
}
if (a) {
for (var j=0; j<9; j++) {
for (var i=0; i<9; i++ ) {
this.it[i][j] = a[i][j];
}
}
}
}
To simulate a multidimensional array in javascript you have to intialise each element of an ‘outer’ array to itself be an (‘inner’) array. The optional initialisation array might turn out to be useful.
At first I had a syntax error in here where the third line read:
var it = new Array(9); // (col, row)
This project taught me that the var keyword can be problematic in ECMAScript languages like js. The above line looks directly analagous to a line of Java code, such as:
Array it = new Array(9);
but js ‘classes’ are a bit of a kludge, and the this keyword is required so that the new array gets attached to the instance of the object being constructed.
I also made simple getter and setter methods (agaist which the old, non-OOP self inside tries to rebel: "Why not just reach in and get the thing you need?", it rants).
Table.prototype.getDataAt = function(coord) {
return this.it[coord[0]][coord[1]];
};
Table.prototype.setDataAt = function(coord, value) {
this.it[coord[0]][coord[1]] = value;
};
I managed to screw these up at first, too, writing stuff like:
return this.it[coord[0], coord[1]];
Wake up, brain! No native multidimensional arrays in js!
The nature of the Table object is that changes are made ‘in place’. This is a key feature of my algorithm, so that the latest version of the grid, with any completed boxes, is always right there.
This next bit was my first real benefit of using OOP. Orignally I had three helper methods which found all the filled-in squares in a given element’s neighbouring column, row and 3x3 square, respectively. When I realised I could make them object methods, I no longer needed to keep track of which copy of the grid I was currently working with (a nightmarish task, which would still go on to cause a frustrating bug at the end).
Table.prototype.neighbourhoodCol = function(coord) {
//iterate down column, so col number is fixed
//returns a vector of other known numbers in the same column
var retVect = new Array();
var temp;
for (var j=0; j<9; j++ ) {
temp = this.it[coord[0]][j];
if (typeof(temp) == "number") {
retVect.push(temp);
}
}
return retVect;
};
Table.prototype.neighbourhoodRow = function(coord) {
//returns a vector of other known numbers in the same row
var retVect = new Array();
var temp;
for (var i=0; i<9; i++ ) {
temp = this.it[i][coord[1]];
if (typeof(temp) == "number") {
retVect.push(temp);
}
}
return retVect;
};
Table.prototype.neighbourhoodSquare = function(coord) {
//returns a vector of known numbers in the same 3x3 square
//calc top left of square:
var sqx = (Math.floor(coord[0]/3))*3;
var sqy = (Math.floor(coord[1]/3))*3;
var retVect = new Array();
var temp;
//iterate through square
for (var j=0; j<3; j++) {
for (var i=0; i<3; i++ ) {
temp = this.it[sqx+i][sqy+j];
if (typeof(temp) == "number") {
retVect.push(temp);
}
}
}
return retVect;
};
At last, some sudoku-specific code! And it worked pretty much straight away, once I’d realised that typeof() returns "number" (with a small ‘n’) when passed a Number (big ‘n’).
push() is a very nice way of building an array of indeterminate length, just by shoving items onto the end in a stack-like way. Oh, and please forgive me for continually referring to single-dimensional arrays as ‘vectors’.
Rapid Response
The other class I needed was a responseObject which gets returned from the solveTable() method with various helpful bits of info, such as the current Table; a string to indicate success, failure or the need for another go round; and the coordinates of an undetermined element with the least number of possibilities, to cut down on the size of the search tree (really the only bit of optimisation I’ve done on this. I’m sure there’s bags more room for improvement.)
function responseObject(t, r, l) { //constructor
this.obj = { "table":t, "result":r, "least":l };
}
responseObject.prototype.getTable = function() {
return this.obj["table"];
};
responseObject.prototype.getResult = function() {
return this.obj["result"];
};
responseObject.prototype.getLeastCoords = function() {
return this.obj["least"];
};
The simplicity of OOP code belies its power. That looks like nothing. But it will come in very handy when that nasty bug I mentioned rears its antennae. Do note the object constructor literal:
this.obj = { "table":clonedTable, "result":r, "least":l };
ECMAScript objects are associative arrays (aka hashtables), where the index can be any string - one of the more powerful data structures. I love that this power is always there under the bonnet, should you ever need it, even when doing the most basic stuff.
The First of Many Solutions
So we have most of what we need for the long sought-after solveTable() function (not an object method, notice, as we need to recurse on it):
function solveTable(t) { //to be recursed, returns a responseObject
var attempt = findPossibilities(t); //returns a responseObject
if (attempt.getResult()=="solved") { return attempt.clone(); }
if (attempt.getResult()=="failed") {
return new responseObject(t, "failed", null);
}
var origT = attempt.getTable();
var coord = attempt.getLeastCoords(); //this is a 2-vector
var bestAttempt;
var possArray = origT.getDataAt(coord);
for (var i=0; i<possArray.length; i++ ) { //should have at least 2 entries
var newT = origT.clone();
newT.setDataAt(coord, possArray[i]);
var attempt2 = solveTable(newT);
if (attempt2.getResult() == "solved") { return attempt2.clone(); }
if (attempt2.getResult() == "unsolved") {
bestAttempt = attempt2.clone();
} //not really best, just an attempt that didn’t fail
}
if (bestAttempt) { return bestAttempt.clone(); }
else {
return new responseObject(origT, "failed", null);
}
}
Ok, ok - so I deferred most of the heavy lifting to findPossibilities(), but this is just for legibility, making it easier for me to think about the main recusion, which schematically goes:
solveTable():
- get possibilities
- if solved, return
- otherwise, iterate over possibilities at a single unsolved position (the one with least choices)
- run
solveTable() on each
- return best attempt
It was as I was writing this that I had my first ely that there might be a problem with the working-in-place nature of the Table class. In order to differentiate the multiple grids produced by each attempt, I introduced a clone() method (below) which is called before the main loop is entered:
Table.prototype.clone = function() {
return new Table(this.it);
};
Since each Table is modified in place, every time we embark on a new variation, a fresh copy must be made.
The findPossibilities() helper function, together with its sub-helpers union() and makeNegative(), adds up to a lot of code, but it just does the donkeywork of aggregating the three sets of possibilities, calculating the least unsolved coordinate, and making the appropriate responseObject.
function findPossibilities(inTable) {
var outTable = inTable.clone();
// we work in place, so make clone of original to work on
var coord = new Array(2);
var response = "solved";
var least;
var leastLength = 10;
//var hashNew=0;
for (var j=0; j<9; j++) {
for (var i=0; i<9; i++ ) {
coord = [i, j]; //col, row
if (typeof(outTable.getDataAt(coord)) == "number") {
continue; } // already filled in
var nr = outTable.neighbourhoodRow(coord);
var nc = outTable.neighbourhoodCol(coord);
var ns = outTable.neighbourhoodSquare(coord);
var nu = union(nr, union(nc, ns));
//all known numbers it can’t be
if (nu.length==9) { // gone wrong
response="failed";
break;
}
var un = makeNegative(nu);
if (un.length==1) { // found entry, stored as a number
outTable.setDataAt(coord, un[0]);
} else {
//hashNew+=un.length;
outTable.setDataAt(coord, un);
// otherwise store array of possibilities
response = "unsolved";
if (un.length < leastLength) {
leastLength = un.length;
least = coord;
}
}
}
//showTable(outTable);
if (response=="failed") break;
}
return new responseObject(outTable, response, least);
}
function union(a, b) { //set theoretic union of two arrays
if (!b || b.length==0) return a;
if (!a || a.length==0) return b;
var retVect = new Array();
for (var i=0; i<a.length; i++) { //deep copy of a
retVect.push(a[i]);
}
var tester;
var gotIt;
//manual scan through for (var i=0; i<b.length; i++) {
tester = b[i];
gotIt = false;
for (var j=0; j<a.length; j++) {
if (a[j] == tester) {
gotIt = true;
break;
}
}
if (gotIt) continue;
retVect.push(tester);
}
return retVect;
}
function makeNegative(v) {
var set = [1, 2, 3, 4, 5, 6, 7, 8, 9 ];
for (var i=0; i<v.length; i++) {
set[v[i]-1] = null; // put null in place of found number
}
var retVect= new Array();
for (var i=0; i<9; i++) { // accumulate non-null entries
if (set[i]) { retVect.push(set[i]); }
}
return retVect;
}
These last two functions are pretty ugly, but they get the job done. JS doesn’t have any set-theoretic functions as far as I know, and I only did one term of computer science, so my union() function looks amateurish even to me. If anyone knows a more elegant solution, please leave a comment. makeNegative() is another sudoku-specific piece of code, figuring out what’s left once you eliminate the numbers it can’t be.
What’s Bugging You?
Putting in the so-dull-they’re-left-as-exercises-for-the-reader getTableData() and populateForm() functions enabled testing to begin, but even aided by the wonderful Firebug extension to Firefox, and my custom trace() function:
function trace(s) {
var tr = document.getElementById("trace");
var para = document.createElement("p");
tr.appendChild(para);
para.innerHTML=s;
}
with its accompanying html:
<div id="trace" style="position:absolute; right:0; top:0; width:400px;
height:100%; border:1px solid pink; overflow:auto;
font-size:12px; line-height:11px; margin:0; padding:0"></div>
it seemed I couldn’t iron out every bug. Most of the time it would loop endlessly, or return "failed", but occasionally it would appear to solve the puzzle correctly, apart from one stray, wrong digit! Only by a thorough mental re-examination of the algorithm was I able to convince myself that it was sound, and must always return a valid result if properly implemented.
Well-positioned trace() calls and, particularly, use of a special showTable() helper:
function showTable(t) {
var temp;
for (var j=0; j<9; j++) {
var g = "";
for (var i=0; i<9; i++ ) {
temp = t.getDataAt([i,j]);
g+=((temp) ? temp : ".")+" ";
}
trace("<pre>"+g+"</pre>");
}
}
showed that things progressed normally until a “failed” state was found (ie a position had no possibilities at all), and the depth-first search had to backtrack up the recursion stack. At which point it seemed data corruption occurred; in other words, because the Tables are being passed by reference, subsequent iterations were accessing old data, causing mayhem. Armed with this, I made two changes which to my slight shock instantly fixed all the problems:
I introduced a clone() method to the responseObject,
responseObject.prototype.clone = function() {
return new responseObject(this.getTable(), this.getResult(),
this.getLeastCoords());
}
invoking it whenever such an object was passed back. I also modified the responseObject constructor so that a clone of the Table is passed, not the original.
function responseObject(t, r, l) { //constructor
var clonedTable = t.clone();
this.obj = { "table":clonedTable, "result":r, "least":l };
}
Whether both of these are necessary, I’m not sure. Recursion still makes my brain hurt, especially when coupled with pass-by-reference and OOP.
I’m not sure if the resulting page will be useful to many people as an actual tool, though my daughter suggested it could be used for creating your own sudoku puzzles (by typing in a few random digits and seeing if a solution exists). At the moment, however, my algorithm cannot detect whether the solution it finds is unique. In fact, because it advances by guesswork, it can ’solve’ the empty grid. Still, for what it’s worth, here it is. I hope I have illuminated some useful javascript nooks along the way.
