var Cells = new Array(82);
var Sets = new Array(28);
var numCellsSet = 0;
var solvedFlag = false;
var allowScreenUpdate = true;
var badSolution = false;
var numCount = new Array(10);


function DisplayNumCellsSet()
{
	//document.getElementById('numCellsDisplay').innerHTML = numCellsSet + '/81';
}



function DrawCell()
{
	if (!allowScreenUpdate)
		return;
	if (this.locked)
	{
		this.htmlElement.style.backgroundColor = '#b1b679';
		this.htmlElement.style.cursor = 'default';
	}
	else
	{
		this.htmlElement.style.backgroundColor = (this.highlight) ? '#cbd17d' : '#bbc16f';
		this.htmlElement.style.cursor = 'hand';
	}
	this.htmlElement.innerHTML = (this.value) ? this.value : ' ';
}




function Cell(htmlElementId)
{
	var obj = new Object();
	obj.locked = false;
	obj.highlight = false;
	obj.value = 0;
 	obj.sets = new Array(4);
        obj.numSets = 0;
	obj.flashing = false;
	obj.flashCount = 0;
	obj.flashHandle = 0;
        obj.htmlElement = document.getElementById(htmlElementId);
	obj.htmlElement.cell = obj;
	obj.Redraw = DrawCell;
	obj.cellNumber = htmlElementId;
	obj.IncrementValue = function(){this.SetValue((this.value + 1) % 10);}
	obj.Highlight = function(){this.highlight = true; this.Redraw();}
	obj.DeHighlight = function(){this.highlight = false; this.Redraw();}
	obj.Clear = function(){this.locked = false; this.highlight = false; this.SetValue(0);}
	obj.Lock = function(){this.locked = true; this.Redraw();}
	obj.UnLock = function(){this.locked = false; this.Redraw();}
	obj.Blink = function()
	{
		if (this.flashCount > 9)
		{
			this.flashCount = 0;
			return;
		}
		var h = this.htmlElement;
		if (++this.flashCount & 1)
		{
			h.style.borderColor = '#ff0000';
			h.style.borderWidth = '2px';
			h.style.width = '38px';
		}
		else
		{
			h.style.borderWidth = '1px;';
			h.style.borderColor = '#a6ac57';
			h.style.width = '40px';
		}
		window.setTimeout('Cells['+this.cellNumber+'].Blink();', 100);
	}
	obj.SetValue = function(value)
	{
		if (!this.locked)
		{
			if ((value == 0) && (this.value != 0))
				numCellsSet--;
			if ((value != 0) && (this.value == 0))
				numCellsSet++;
			numCount[this.value]--;
			numCount[value]++;
			DisplayNumCellsSet();
			if (this.value)
				for (var i = 1; i < 4; i++)
					this.sets[i].Include(this.value);
			if (value)
				for (var i = 1; i < 4; i++)
					this.sets[i].Exclude(value);
			this.value = value; 
			this.Redraw();
		}
	}
	obj.NumOptions = function()
	{
		var numOptions = 0;
		for (var n = 1; n < 10; n++)
		{
			var isOption = 1;
			for (var i = 1; i < 4; i++)
			{
				var set = this.sets[i];
				if (!set.Contains(n))
					isOption = 0;
			}
			if (isOption)
				numOptions++;
		}
		return numOptions;
	}

	obj.IsOption = function(value)
	{
		for (var i = 1; i < 4; i++)
		{
			var set = this.sets[i];
			if (!set.Contains(value))
				return false;
		}
		return true;		
	}

	obj.GetFirstOption = function()
	{
		for (var n = 1; n < 10; n++)
			if (this.IsOption(n))
				return n;
		return 0;
	}

	obj.AssociateWithSet = function(setID)
	{
		this.sets[++this.numSets] = Sets[setID]; 
		Sets[setID].AssociateWithCell(this);
	}
	return obj;
}




function Set()
{
	var obj = new Object();
	obj.valueCount = new Array(10);
	obj.ValueToBit = function(value){return (1 << (value - 1));}
	obj.value = 511;
	obj.associatedCells = new Array(10);
	obj.numAssociatedCells = 0;
	obj.count = 0;

	for (var i = 1; i < 10; i++)
		obj.valueCount[i] = 0;

	obj.Exclude = function(value)
	{	
		var b = this.ValueToBit(value); 
		this.value &= ~b;
		this.valueCount[value]++;
		this.count--;
		if ((b == 0) && (count < 9))
			badSolution = true;
	}
	obj.Include = function(value)
	{
		this.valueCount[value]--;
		if (this.valueCount[value] == 0)
		{
			var b = this.ValueToBit(value); 
			this.value |= b;
			this.count++;
		}
	}
	obj.NumFreeCells = function(){var n = 0; for (var i = 1; i <= this.numAssociatedCells; i++) if (this.associatedCells[i].value == 0) n++; return n;}
	obj.AssociateWithCell = function(cell){this.associatedCells[++this.numAssociatedCells] = cell;}
	obj.Contains = function(value){var b = this.ValueToBit(value); return ((this.value & b) == b);}
	obj.Clear = function()
	{
		this.value = 511; 
		for (var i = 1; i < 10; i++) 
			this.valueCount[i] = 0;	
		this.count = 0;
	}
	obj.IsValid = function(){for (var i = 1; i < 10; i++) if (this.valueCount[i] > 1) return false; return true;}
	obj.FindCellWithOneOption = function(autoSelect)
	{
		for (var num = 1; num < 10; num++)
		{
			var c = 0;
			var cell = 0;
			for (var i = 1; i <= this.numAssociatedCells; i++)
				if ((this.associatedCells[i].value == 0) && (this.associatedCells[i].IsOption(num)))
				{
					c++;
					cell = this.associatedCells[i];
				}
			if (c == 1)
			{
				if (autoSelect)
					cell.SetValue(num);
				return cell;
			}
		}
		return 0;		
	}

	return obj;
}







function CreateBoard()
{
	// Create the HTML objects needed to show the sudoku board.
	document.writeln('<TABLE CLASS="sudokuBoard" CELLPADDING=0 CELLSPACING=0 NOWRAP WIDTH=386'+
				' onmouseout="ShowOptions(null);">');
	for (var y = 0; y < 3; y++)
	{
		document.writeln('<TR>');
		for (var x = 0; x < 3; x++)
		{
			document.writeln('<TD>');
			document.writeln('<TABLE CLASS="sudokuSubBoard" CELLPADDING=0 CELLSPACING=0>');
			for (var y2 = 0; y2 < 3; y2++)
			{
				document.writeln('<TR>');
				for (var x2 = 0; x2 < 3; x2++)
				{
					var cellID = ((y * 3) + y2) * 9;
					cellID += (x * 3) + x2 + 1;
					document.writeln('<TD CLASS="sudokuCell" ');
					document.writeln('ID=' + cellID + ' ');
					document.writeln('onmouseover=OnMouseOver(this) ');
					document.writeln('onmouseout=OnMouseOut(this) ');
					document.writeln('onclick=OnClick(this) ');
					document.writeln('>&nbsp;</TD>');
				}
				document.writeln('</TD>');
			}
			document.writeln('</TABLE>');
			document.writeln('</TD>');
		}
		document.writeln('</TR>');
	}
	document.writeln('</TABLE>');

	// Create a new Cell object connected to each html object
	// representing a cell in the sudoku board.

	for (var i = 1; i < 82; i++)
		Cells[i] = Cell(i);

	// Create 27 sets containing the numbers from 1 to 9.
	// Each set is a row, column, or square of the board which should
	// contain only the numbers 1 to 9 once each.
	for (var i = 1; i < 28; i++)
		Sets[i] = Set();

	// Associate each cell with the sets which is effects.
	for (var i = 1; i < 82; i++)
	{
		Cells[i].AssociateWithSet(((i - 1) % 9) + 1);
		Cells[i].AssociateWithSet(Math.floor((i - 1) / 9) + 10);
		var x = Math.floor((i - 1) / 3);
		var y = Math.floor((i - 1) / 27);
		Cells[i].AssociateWithSet((y * 3) + Math.floor(((i - 1) % 9) / 3) + 19);
	}

	// init global stuff
	for (var i = 0; i < 10; i++)
		numCount[i] = 0;
	numCount[0] = 81;
}




function ShowHint()
{
	for (var s = 1; s < 28; s++)
	if (Sets[s].NumFreeCells() != 0)
	{
		var c = 0;
		var cell = 0;
		var num = 1;
		for (num = 1; num < 10; num++)
		{
			c = 0;
			cell = 0;
			for (var i = 1; i <= Sets[s].numAssociatedCells; i++)
				if ((Sets[s].associatedCells[i].value == 0) && (Sets[s].associatedCells[i].IsOption(num)))
				{
					c++;
					cell = Sets[s].associatedCells[i];
				}
			if (c == 1)
			{
				cell.Blink();
				return;
			}
		}
	}
}




function Solve(justForHint)
{
	if (!IsValidBoard())
	{
		window.alert("Invalid position to solve from.");
		return;
	}
	allowScreenUpdate = false;
	solvedFlag = false;
	var d = new Date();
	var start = d.getTime();
	Solve2(19, 1);
	var d2 = new Date();
	var finish = d2.getTime();
	window.alert("solution found in " + (finish - start) / 1000 + " seconds.");
	allowScreenUpdate = true;
	badSolution = false;
	for (var i = 1; i < 82; i++)
		Cells[i].Redraw();
}





	


function Solve2()
{
	var cellChangedStack = new Array(82);
	var cellChangedStackCount = 0;

	var cellChangedStackCountStack = new Array(1000);
	var cellChangedStackCountStackCount = 0;

	var setNumberStack = new Array(100);
	var setNumberStackCount = 0;

	var numberStack = new Array(100);
	var numberStackCount = 0;

	var cellNumberStack = new Array(100);
	var cellNumberStackCount = 0;

	var number = 1;
	var setNumber = 1;
	var cellNumber = 1;

	var initialized = false;

	var setArray = new Array(10);
	var numberArray = new Array(10);			
		
	while (!solvedFlag)
	{
		if (setNumber >= 10)
		{
			setNumber = 1;
			number++;
		}

		// place all numbers which are a given in the current position.
  		var loop = true;

		while (loop)
		{
			loop = false;
			for (var s = 19; ((!loop) && (s < 28)); s++)
				if (Sets[s].NumFreeCells() != 0)
				{
					var c = 0;
					var cell = 0;
					var num = 1;
					for (num = 1; ((!loop) && (num < 10)); num++)
					{
						c = 0;
						cell = 0;
						for (var i = 1; i <= Sets[s].numAssociatedCells; i++)
							if ((Sets[s].associatedCells[i].value == 0) && (Sets[s].associatedCells[i].IsOption(num)))
							{
								c++;
								cell = Sets[s].associatedCells[i];
							}
						if (c == 1)
						{
							cellChangedStack[cellChangedStackCount++] = cell;
							cell.SetValue(num);
							loop = true;
						}
					}
				}
		}

		// if this solves it then we are done.
		if (numCellsSet == 81)
			solvedFlag = true;

		if ((!initialized) && (!solvedFlag))
		{

			// create the order in which the sets will be checked.  most resolved first.
			var n = 1;
			for (var i = 0; i < 10; i++)
				for (var j = 19; j < 28; j++)
					if (Sets[j].NumFreeCells() == i)
						setArray[n++] = j;

			var numCount = new Array(10);
			for (var i = 1; i < 10; i++)
				numCount[i] = 0;
			for (var i = 1; i < 82; i++)
				if (Cells[i].value)
					numCount[Cells[i].value]++;
			n = 1;
			for (var i = 1; i < 10; i++)
			{
				var max = 1;
				for (var j = 1; j < 10; j++)
					if (numCount[j] >= max)
						max = j;
				numberArray[n++] = max;
				numCount[max] = -1;
			}
			initialized = true;
		}

		var targetNumber = numberArray[number];
		if (!solvedFlag)
		{
			// find a 3x3 grid that needs to place the current number.
			// find a cell within that 3x3 that qualifies as a possible place for that number.
			var placedNumber = false;
			var s = Sets[setArray[setNumber]];
			if (s.Contains(targetNumber))
			{
				for (; ((!placedNumber) && (cellNumber < 10)); cellNumber++)
				{
					var cell = s.associatedCells[cellNumber];
					if ((cell.value == 0) && (cell.IsOption(targetNumber)))
					{
						cell.SetValue(targetNumber);
						cellChangedStack[cellChangedStackCount++] = cell;
						placedNumber = true;
					}
				}

				if ((!placedNumber) || (badSolution))
				{
					// we were unable to place the current number in the current 3x3.  
					// undo the cell changes made and try another possibility.
					var n = cellChangedStackCountStack[--cellChangedStackCountStackCount];
					while (cellChangedStackCount > n)
					{
						cell = cellChangedStack[--cellChangedStackCount];
						cell.SetValue(0);
					}
					if (!setNumberStackCount)
						return;

					setNumber = setNumberStack[--setNumberStackCount];
					number = numberStack[--numberStackCount];
					cellNumber = cellNumberStack[--cellNumberStackCount];
					badSolution = false;
				}
				else
				{
					cellChangedStackCountStack[cellChangedStackCountStackCount++] = cellChangedStackCount - 1;
					cellNumberStack[cellNumberStackCount++] = cellNumber;
					cellNumber = 1;
					setNumberStack[setNumberStackCount++] = setNumber;
				    	numberStack[numberStackCount++] = number;
					setNumber++;
				}
			}
			else
			{
				setNumber++;
			}
		}
	}

}







function IsValidBoard()
{
	for (var i = 1; i < 28; i++)
		if (!Sets[i].IsValid())
				return false;
	return true;
}




function ClearBoard()
{
	for (var i = 1; i < 82; i++)
		Cells[i].Clear();
	for (var i = 1; i < 28; i++)
		Sets[i].Clear();
}



function GetCell(x, y)
{
	// give the board x and y coordinates, return the
	// unique cell associated with it.
	return Cells[((y - 1) * 9) + x];
}



function SetCell(x, y, value, lock)
{
	var cellObj = GetCell(x, y);
	cellObj.SetValue(value);
	if (lock)
		cellObj.Lock();
	else
		cellObj.UnLock();
}



function SetUpBoard(gameNum)
{
	// set up the board with an example game
    ClearBoard();

    if (gameNum == 1)
    {
    SetCell(2, 1, 6, true);
    SetCell(4, 1, 1, true);
    SetCell(6, 1, 4, true);
    SetCell(8, 1, 5, true);
    SetCell(3, 2, 8, true);
    SetCell(4, 2, 3, true);
    SetCell(6, 2, 5, true);
    SetCell(7, 2, 6, true);
    SetCell(1, 3, 2, true);
    SetCell(9, 3, 1, true);
    SetCell(1, 4, 8, true);
    SetCell(4, 4, 4, true);
    SetCell(6, 4, 7, true);
    SetCell(9, 4, 6, true);
    SetCell(3, 5, 6, true);
    SetCell(7, 5, 3, true);
    SetCell(1, 6, 7, true);
    SetCell(4, 6, 9, true);
    SetCell(6, 6, 1, true);
    SetCell(9, 6, 4, true);
    SetCell(1, 7, 5, true);
    SetCell(9, 7, 2, true);
    SetCell(3, 8, 7, true);
    SetCell(4, 8, 2, true);
    SetCell(6, 8, 6, true);
    SetCell(7, 8, 9, true);
    SetCell(2, 9, 4, true);
    SetCell(4, 9, 5, true);
    SetCell(6, 9, 8, true);
    SetCell(8, 9, 7, true);
    return;
    }


    SetCell(1, 1, 6, true);
    SetCell(5, 1, 1, true);
    SetCell(6, 1, 8, true);
    SetCell(8, 1, 7, true);
    SetCell(3, 2, 7, true);
    SetCell(4, 2, 9, true);
    SetCell(7, 2, 6, true);
    SetCell(9, 2, 3, true);
    SetCell(4, 3, 7, true);
    SetCell(5, 3, 6, true);
    SetCell(7, 3, 8, true);
    SetCell(1, 4, 7, true);
    SetCell(4, 4, 2, true);
    SetCell(3, 5, 1, true);
    SetCell(7, 5, 3, true);
    SetCell(6, 6, 9, true);
    SetCell(9, 6, 2, true);
    SetCell(3, 7, 2, true);
    SetCell(5, 7, 9, true);
    SetCell(6, 7, 1, true);
    SetCell(1, 8, 1, true);
    SetCell(3, 8, 5, true);
    SetCell(6, 8, 7, true);
    SetCell(7, 8, 2, true);
    SetCell(2, 9, 4, true);
    SetCell(4, 9, 3, true);
    SetCell(5, 9, 2, true);
    SetCell(9, 9, 6, true);
}



function ShowOptions(cell)
{
	var st = '';
	if (cell != null)
	{
		for (var n = 1; n < 10; n++)
		{
			var isOption = 1;
			for (var i = 1; i < 4; i++)
			{
				var set = cell.sets[i];
				if (!set.Contains(n))
					isOption = 0;
			}
			if (isOption)
			{
				if (st !='')
					st += ', ';
				st += n;
			}
		}
	}

	if (st != '')
		st = 'Options: ' + st;
	document.getElementById('hintWindow').innerHTML = st;
}




function OnMouseOver(object)
{
	object.cell.Highlight();
	ShowOptions(object.cell);
}



function OnMouseOut(object)
{
	object.cell.DeHighlight();
}



function OnClick(object)
{
	object.cell.IncrementValue();
	ShowOptions(object.cell);
}