/* Script to drive a Su Doku puzzle solver. -*- Mode: c++; c-basic-offset: 4; -*-
 *
 * $Id: sudoku.js,v 1.12 2010-05-23 22:07:30 eddy Exp $
 */

/* TODO: fix it so we can fix typos during set-up of givens.
 *
 * Change the pending-ness of events so that a cell gets set promptly but its
 * new value only gets to affect the rest of the world when we flush().  We can
 * still check whether it conflicts with anything by asking its .row, .col and
 * .tile whether they have the given entry.  Then we can support a delete
 * operation on a marked cell during set-up.
 */

/* TODO: write tools for the reverse problem - automate identifying which cells
 * in a partially-filled grid can be cleared without adding ambiguity.
 */
/* TODO: let the user specify "I know this cell is not d".
 */
/* TODO: a better UI might be to let the user input random (non-forbidden) crap
 * and hit return to do inference; don't do it otherwise.  Requires that filling
 * a cell do necessary forbidding on its peers.  May require proto-inference: if
 * a cell is left with only one non-forbidden value, it claims it, but we do no
 * further scrutiny.  Hitting return does scrutiny.
 */
/* TODO: symbolic markings - allow letters in place of numbers, each letter
 * understood as being consistently used to stand for *some* number; track which
 * numbers that can't be.  Open choice, perhaps as toggle on form: whether or
 * not to assume distinct letters are distinct numbers.
 */

function classLogger() {
    function Logger(ul) {
	this.parent = ul;
	this.current = null;
	if (opera && opera.postError)
	    this.debug = opera.postError;
    }
    Logger.prototype = {

	'newNode': function (klaz) {
	    var node = document.createElement("li");
	    if (klaz) node.className = klaz;
	    this.parent.insertBefore(node, this.parent.firstChild);
	    this.detail = null;
	    return node;
	},

	'report': function (message, klaz) {
	    this.current = this.newNode(klaz);
	    this.current.appendChild(document.createTextNode(message));
	},

	'done': function () { this.current = null; },

	'append': function (message, klaz) {
	    if (! this.current)
		this.current = this.newNode('');

	    var node = document.createElement("li");
	    if (this.detail) {
		this.detail.insertBefore(node, this.detail.firstChild);
	    } else {
		this.detail = document.createElement("ul");
		this.current.appendChild(this.detail);
		this.detail.appendChild(node);
	    }

	    if (klaz) node.className = klaz;
	    node.appendChild(document.createTextNode(message));
	},

	'debug': function (message) {
	    this.report(message, 'debug');
	}
    }
    return Logger;
}

function classCell() {
    function Cell(grid, td, a, d) {
	this.grid = grid;
	this.ent = td;
	this.across = a;
	this.down = d;
	this.row = grid.row[d];
	this.col = grid.col[a];
	this.tile = grid.tile[(a - (a % 3)) / 3][(d - (d % 3)) / 3];
	this.tdclick = td.onclick = function () { grid.select(a, d); }
	this.maybe = [, 1, 2, 3, 4, 5, 6, 7, 8, 9];
	this.flags = 0; // |-ed together State flags, see prototype
    }
    Cell.prototype = {
	'errorState': 1, 'liveState': 2, 'focusState': 4,
	'tryState': 8, 'givenState': 16, 'inferState': 32,

	'copy': function (grid) {
	    if (this.maybe[0]) return this;
	    var ans = new Cell(grid, this.ent, this.across, this.down);
	    for (var i = 1; i < 10; i++)
		if (!this.maybe[i])
		    delete ans.maybe[i];

	    if (this.maybe[0])
		ans.maybe[0] = this.maybe[0];

	    ans.flags = this.flags;
	    return ans;
	},

	'restore': function () {
	    this.ent.onclick = this.tdclick;
	    this.ent.title = "" + this.maybe;
	    this.setClass();
	    if (!this.maybe[0] && this.ent.firstChild)
		this.ent.firstChild.data = '';
	},

	'setClass': function () {
	    if (!this.flags) this.ent.className = '';
	    else {
		var name = "";

		if (this.flags & this.errorState) name = "error";
		else if (this.flags & this.liveState) name = "live";
		else if (this.flags & this.focusState) name = "focal";

		var frag;
		if (this.flags & this.givenState) frag = "given";
		else if (this.flags & this.tryState) frag = "try";
		if (frag)
		    if (name) name = name + " " + frag;
		    else name = frag;

		this.ent.className = name;
	    }
	},

	'select': function () {
	    if (this.maybe[0] &&
		((this.flags & this.inferState) || this.grid.TryClass)) {
		this.flags |= this.focusState;
		this.setClass();
		return this.grid.TryClass ? false : true;
	    }
	    this.flags |= this.liveState;
	    this.setClass();
	    return true;
	},

	'unselect': function () {
	    this.flags &= ~(this.liveState | this.focusState);
	    this.setClass();
	},

	'set': function (entry) {
	    if (entry) logger.report("Setting " + entry + this);
	    if (this.maybe[0]) {
		var ans = !entry || entry == this.maybe[0];
		if (entry &&
		    (this.flags & this.inferState) &&
		    ! this.grid.TryGrid) {
		    this.flags |= ans ? this.givenState : this.errorState;
		    this.setClass();
		} else
		    logger.append("Can't reset cell - type back-space " +
				  "to back out of latest input");
		return ans;
	    }

	    var flag = entry ? ( this.grid.TryGrid ?
				 this.tryState :
				 this.givenState ) : this.inferState;
	    for (var i in this.grid.solved)
		if (this.grid.solved[i] == this)
		    delete this.grid.solved[i];

	    if (!entry) {
		for (var i = 1; i < 10; i++) {
		    if (this.maybe[i]) {
			if (entry) {
			    logger.append("ambiguous " + entry +
					  ", " + i + this);
			    return false;
			}
			entry = i;
		    }
		}
	    } else if (! this.maybe[entry]) {
		logger.append("invalid " + entry + this);;
		return false;
	    }

	    if (entry) {
		if (this.row.blocks(entry, this) ||
		    this.col.blocks(entry, this) ||
		    this.tile.blocks(entry, this)) {
		    logger.append("Contention: " + entry + this);
		    return false;
		}

		this.row.claim(entry, this);
		this.col.claim(entry, this);
		this.tile.claim(entry, this);
		this.maybe[0] = entry;
		for (var i = 1; i < 10; i++)
		    if (i != entry && this.maybe[i])
			delete this.maybe[i];

		delete this.ent.title;

		if (this.ent.firstChild)
		    this.ent.firstChild.data = '' + entry;
		else
		    this.ent.appendChild(document.createTextNode('' + entry));
	    } else {
		flag = this.errorState;
		this.fail("Undetermined state to set()");
	    }

	    this.flags |= flag;
	    if (flag == this.inferState)
		logger.append("Set " + entry + this);
	    else {
		this.setClass();
		logger.done();
	    }
	    return true;
	},

	'count': function () {
	    if (this.maybe[0]) return 1;
	    var count = 0;
	    for (var i = 1; i < 10; i++)
		if (this.maybe[i])
		    count++;
	    return count;
	},

	'toString': function () {
	    return " @(" + this.across + ", " + this.down + ")";
	},

	'fail': function (message) {
	    this.flags |= this.errorState;
	    this.setClass();
	    if (message) logger.append(message + " " + this);
	    else logger.append("Failing " + this);
	    this.grid.fail();
	},

	'forbid': function (entry) {
	    // Notice that this can't take value entry
	    if (this.maybe[entry]) {
		if (this.maybe[0]) {
		    this.fail("Can't forbid(" + entry +
			      ") given " + this.maybe[0]);
		    return false;
		}
		delete this.maybe[entry];
		this.ent.title = "" + this.maybe;
		var count = 0, found;
		for (var i = 1; i < 10; i++) {
		    if (this.maybe[i]) {
			count++;
			found = i;
		    }
		}
		if (count < 1) {
		    this.fail("Forbade only candidate, " + entry);
		} else if (count < 2) {
		    if (this.grid.queue(this))
			logger.append("Forbade " + entry + this +
				      ", making it " + found);
		}
		return true;
	    }
	    return false;
	}
    }
    return Cell;
}

function classRack() {
    function Rack() {}
    Rack.prototype = {
	/* Each derived class must also implement method:
	 * entry(i) -> a cell, for i from 0 to 8
	 */

	'init': function (grid) {
	    this.grid = grid;
	    this.todo = [, 1, 2, 3, 4, 5, 6, 7, 8, 9];
	},

	'candidates': function (entry) {
	    // list of cells in this that might take value entry
	    maybe = [];
	    for (var i = 0; i < 9; i++) {
		var cell = this.entry(i);
		if (cell.maybe[entry])
		    maybe[maybe.length] = cell;
	    }
	    return maybe;
	},

	'blocks': function (entry, cell) {
	    if (! this.todo[entry]) return cell;
	    for (var i = 0; i < 9; i++) {
		var it = this.entry(i);
		if (it != cell && it.maybe[entry]) {
		    var free = 0;
		    for (var j = 1; j < 10; j++) {
			if (it.maybe[j]) free++;
		    }
		    if (free < 2) return it;
		}
	    }
	    return null;
	},

	'claim': function (entry, cell) {
	    for (var i = 0; i < 9; i++) {
		var it = this.entry(i);
		if (it != cell)
		    it.forbid(entry);
	    }
	    delete this.todo[entry];
	},

	'restrict': function (entry, allow) {
	    /* Like claim, but exempting a list of cells allowed to be
	     * the entry */
	    var count = 0;
	    for (var i = 0; i < 9; i++) {
		var cell = this.entry(i);
		var bad = cell.maybe[entry];
		if (bad)
		    for (var j in allow)
			if (allow[j] == cell) {
			    bad = false;
			    break;
			}
		if (bad) {
		    if (cell.forbid(entry))
			count++;
		}
	    }
	    return count;
	},

	'knows': function (entry) {
	    for (var i = 0; i < 9; i++) {
		var it = this.entry(i);
		if (it.maybe[0] == entry)
		    return it;
	    }
	    return null;
	},

	'regionName': function () {
	    /* Over-ridden by each derived class, but this is a handy
	     * default anyway. */
	    var start = this.entry(0), end = this.entry(8);
	    return ("("  + start.across + "-" + end.across +
		    ", " + start.down   + "-" + end.down + ")");
	},

	'scrutinise': function () {
	    // See if we can infer anything useful:
	    var progress = false;
	    for (var i = 1; i < 10; i++) {
		var can = this.candidates(i);
		if (can.length == 1) {
		    var cell = can[0];
		    if (! cell.maybe[0]) {
			for (var j in cell.maybe)
			    if (j != i)
				delete cell.maybe[j];

			if (this.grid.queue(cell))
			    logger.append("In " + this + ": " + i +
					  " can only be" + cell);
			progress = true;
		    }
		} else if (can.length < 1) {
		    logger.append("No candidate for " + i + " in " + this);
		    this.grid.fail();
		} else if (this.crossCheck(i, can))
		    progress = true;
	    }
	    if (this.partition()) progress = true;
	    return progress;
	},

	'partition': function() {
	    // attempt sub-set analysis
	    var progress = false;
	    var open = []; // unresolved cells
	    for (var i = 0; i < 9; i++) {
		var cell = this.entry(i);
		if (cell.count() > 1)
		    open[open.length] = cell;
	    }
	    // iterate over proper subsets of open:
	    for (var s = (1 << open.length) - 2; s > 1; s--) {
		var ss = []; // a proper subset of open
		for (var i in open)
		    if ((s & (1<<i)) != 0)
			ss[ss.length] = open[i];
		/* A singleton partition would have been handled
		 * already because its .candidates().length == 1. */
		if (ss.length > 1) {
		    // set of digits that may appear in any of ss's cells:
		    var maybe = [];
		    for (var i in ss)
			for (var j = 1; j < 10; j++)
			    if (ss[i].maybe[j])
				maybe[j] = j;
		    var count = 0;
		    for (var j = 1; j < 10; j++)
			if (maybe[j]) count++;
		    if (count == ss.length) {
			// partition !
			var care = false;
			// complement of ss can't use maybe's entries
			for (var i in open)
			    if (!(s & (1<<i))) // cell not in ss
				for (var j = 1; j < 10; j++)
				    if (maybe[j])
					if (open[i].forbid(j))
					    care = true;
			if (care) {
			    logger.append("Partitioned (" + maybe +
					  ") in (" + ss + ") of " + this);
			    progress = true;
			}
		    } else if (count < ss.length) {
			// broken !
			logger.append("Too few candidates (" + maybe +
				      ") for cells (" + ss + ") in " + this);
			this.grid.fail();
		    }
		}
	    }
	    return progress;
	},

	// Tile over-rides this, but Row and Col share this version:
	'crossCheck': function (i, can) {
	    var tile = null;
	    for (var j in can) {
		if (tile) {
		    if (can[j].tile != tile) return false;
		} else
		    tile = can[j].tile;
	    }
	    if (tile) { // the only tile within which this lets i appear
		if (tile.restrict(i, can)) {
		    logger.append("Cross-checking " + i +
				  " in " + this + " restricted " + tile);
		    return true;
		}
	    } else logger.debug("Tile check with no cells ! " + can);
	    return false;
	}
    }
    return Rack;
}

function classRow(Rack) {
    function Row(grid, tr, d) {
	this.init(grid);
	this.ent = tr;
	this.down = d;
    }
    Row.prototype = new Rack;

    Row.prototype.toString = function () {
	return "row " + this.down;
    }

    Row.prototype.entry = function (i) {
	return this.grid.cell[i][this.down];
    }

    return Row;
}

function classCol(Rack) {
    function Col(grid, a) {
	this.init(grid);
	this.across = a;
    }
    Col.prototype = new Rack;

    Col.prototype.toString = function () {
	return "column " + this.across;
    }
    Col.prototype.entry = function (i) {
	return this.grid.cell[this.across][i];
    }

    return Col;
}

function classTile(Rack) {
    function Tile(grid, a, d) {
	this.init(grid);
	this.across = 3 * a;
	this.down = 3 * d;
    }
    Tile.prototype = new Rack;

    Tile.prototype.toString = function () {
	if (this.across == 3 && this.down == 3) return "centre tile";
	var across, down;
	switch (this.across) {
	case 0: across = "left"; break;
	case 3: across = "mid"; break;
	default: logger.debug("Saw tile with across = " + this.across);
	case 6: across = "right"; break;
	}
	switch (this.down) {
	case 0: down = "top"; break;
	case 3: down = "mid"; break;
	default: logger.debug("Saw tile with down = " + this.down);
	case 6: down = "bottom"; break;
	}
	return down + " " + across + " tile";
    }

    Tile.prototype.entry = function (i) {
	var a = i % 3;
	var d = (i - a) / 3;
	return this.grid.cell[this.across + a][this.down + d];
    }

    Tile.prototype.colCheck = function (i, can) {
	var col = null;
	for (var j in can) {
	    if (!col)
		col = can[j].col;
	    else if (col != can[j].col)
		return false;
	}
	if (col) { // the only column in which this lets i appear
	    if (col.restrict(i, can)) {
		logger.append("Cross-checking " + i +
			      " in " + this + " restricted " + col);
		return true;
	    }
	} else logger.debug("Column check with no cells ! " + can);
	return false;
    }

    Tile.prototype.rowCheck = function (i, can) {
	var row = null;
	for (var j in can) {
	    if (!row)
		row = can[j].row;
	    else if (row != can[j].row)
		return false;
	}
	if (row) { // the only row in which this lets i appear
	    if (row.restrict(i, can)) {
		logger.append("Cross-checking " + i +
			      " in " + this + " restricted " + row);
		return true;
	    }
	} else logger.debug("Row check with no cells ! " + can);
	return false;
    }

    Tile.prototype.crossCheck = function (i, can) {
	var ans = false;
	if (this.rowCheck(i, can)) ans = true;
	if (this.colCheck(i, can)) ans = true;
	return ans;
    }

    return Tile;
}

function classBaseGrid() {
    function BaseGrid () {
	var Rack = classRack();
	this.Row = classRow(Rack);
	this.Col = classCol(Rack);
	this.Tile = classTile(Rack);
	this.Cell = classCell();
    }
    BaseGrid.prototype = {
	'TryGrid': null,

	'init': function (tbody) {
	    this.ent = tbody;
	    this.solved = [];
	    this.failed = false;
	    this.rackinit(tbody.childNodes);
	},

	'toString': function () { return 'BaseGrid()'; },

	'rackinit': function (trs) {
	    this.cell = [];
	    this.tile = [];
	    this.row = [];
	    this.col = [];
	    for (var i = 0; i < 9; i++) {
		this.cell[i] = [];
		this.row[i] = new this.Row(this, trs[i], i);
		this.col[i] = new this.Col(this, i);
		if (i < 3)
		    this.tile[i] = [ new this.Tile(this, i, 0),
				     new this.Tile(this, i, 1),
				     new this.Tile(this, i, 2) ];
	    }
	    this.cellinit(trs); // define in each derived class
	},

	'queue': function (cell) {
	    for (var j in this.solved)
		if (this.solved[j] == cell)
		    return false;

	    var i = 0;
	    while (this.solved[i]) i++;
	    this.solved[i] = cell;
	    return true;
	},

	'flush': function (message) {
	    var change = 1; // to ensure first time round happens
	    if (message) {
		logger.report(message);
		logger.append("Flushing");
	    } else
		logger.report("Flushing");

	    while (change && !this.failed) {
		change = 0;

		for (var i in this.row)
		    this.row[i].scrutinise();
		for (var i in this.col)
		    this.col[i].scrutinise();
		for (var i in this.tile)
		    for (var j in this.tile[i])
			this.tile[i][j].scrutinise();

		while (this.solved.length > 0 && !this.failed) {
		    var j = 0, seq = [], cell = null;
		    for (var i in this.solved) {
			var it = this.solved[i];
			if (cell) seq[j++] = it;
			else cell = it;
		    }
		    logger.append("Inference" + cell +
				  ", pending " + seq.length + " more");
		    this.solved = seq;
		    if (! cell.set()) {
			logger.append("Failed to set" + cell);
			this.fail();
			return false;
		    }
		    change++;
		}
	    }
	    logger.done();
	    return !this.failed;
	},

	'restore': function (message) {
	    for (var i in this.cell)
		for (var j in this.cell[i])
		    this.cell[i][j].restore();

	    this.editable = this.live.select();
	    this.flush(message);
	},

	'select': function (a, d) {
	    if (this.live) {
		if (this.live.across == a && this.live.down == d)
		    return;
		this.live.unselect();
	    }
	    this.live = this.cell[a][d];
	    this.editable = this.live.select();
	},

	'keyPress': function (key) {
	    if (48 < key && key < 58) { // positive digit
		if (!this.editable) {
		    logger.append("Non-editable cell" + this.live);
		} else if (this.TryGrid) {
		    var digit = key - 48;
		    solver = new this.TryGrid(digit, this);
		    while (solver.failed && solver.prior)
			solver = solver.undo();
		} else {
		    this.live.set(key - 48);
		}
	    } else {
		switch (key) {
		case 85: case 117: /* U, u for "undo" */
		case  8: /* Back-space */ solver = this.undo(); break;
		case  9: /* Tab */	this.next(); break;
		case 13: /* Return */ this.freeze(); break;
		case 37: /* Left */
		if (this.live.across > 0)
		    this.select(this.live.across - 1, this.live.down);
		break;
		case 38: /* Up */
		if (this.live.down > 0)
		    this.select(this.live.across, this.live.down - 1);
		break;
		case 39: /* Right */
		if (this.live.across < 8)
		    this.select(this.live.across + 1, this.live.down);
		break;
		case 40: /* Down */
		if (this.live.down < 8)
		    this.select(this.live.across, this.live.down + 1);
		break;
		// Let someone else handle any other key-presses:
		default: return false;
		}
	    }
	    return true;
	},

	'next': function () {
	    if (this.live.across < 8)
		this.select(this.live.across + 1, this.live.down);
	    else if (this.live.down < 8)
		this.select(0, this.live.down + 1);
	    else
		this.select(0, 0);
	},

	'freeze': function () {
	    BaseGrid.prototype.TryGrid = classTryGrid(new BaseGrid);
	    this.flush("Froze marked inputs as givens");
	    BaseGrid.prototype.freeze = function () {
		logger.report("Grid is already frozen, " +
			      "givens are already fixed");
		logger.done();
	    }
	}
    }
    return BaseGrid;
}

function classTryGrid(proto) {
    function TryGrid(digit, grid) {
	this.prior = grid;
	this.digit = digit;
	this.init(grid.ent);
	grid.live.unselect();
	this.select(grid.live.across, grid.live.down);
	this.flush("Pushed " + digit + grid.live + " onto stack.");
    }
    TryGrid.prototype = proto;

    TryGrid.prototype.toString = function () {
	return "TryGrid(" + this.digit + ", " + this.prior + ")";
    }

    TryGrid.prototype.cellinit = function (trs) {
	for (var i = 0; i < 9; i++)
	    for (var j = 0; j < 9; j++)
		this.cell[j][i] = this.prior.cell[j][i].copy(this);

	var prior = this.prior.live;
	if (!prior) logger.debug("No prior cell !");
	var cell = this.cell[prior.across][prior.down];
	if (cell == prior)
	    logger.debug("TryGrid sharing live cell with prior");
	cell.set(this.digit);
    }

    TryGrid.prototype.undo = function () {
	this.prior.restore("Undoing " + this.digit + this.prior.live);
	logger.done();
	return this.prior;
    }

    TryGrid.prototype.fail = function () {
	logger.append("Failed: I'll forbid " +
		      this.digit + this.prior.live);
	this.prior.live.forbid(this.digit);
	this.failed = true;
    }

    return TryGrid;
}

function classGivenGrid() {
    function GivenGrid(tbody) {
	this.prior = null;
	this.init(tbody);
	this.select(4, 4);
    }
    var BaseGrid = classBaseGrid();
    GivenGrid.prototype = new BaseGrid;

    GivenGrid.prototype.toString = function () { return "GivenGrid()"; }
    GivenGrid.prototype.cellinit = function (trs) {
	// TODO skip textNodes found in the course of this
	var Cell = this.Cell;
	for (var i = 0; i < 9; i++) {
	    var tds = trs[i].childNodes;
	    for (var j = 0; j < 9; j++)
		this.cell[j][i] = new Cell(this, tds[j], j, i);
	}
    }

    GivenGrid.prototype.undo = function () {
	logger.append("Can't back-up past givens");
	return this;
    }

    GivenGrid.prototype.fail = function () {
	logger.append("Impossible !");
	this.failed = true;
    }

    return GivenGrid;
}

/* Globals: */
var solver;
var logger;

var eventKey = document.layers ? 1 : document.all ?
    2 : document.getElementById ? 2 : 0;
function keyPress(event) {
    return ! solver.keyPress(eventKey == 1 ? event.which :
			     eventKey > 1 ? event.keyCode : 0);
}

function Initialize() {
    var Log = classLogger();
    logger = new Log(document.getElementById("log"));
    var table = document.getElementById("solver");
    table.parentNode.className = ''; // turn off .noscript
    var Grid = classGivenGrid();
    solver = new Grid(table.firstChild);
}