// March 20, 2006 -- Pius Fischer
//
// Tested in the following environments:
//
// IE 6.0       (Windows 2000)          Passed
// Firefox 1.5  (Windows 2000)          Passed
// Safari 1.3.2 (Mac OS X 10.3.9)       Failed
// IE 5.2       (Mac OS X 10.3.9)       Failed
// Firefox 1.0  (Max OS X 10.3.9)       Failed
//
// The problem with all three browsers tested on the Mac is that table
// cells can't receive keyboard events (including focus and blur). So you
// can't click on a cell and enter a digit. However, the four buttons
// (Solve, Step, Clear, and Sample) all work.
//
// Safari also wouldn't let me change the nodeValue of a text node if the
// node was created with a blank string. So I created those nodes with a
// non-breaking space character (nbsp) instead. This also helps with IE
// on the Mac because it won't render the borders of a table cell if the
// cell only contains a blank string.

// Global variables
var grid;
var rowSolved;
var columnSolved;
var regionSolved;
var regionReduced;
var numToSolve;
var tbody;
var info;
var step;

// Define these so we don't have to use /, %, or *
var regionRowMap1 = new Array(0,0,0,1,1,1,2,2,2);
var regionRowMap3 = new Array(0,0,0,3,3,3,6,6,6);
var regionColumnMap1 = new Array(0,1,2,0,1,2,0,1,2);
var regionColumnMap3 = new Array(0,3,6,0,3,6,0,3,6);

var CELL_FLAG_ROW_PAIR_CHECKED          = 1;
var CELL_FLAG_COLUMN_PAIR_CHECKED       = 2;
var CELL_FLAG_REGION_PAIR_CHECKED       = 4;

var nbsp = String.fromCharCode(160);

var sampleGrid1 = new Array(
	'216000300',
	'000630000',
	'000000790',
	'740050600',
	'000060000',
	'001080024',
	'075000000',
	'000092000',
	'003000968'
);

function Cell(_row, _column)
{
	this.answer = 0;
	this.possible = new Array(10);
	for (var i = 0; i < 10; ++i)
		this.possible[i] = false;
	this.numPossible = 0;
	this.flags = 0;
	this.row = _row;
	this.column = _column;
}
function initVariables()
{
	var i, j;

	grid = new Array(9);
	rowSolved = new Array(9);
	columnSolved = new Array(9);
	regionSolved = new Array(9);
	regionReduced = new Array(9);
	for (i = 0; i < 9; ++i)
	{
		grid[i] = new Array(9);
		for (j = 0; j < 9; ++j)
			grid[i][j] = new Cell(i, j);
		rowSolved[i] = new Array(10);
		columnSolved[i] = new Array(10);
		regionSolved[i] = new Array(10);
		regionReduced[i] = new Array(10);
		for (j = 0; j < 10; ++j)
		{
			rowSolved[i][j] = false;
			columnSolved[i][j] = false;
			regionSolved[i][j] = false;
			regionReduced[i][j] = false;
		}
	}
	numToSolve = 81;
}
function setInfo(value)
{
	if (value.substr(0,1) === '#') {
		value = value.substr(1);
		info.style.color = '#0000FF';
	} else {
		value = 'ERROR: ' + value;
		info.style.color = '#FF0000';
	}
	info.firstChild.nodeValue = value;
}
function clearInfo()
{
	info.firstChild.nodeValue = ' ';
}
function setCell(row, column, answer)
{
	var cell = grid[row][column];
	var node = tbody.childNodes[row].childNodes[column];

	if (cell.answer == answer)
	{
		node.style.color = '#000000';
		return;
	}

	var region = regionRowMap3[row] + regionRowMap1[column];

	if (rowSolved[row][answer])
		throw 'Row ' + row +' already has a ' + answer + '.';
	if (columnSolved[column][answer])
		throw 'Column ' + column + ' already has a ' + answer + '.';
	if (regionSolved[region][answer])
		throw 'Region ' + region + ' already has a ' + answer + '.';

	node.title = '';
	node.style.color = '#000000';
	node.firstChild.nodeValue = answer;

	if (cell.answer == 0)
		--numToSolve;
	else
	{
		rowSolved[row][cell.answer] = false;
		columnSolved[column][cell.answer] = false;
		regionSolved[region][cell.answer] = false;
	}

	cell.answer = answer;

	rowSolved[row][answer] = true;
	columnSolved[column][answer] = true;
	regionSolved[region][answer] = true;
}
function unsetCell(row, column)
{
	var cell = grid[row][column];

	if (cell.answer == 0)
		return;

	var node = tbody.childNodes[row].childNodes[column];
	var region = regionRowMap3[row] + regionRowMap1[column];

	node.title = '';
	node.firstChild.nodeValue = nbsp;

	++numToSolve;
	rowSolved[row][cell.answer] = false;
	columnSolved[column][cell.answer] = false;
	regionSolved[region][cell.answer] = false;

	cell.answer = 0;
}
function fillGrid(_grid)
{
	try {
		clearGrid();
		for (var row = 0; row < 9; ++row)
			for (var column = 0; column < 9; ++column)
			{
				var answer = _grid[row].charAt(column);
				if (answer !== '0')
					setCell(row, column, answer);
			}
	} catch (e) {
		setInfo(e);
	}
}
function clearGrid()
{
	clearInfo();
	for (var row = 0; row < 9; ++row)
		for (var column = 0; column < 9; ++column)
			unsetCell(row, column);
}
function handleFocus(_event)
{
	var node = window.event ? window.event.srcElement : _event.target;

	node.style.backgroundColor = '#CCCCCC';
}
function handleBlur(_event)
{
	var node = window.event ? window.event.srcElement : _event.target;

	node.style.backgroundColor = '#FFFFFF';
}
function handleKeyDown(_event)
{
	var node;
	var keyCode;

	if (window.event) {
		node = window.event.srcElement;
		keyCode = window.event.keyCode;
	} else {
		node = _event.target;
		keyCode = _event.which;
	}

	switch (keyCode)
	{
		case 8: // backspace
		case 37: // left arrow
		case 38: // up arrow
		case 39: // right arrow
		case 40: // down arrow
			break;
		default:
			return;
	}

	var row = node.id.substr(2,1);
	var col = node.id.substr(3,1);

	clearInfo();

	switch (keyCode)
	{
		case 8: // backspace
			if (--col < 0)
			{
				col = 8;
				if (--row < 0)
					row = 8;
			}
			break;
		case 37: // left arrow
			if (--col < 0) col = 8;
			break;
		case 38: // up arrow
			if (--row < 0) row = 8;
			break;
		case 39: // right arrow
			if (++col == 9) col = 0;
			break;
		case 40: // down arrow
			if (++row == 9) row = 0;
			break;
	}

	if (window.event) {
		window.event.cancelBubble = true;
		window.event.returnValue = false;
	} else {
		_event.stopPropagation();
		_event.preventDefault();
	}

	tbody.childNodes[row].childNodes[col].focus();
}
function handleKeyPress(_event)
{
	var node;
	var keyCode;

	if (window.event) {
		node = window.event.srcElement;
		keyCode = window.event.keyCode;
	} else {
		node = _event.target;
		keyCode = _event.which;
		if (keyCode == 0 || keyCode == 8)
			return;
	}

	var row = node.id.substr(2,1);
	var col = node.id.substr(3,1);

	clearInfo();

	if (keyCode >= 49 && keyCode <= 57) // '1' .. '9'
	{
		try {
			setCell(row, col, String.fromCharCode(keyCode));
		} catch (e) {
			setInfo(e);
			return;
		}
	}
	else if (keyCode == 48 || keyCode == 32) // '0', ' '
	{
		unsetCell(row, col);
	}

	if (++col == 9)
	{
		col = 0;
		if (++row == 9)
			row = 0;
	}

	tbody.childNodes[row].childNodes[col].focus();
}
function init()
{
	initVariables();

	tbody = document.createElement('tbody');
	tbody.style.cursor = 'pointer';

	info = document.getElementById('info');
	info.appendChild(document.createTextNode(nbsp));

	for (var i = 0; i < 9; ++i)
	{
		var trNode = document.createElement('tr');
		for (var j = 0; j < 9; ++j)
		{
			var cell = document.createElement('td');

			cell.id = 'td' + i + j;
			cell.tabIndex = 1;
			cell.onblur = handleBlur;
			cell.onfocus = handleFocus;
			cell.onkeydown = handleKeyDown;
			cell.onkeypress = handleKeyPress;

			var rowMod3 = i % 3;
			var colMod3 = j % 3;
			if (rowMod3 == 0)
				cell.style.borderTopWidth = '2px';
			else if (rowMod3 == 2)
				cell.style.borderBottomWidth = '2px';
			if (colMod3 == 0)
				cell.style.borderLeftWidth = '2px';
			else if (colMod3 == 2)
				cell.style.borderRightWidth = '2px';

			cell.appendChild(document.createTextNode(nbsp));
			trNode.appendChild(cell);
		}
		tbody.appendChild(trNode);
	}

	var tableNode = document.createElement('table');
	tableNode.cellPadding = 0;
	tableNode.cellSpacing = 0;
	tableNode.style.borderCollapse = 'collapse';
	tableNode.appendChild(tbody);

	document.getElementById('grid').appendChild(tableNode);
}
function solveCell(_cell, _answer, _reason)
{
	var row = _cell.row;
	var column = _cell.column;

	var node = tbody.childNodes[row].childNodes[column];
	var region = regionRowMap3[row] + regionRowMap1[column];

	if (rowSolved[row][_answer]
		|| columnSolved[column][_answer]
		|| regionSolved[region][_answer])
	{
		node.focus();
		throw 'Cell [' + row + ',' + column +
			'] has no possible answer.';
	}

	_cell.answer = _answer;
	--numToSolve;

	node.title = '';
	node.style.color = '#0000FF';
	node.firstChild.nodeValue = _answer;

	rowSolved[row][_answer] = true;
	columnSolved[column][_answer] = true;
	regionSolved[region][_answer] = true;

	if (step)
	{
		node.focus();
		throw '#' + _reason;
	}

	updateRow(row, column, _answer);
	updateColumn(row, column, _answer);
	updateRegion(row, column, _answer);
}
function updateCell(_cell, _reason)
{
	var answer;

	for (answer = 1; answer <= 9; ++answer)
		if (_cell.possible[answer])
			break;

	solveCell(_cell, answer,
		'The only possibility remaining for cell [' +
		_cell.row + ',' + _cell.column + '] is a ' +
		answer + '.');
}
function updateRow(_row, _column, _answer)
{
	for (var column = 0; column < 9; ++column)
	{
		if (column == _column)
			continue;

		var cell = grid[_row][column];

		if (cell.answer || !cell.possible[_answer])
			continue;

		cell.possible[_answer] = 0;

		if (--(cell.numPossible) == 1)
			updateCell(cell, ' ');
	}
}
function updateColumn(_row, _column, _answer)
{
	for (var row = 0; row < 9; ++row)
	{
		if (row == _row)
			continue;

		var cell = grid[row][_column];

		if (cell.answer || !cell.possible[_answer])
			continue;

		cell.possible[_answer] = 0;

		if (--(cell.numPossible) == 1)
			updateCell(cell, ' ');
	}
}
function updateRegion(_row, _column, _answer)
{
	var rowBase = regionRowMap3[_row];
	var columnBase = regionRowMap3[_column];

	for (var i = 0; i < 9; ++i)
	{
		var row = rowBase + regionRowMap1[i];
		var column = columnBase + regionColumnMap1[i];

		if (row == _row && column == _column)
			continue;

		var cell = grid[row][column];

		if (cell.answer || !cell.possible[_answer])
			continue;

		cell.possible[_answer] = 0;

		if (--(cell.numPossible) == 1)
			updateCell(cell, ' ');
	}
}
function solveRow(_row, _answer)
{
	var numPossible = 0;
	var firstCell;

	for (var column = 0; column < 9; ++column)
		if (!grid[_row][column].answer &&
			grid[_row][column].possible[_answer])
			if (++numPossible == 1)
				firstCell = grid[_row][column];
			else
				break;
	if (numPossible == 0)
		throw 'Row ' + _row + ' cannot have a ' + _answer + '.';
	if (numPossible == 1)
		solveCell(firstCell, _answer,
			'The only possibility for a ' + _answer +
			' in row ' + _row + ' is cell [' +
			firstCell.row + ',' + firstCell.column + ']');
}
function solveColumn(_column, _answer)
{
	var numPossible = 0;
	var firstCell;

	for (var row = 0; row < 9; ++row)
		if (!grid[row][_column].answer &&
			grid[row][_column].possible[_answer])
			if (++numPossible == 1)
				firstCell = grid[row][_column];
			else
				break;
	if (numPossible == 0)
		throw 'Column ' + _column + ' cannot have a ' + _answer + '.';
	if (numPossible == 1)
		solveCell(firstCell, _answer,
			'The only possibility for a ' + _answer +
			' in column ' + _column + ' is cell [' +
			firstCell.row + ',' + firstCell.column + ']');
}
function solveRegion(_region, _answer)
{
	var numPossible = 0;
	var firstCell;

	var rowBase = regionRowMap3[_region];
	var columnBase = regionColumnMap3[_region];

	for (var i = 0; i < 9; ++i)
	{
		var row = rowBase + regionRowMap1[i];
		var column = columnBase + regionColumnMap1[i];

		if (!grid[row][column].answer &&
			grid[row][column].possible[_answer])
			if (++numPossible == 1)
				firstCell = grid[row][column];
			else
				break;
	}

	if (numPossible == 0)
		throw 'Region ' + _region + ' cannot have a ' + _answer + '.';
	if (numPossible == 1)
		solveCell(firstCell, _answer,
			'The only possibility for a ' + _answer +
			' in region ' + _region + ' is cell [' +
			firstCell.row + ',' + firstCell.column + ']');
}
function solveAll()
{
	for (var i = 0; i < 9; ++i)
		for (var answer = 1; answer <= 9; ++answer)
		{
			if (!rowSolved[i][answer])
				solveRow(i, answer);

			if (!columnSolved[i][answer])
				solveColumn(i, answer);

			if (!regionSolved[i][answer])
				solveRegion(i, answer);
		}
}
function getRow(row, i)
{
	return grid[row][i];
}
function getColumn(column, i)
{
	return grid[i][column];
}
function getRegion(region, i)
{
	return grid[regionRowMap3[region] + regionRowMap1[i]]
			[regionColumnMap3[region] + regionColumnMap1[i]];
}
function checkSetForPairs(_scope, _flag, _getCell)
{
	var i, j;
	var answer;
	var cell1;
	var cell2;

	for (i = 0; i < 8; ++i)
	{
		cell1 = _getCell(_scope, i);
		if (cell1.answer || cell1.numPossible != 2
			|| (cell1.flags & _flag))
			continue;

		cell1.flags |= _flag;

		for (j = i + 1; j < 9; ++j)
		{
			cell2 = _getCell(_scope, j);
			if (cell2.answer || cell2.numPossible != 2)
				continue;
			for (answer = 1; answer <= 9; ++answer)
				if (cell1.possible[answer] !=
					cell2.possible[answer])
					break;
			if (answer == 10)
				break;
		}
		if (j == 9)
			continue;

		cell2.flags |= _flag;

		for (answer = 1; answer <= 9; ++answer)
		{
			if (!cell1.possible[answer])
				continue;
			for (j = 0; j < 9; ++j)
			{
				var cell = _getCell(_scope, j);
				if (cell.answer || !cell.possible[answer]
					|| cell == cell1 || cell == cell2)
					continue;
				cell.possible[answer] = 0;
				if (--(cell.numPossible) == 1)
					updateCell(cell, ' ');
			}
		}
	}
}
function checkForPairs()
{
	for (var i = 0; i < 9; ++i)
	{
		checkSetForPairs(i, CELL_FLAG_ROW_PAIR_CHECKED, getRow);
		checkSetForPairs(i, CELL_FLAG_COLUMN_PAIR_CHECKED, getColumn);
		checkSetForPairs(i, CELL_FLAG_REGION_PAIR_CHECKED, getRegion);
	}
}
function fillPossible()
{
	var region;
	var answer;
	var firstAnswer;

	for (var row = 0; row < 9; ++row)
		for (var column = 0; column < 9; ++column)
		{
			var cell = grid[row][column];

			if (cell.answer != 0)
				continue;

			cell.flags = 0;
			cell.numPossible = 0;

			region = regionRowMap3[row] + regionRowMap1[column];

			for (answer = 1; answer <= 9; ++answer)
				if (!rowSolved[row][answer]
					&&
					!columnSolved[column][answer]
					&&
					!regionSolved[region][answer])
				{
					cell.possible[answer] = true;
					if (++(cell.numPossible) == 1)
						firstAnswer = answer;
				}
				else
					cell.possible[answer] = false;

			if (cell.numPossible == 0)
				throw 'Cell [' + row + ',' + column +
					'] has no possible answer.';
			if (cell.numPossible == 1)
				solveCell(cell, firstAnswer,
					'The only possibility for cell [' +
					row + ',' + column + '] is a ' +
					firstAnswer + '.');
		}
}
function showPossible()
{
	for (var row = 0; row < 9; ++row)
		for (var column = 0; column < 9; ++column)
		{
			var cell = grid[row][column];
			if (cell.answer)
				continue;

			var title = '';
			for (var answer = 1; answer <= 9; ++answer)
				if (cell.possible[answer])
				{
					if (title)
						title += ', ';
					title += answer;
				}

			tbody.childNodes[row].childNodes[column].title = title;
		}
}
function solve(_step)
{
	step = _step;
	try {
		fillPossible();

		while (numToSolve)
		{
			var savedNumToSolve = numToSolve;

			solveAll();
			if (numToSolve == 0)
				break;

			checkForPairs();

			if (numToSolve == savedNumToSolve)
				break;
		}

		if (numToSolve)
			showPossible();

		clearInfo();
	} catch (e) {
		setInfo(e);
	}
}