////////////////////////////////////////////////////////////////////////
//
// UI global variables
//
////////////////////////////////////////////////////////////////////////
KEY_LEFT = 37;
KEY_UP = 38;
KEY_RIGHT = 39;
KEY_DOWN = 40;
KEY_DEL = 46;
KEY_BACKSPACE = 8;
KEY_TAB = 9;
changed = true;
changedByJavascript = false;

pos = new Array(81); // Last position entered/selected by the user

examples = 
[
	["", "---- パズルを選択 ----"],

		["97.3.4.65.2.5.6.8............58.29....2.4.3....87.51............6.2.8.3.84.1.9.27", "Easiest"],
		[".985..2..1.......4.5.....3...26431.....9.8.....71526...7.....8.2.......7..6..152.", "Gentle"],
		["3.2.7.5.4...........6254....9....6....89651....5....2....1978...........5.7.8.2.6", "Moderate"],
		["..54.16......6.....94..7.2.37..2..4.....1.....1..4..56.5.8..26.....9......23.69..", "Tough"],
		["..1..38...4.....6.7..9.65.16..5....2.........8....7..93.61.8..4.9.....8...87..2..", "Diabolical"],
		["5.4.....1..64...7....6.8.......5..13.........83..2.......9.4....4...76..2.....8.9", "22 clues"],
		["...............157.8.725.6...5.4.7..79.2.6.15..4.9.8...4.168.3.321...............", "Weird 1 (gentle)"],
		["...............91.13.6.4.52.8.2.3.465.......861.5.7.3.89.4.5.67.52...............", "Weird 2 (tough)"],
		["9..4.5..1.7.....3...4...9....35.41....7...4....89.15....9...6...8.....2.4..2.8..9", "Evil (with.x-wings)"],
		["..17.48...8.....4.5...9..2...85.31..1...4...8..39.12...9..6...3.1.....5...61.97..", "Evil (with.SF)"],
		["2581.4.3793682751447153.28.7152.3.4.84967532136241..751249..753593742168687351492", "Remote Pairs Test 1"],
		[".8....4955.18493.292435.8.1.3.5.16...15...7....94..51..9672415.1426.59.775....246", "Remote Pairs Test 2"],
		["43..2..96..79.61.4...4.5....4.....12.........96.....4....1.7...5.83.47..17..9..63", "Triples Example"],
		["5........4.1.7..569.84.5...21...3.98..52.96...498...25..26.45737.3.2..64..4...2.9", "Hidden Triple Example"], 
		["..7........45.92..5...43..19..1.8..3..1...6..3..7.5..86..98...4..83.75........8..", "Hidden Quad Example (but no quad)"],
		["..54.781....1.27....1.56..21.7...4.84.2..1..98.6...2.16...1.....139.8.....47.31..", "Hidden Quad Example 2"],
		[".7.3.2.8...3...1..5..4.1..31.......5.3.2.5.1.2.......96..5.9..7..9...5...5.7.4.2.", "Box/Line Example"], 
		[".51.7.9..928156347..398.5..297465..3536.1.479814739625..952.736.62.97.54..564.29.", "Y-wing (single)"], 
		["..931.7.48742593163..74.9.5946587231.3.16459...592346.493671852627895143...432679", "Y-wings (several)"], 
		[".4398.25.6..425...2....1.949....4.7.3..6.8...41.2.9..382.5.........4...553489.71.", "X-wing Example"], 
		[".1....8.35...961....4.81.6.9..4.3..6.2..6..1....8.5..7.6..3.4.1...17.6351.36...2.", "Sword-Fish Example"], 
		["1567.8.2.42961.78.378.4.6.1647...2.8213..7...8954263179.1.7...2534.6.8797.29.41..", "Double Guardian.Example"],
		["1..8.2..482794..5...3...8..234798615...4.1283.18.2.479..6.8.9...82..9.4.3912.4.68", "Disruptive.Guardian.Example"],
];

rowname = ["9", "8", "7", "6", "5", "4", "3", "2", "1"];
colname = ["a", "d", "g", "b", "e", "h", "c", "f", "i"];
colmap  = [0, 3, 6, 1, 4, 7, 2, 5, 8];
blockname = [
//	["upper left", "upper middle", "upper right"],
//	["middle left", "center", "middle right"],
//	["lower left", "lower middle", "lower right"]
	["左上ブロック", "ミドル上ブロック", "右上ブロック"],
	["左真ん中ブロック", "中心ブロック", "右真ん中ブロック"],
	["左下ブロック", "ミドル下ブロック", "右下ブロック"]
];

highlight_grey = '#d8d8d8';
highlight_red = '#ff8080';
highlights = false;
doitforme = 0;

list = ""; // Used to build strings of the form "a, b, c"

trace = true;

regenhxs = false;

////////////////////////////////////////////////////////////////////////
//
// Trace()
//
////////////////////////////////////////////////////////////////////////
function Trace (msg)
{
	if (trace)
		trace &= confirm(msg);
}

////////////////////////////////////////////////////////////////////////
//
// AppendList()
//
////////////////////////////////////////////////////////////////////////
function AppendList (str)
{
	if (list != "")
		list += ", ";
	list += str;
}

////////////////////////////////////////////////////////////////////////
//
// GetList()
//
////////////////////////////////////////////////////////////////////////
function GetList ()
{
	str = list;
	list = "";
	return str;
}


////////////////////////////////////////////////////////////////////////
//
// WriteBoard()
//
// printing: 0 - not printing
//           1 - printing board only
//           2 - printing state
//
////////////////////////////////////////////////////////////////////////
function WriteBoard (doc, printing)
{
	var i, j, k, l, m, value;

	changedByJavascript = true;

	doc.writeln("<table cellspacing=0 cellpadding=0 border=0><tr>");
	doc.writeln("<td><table cellspacing=0 cellpadding=0 border=0>");
	for (i = 0 ; i < 9 ; i++)
		doc.writeln("<tr><td class=label>" + rowname[i] + "</td></tr>");
	doc.writeln("</table></td>");
	doc.writeln("<td class=board><table cellspacing=0 cellpadding=0 border=0>");
	for (i = 0 ; i < 3 ; i++)
	{
		doc.writeln("<tr>");
		for (j = 0 ; j < 3 ; j++)
		{
			doc.writeln("<td class=block><table cellspacing=0 cellpadding=0 border=0>");
			for (k = 0 ; k < 3 ; k++)
			{
				doc.writeln("<tr>");
				for (l = 0 ; l < 3 ; l++)
				{
					var index = (27*i + 9*k + 3*l + j);
					if (printing)
					{
						value = document.sudoku["s" + index].value;
						if (value == "")
						{
							if (printing == 2)
							{
								doc.writeln("<td class=square_small>");
								for (m = 0 ; m < 9 ; m++)
								{
									if (xpos[index] & (1 << m))
										doc.write((m+1) + " ");
								}
							}
							else
								doc.writeln("<td class=square>&nbsp;");
						}
						else
							doc.writeln("<td class=square>" + value);
					}
					else
					{
						doc.writeln("<td class=square id=t" + index + ">");
						doc.write("<textarea class=square type=text size=1 maxlength=1 name=s" + index + " onfocus='select()' onkeyup='EnterDigit(" + index + ", value)'></textarea>");
					}
					doc.writeln("</td>");
				}
				doc.writeln("</tr>");
			}
			doc.writeln("</table></td>");
		}
		doc.writeln("</tr>");
	}
	doc.writeln("</table></td>");
	doc.writeln("<td class=label>&nbsp;</td>");
	doc.writeln("</tr><tr><td>&nbsp;</td><td align=center><table cellspacing=0 cellpadding=0 border=0>");
	for (i = 0 ; i < 9 ; i++)
		doc.writeln("<td class=label>" + colname[colmap[i]] + "</td>");
	doc.writeln("</tr></table></td><td>&nbsp;</td></tr></table>");

	// Set the focus to the first square
	if (!printing)
		document.sudoku["s0"].focus();
}

////////////////////////////////////////////////////////////////////////
//
// EnterDigit()
//
////////////////////////////////////////////////////////////////////////
function EnterDigit (index, value)
{
	document.sudoku["s" + index].className='square';	
	changed = true;
	if (value.length > 1)
	{
//		value=value.substr(value.length-1,1);
//		document.sudoku["s" + index].value = value;
    document.sudoku["s" + index].className='square3';	
		}
  
	if (value.length)
	{
//		if (value.charCodeAt(0) < 49 || value.charCodeAt(0) > 57)
//			value = document.sudoku["s" + index].value = "";
	}

	if (value.length==1)
	{
		document.sudoku["s" + index].className='square';
		SetSquare(value.charCodeAt(0) - 49, index);
	} 
  
	if (value != pos[index]) 
	{
		if (highlights)
			ClearHighlights();
		var k;
		if (changedByJavascript)
		{
			for (k = 0 ; k < 81 ; k++)
				pos[k] = document.sudoku["s" + k].value;
			changedByJavascript = false;
		}
		else
			pos[index] = document.sudoku["s" + index].value;
		if (value != "")
		{
			for (k = 0 ; k < 20 ; k++)
			{
				if (pos[index] == pos[influence[index][k]])
				{
					SetHighlight(index, highlight_red);
					SetHighlight(influence[index][k], highlight_red);
//					GiveHint(SquareName(index) + " and " + SquareName(influence[index][k]) + " cannot both be " + value);
//					a2とa9は同時に2であってはいけません。
					GiveHint(SquareName(index) +"と"+SquareName(influence[index][k])+"は同時に"+value+"であってはいけません。");
					
					break;
				}
			}
		}
	}

	row = Math.floor(index/9);
	col = index%9;
	col = (col%3)*3 + Math.floor(col/3);

	if (row >= 0 && row <= 8 && col >= 0 && col <= 8)
	{
		index = 9*row + (col%3)*3 + Math.floor(col/3);
		document.sudoku["s" + index].select();
	}
}

////////////////////////////////////////////////////////////////////////
//
// LoadPuzzle2()
//
////////////////////////////////////////////////////////////////////////

function LoadPuzzle2 (k)
{
	if (k !="")
	{	
  		var i;
  		for (i = 0 ; i < 81 ; i++)
  		{
  			var row = Math.floor(i/9);
  			var col = i%9;
  			var index = 9*row + 3*(col%3) + Math.floor(col/3);
  			pos[index] = k.charAt(i);
  			if ((pos[index] == " ") || (pos[index] == "0") || (pos[index] == "."))
  				pos[index] = "";
  			document.sudoku["s" + index].value = pos[index];
  			document.sudoku["s" + index].className = 'square';
  		}
  		changed = 1;
  		changedByJavascript = 1;
  		ResetHints();
  		GetPos();
  		SethxsAll();
	}	
}

function LoadPuzzle (k)
{
	if (examples[k][0] != "")
	{
		LoadPuzzle2(examples[k][0]);

	}
}

////////////////////////////////////////////////////////////////////////
//
// SetHighlight()
//
////////////////////////////////////////////////////////////////////////
function SetHighlight (index, colour)
{
	document.sudoku["s" + index].style.background = colour;
	document.getElementById("t" + index).style.background = colour;
	highlights = true;
}

////////////////////////////////////////////////////////////////////////
//
// ClearHighlights()
//
////////////////////////////////////////////////////////////////////////
function ClearHighlights ()
{
	for (k = 0 ; k < 81 ; k++)
		SetHighlight(k, '#ffffff');
	highlights = false;
}

////////////////////////////////////////////////////////////////////////
//
// SquareName()
//
////////////////////////////////////////////////////////////////////////
function SquareName (index)
{
	return colname[index%9] + rowname[Math.floor(index/9)];
}

////////////////////////////////////////////////////////////////////////
//
// GiveHint()
//
////////////////////////////////////////////////////////////////////////
function GiveHint (hint)
{
	document.getElementById("hint").innerHTML = "<b>" + hint + "</b>";
//	if (doitforme) 		document.sudoku["doitforme"].focus();
  		
	doitforme = false;
	stuck = false;

}

////////////////////////////////////////////////////////////////////////
//
// DoItForMe()
//
////////////////////////////////////////////////////////////////////////
function DoItForMe (n, index)
{
	doitforme = 1;
		return "<br><br><input type=hidden name=doitforme onclick='DoHintMove(" + n + "," + index + ")' value=\"ヒント通りにします"+"\">";
//	return "<br><br><input type=button name=doitforme onclick='DoHintMove(" + n + "," + index + ")' value=\"ヒント通りにします"+"\">";
//  	return "<br><br><input type=hidden name=doitforme onclick='DoHintMove(" + n + "," + index + ")' value=\"Do it for me"+"\">";
	
}

////////////////////////////////////////////////////////////////////////
//
// DoHintMove()
//
////////////////////////////////////////////////////////////////////////
function DoHintMove (n, index)
{
    	if (n<9) DoMove(n, index);
     	document.getElementById("hint").innerHTML = "";
     	ClearHighlights();
     	document.sudoku["hintButton"].focus();
      SethxsAll();
}


//=======================================================================================================
//
//  SUDOKU ENGINE
//
//=======================================================================================================


////////////////////////////////////////////////////////////////////////
//
// Global variables
//
////////////////////////////////////////////////////////////////////////

xpos = new Array(81);       // Bitmask of possible digits in location k
influence = new Array(81);  // influence[k] = list of 20 squares in the same row/column/block as k
markPresent = new Array(9); // used to mark squares for graph algorithms
markAbsent = new Array(9);  // used to mark squares for graph algorithms
markCounter = 0;            // Square k is marked when mark[k] == markCounter
longerChainExists = false;
debugInfluence = 0;

commonInfluence = new Array(20); // Used to compute common influence of two squares
commonSize = 0;

// The xpos array encodes the sudoko board in the following order:
//
// 0  3  6  1  4  7  2  5  8
// 
// 9 12 15 10 13 16 11 14 17
//
// ...
//
// Use the notation {a,b} for the arithmetic sequence
// {a, a+b, ..., a+8b}.  Then row k is {0,k}, column k
// is {k,9}, and block (i,j) is {27j+i,3}.
//

buckets = new Array(9); // buckets[3*j + i] = Bitmask of possible bucket optimizations in block (i,j)

stuck = false;
numSquares = 0;
weight = new Array(512); // number of 1's in binary representations of 0-511
hintOnly = false;

// Globals used for chain searches
firstIndex = 0;
searchDigit = 0;
searchType = 0;

// Inference rule caches
influenceCache = new Array(9 * 81 * 20);
lockedPairCache = new Array(9 * 81 * 3);

////////////////////////////////////////////////////////////////////////
//
// Initialization
//
////////////////////////////////////////////////////////////////////////
function Initialize ()
{
	var i, j, k;

	// Initialize weight table
	for (i = 0 ; i < 512 ; i++)
	{
		weight[i] = 0;
		for (j = 256 ; j ; j >>= 1)
		{
			if (i & j)
				weight[i]++;
		}
	}

	// Initialize the influence table
	for (k = 0 ; k < 81 ; k++)
	{
		influence[k] = new Array(20);
		var row = Math.floor(k/9);
		var col = k%9;
		var blockx = col%3;
		var blocky = Math.floor(row/3);
		j = 0;

		// Add block
		var base = blocky * 27 + blockx;
		for (i = 0 ; i < 9 ; i++)
		{
			if (base + 3*i != k)
				influence[k][j++] = base + 3*i;
		}

		// Add row
		base = row * 9;
		for (i = 0 ; i < 9 ; i++)
		{
			if ((i%3) != blockx)
				influence[k][j++] = base + i;
		}

		// Add column
		base = col;
		for (i = 0 ; i < 9 ; i++)
		{
			if (Math.floor(i/3) != blocky)
				influence[k][j++] = base + 9*i;
		}

		influence[k].sort(function(a,b) { return a-b; });
	}

	// Initialize the marks
	for (i = 0 ; i < 9 ; i++)
	{
		markPresent[i] = new Array(81);
		markAbsent[i] = new Array(81);
		for (k = 0 ; k < 81 ; k++)
		{
			markPresent[i][k] = 0;
			markAbsent[i][k] = 0;
		}
	}
}

Initialize();

////////////////////////////////////////////////////////////////////////
//
// GetPos()
//
////////////////////////////////////////////////////////////////////////
function GetPos ()
{
	var i;
	var n;

	// Initialize globals
	for (i = 0 ; i < 81 ; i++)
		xpos[i] = 0x1ff;
	for (i = 0 ; i < 9 ; i++)
	{
		buckets[i] = 0x1ff;
	}
	numSquares = 0;

	// Import the current position
	for (i = 0 ; i < 81 ; i++)
	{
		value = document.sudoku["s" + i].value;
		if (value.length==1)
		{
			n = value.charCodeAt(0) - 49;
			if (n >= 0 && n <= 8)
				SetSquare(n, i);
		}
	}
  
	changed = false;
}

////////////////////////////////////////////////////////////////////////
//
// SetSquare()
//
// Set square[index] with digit (n+1)
//
////////////////////////////////////////////////////////////////////////
function SetSquare (n, index)
{
	var bit = 1 << n;
	var irow = 9 * Math.floor(index / 9);
	var icol = index % 9;
	var iblock = 27 * Math.floor(index / 27) + (index % 3);
	var k;

	document.sudoku["s" + index].value = (n+1);
	xpos[index] = 0;
	changedByJavascript = true;

	for (k = 0 ; k < 9 ; k++)
	{
		xpos[irow + k] &= ~bit;
		xpos[icol + 9*k] &= ~bit;
		xpos[iblock + 3*k] &= ~bit;
	}
	buckets[(icol%3) + 3 * Math.floor(irow/3)] &= ~bit;

	numSquares++;
}

////////////////////////////////////////////////////////////////////////
//
// DoMove()
//
// Move digit (n+1) at index
//
////////////////////////////////////////////////////////////////////////
function DoMove (n, index)
{
	SetSquare(n, index);
  document.sudoku["s" + index].className='square2';	
	stuck = false;
}

////////////////////////////////////////////////////////////////////////
//
// GetContext()
//
////////////////////////////////////////////////////////////////////////
function GetContext (index, stride)
{
	var k;
	ClearHighlights();
	hindex = index;
	hstride = stride;
	for (k = 0 ; k < 9 ; k++)
		SetHighlight(index + k*stride, highlight_grey);

	if (stride == 1)
		//return "In row " + rowname[Math.floor(index/9)];
		
		return "行"+rowname[Math.floor(index/9)]+"に";
		
	else if (stride == 9)
//		return "In column " + colname[index%9];
		return "列" + colname[index%9]+"に";
		
	else
//		return "In the " + blockname[Math.floor(index/27)][index%3] + " block";
		return blockname[Math.floor(index/27)][index%3] + "に";
}

////////////////////////////////////////////////////////////////////////
//
// DoHorzBucket()
//
// The digit (n+1) is in the kth horizontal bucket in block (i,j)
//
////////////////////////////////////////////////////////////////////////
function DoHorzBucket (n, i, j, k, isBlock)
{
	var bit = 1 << n;
	var irow = 9 * (3 * j + k);
	var iblock = 27*j + i;
	var l;

	buckets[3*j + i] &= ~bit;

	// Cleanup
	for (l = 0 ; l < 9 ; l++, irow++, iblock += 3)
	{
		// row
		if (((l%3) != i) && (xpos[irow] & bit))
		{
			stuck = false;
			xpos[irow] -= bit;
		}

		// block
		if ((Math.floor(l/3) != k) && (xpos[iblock] & bit))
		{
			stuck = false;
			xpos[iblock] -= bit;
		}
	}

	if (!stuck && hintOnly)
	{
		var index = 27*j + i + 9*k;
		var hint;
		if (isBlock)
			hint = GetContext(27*j + i, 3);
		else
			hint = GetContext(27*j + 9*k, 1);
//		hint += ", one of ";
		hint += "";
		for (l = 0 ; l < 9 ; l += 3)
		{
			if (xpos[index + l] & bit)
			{
				AppendList(SquareName(index + l));
				SetHighlight(index + l, highlight_red);
			}
		}
//		GiveHint(hint + GetList() + " must be " + (n+1));
		GiveHint(hint + GetList() + "の中必ず" + (n+1)+"があります。"+DoItForMe(9,9));

	}
}

////////////////////////////////////////////////////////////////////////
//
// DoVertBucket()
//
// The digit (n+1) is in the kth vertical bucket in block (i,j)
//
////////////////////////////////////////////////////////////////////////
function DoVertBucket (n, i, j, k, isBlock)
{
	var bit = 1 << n;
	var icol = i + 3*k;
	var iblock = 27*j + i;
	var l;

	buckets[3*j + i] &= ~bit;

	// Cleanup
	for (l = 0 ; l < 9 ; l++, icol += 9, iblock += 3)
	{
		// col
		if ((Math.floor(l/3) != j) && (xpos[icol] & bit))
		{
			stuck = false;
			xpos[icol] -= bit;
		}

		// block
		if (((l%3) != k) && (xpos[iblock] & bit))
		{
			stuck = false;
			xpos[iblock] -= bit;
		}
	}

	if (!stuck && hintOnly)
	{
		var index = 27*j + i + 3*k;
		var hint;
		if (isBlock)
			hint = GetContext(27*j + i, 3);
		else
			hint = GetContext(i + 3*k, 9);
//		hint += ", one of ";
		hint += "";
		for (l = 18 ; l >= 0 ; l -= 9)
		{
			if (xpos[index + l] & bit)
			{
				AppendList(SquareName(index + l));
				SetHighlight(index + l, highlight_red);
			}
		}
//		GiveHint(hint + GetList() + " must be " + (n+1));
//		GiveHint(hint + GetList() + "の中必ず" + (n+1)+"があります。aaaaaa");
		GiveHint(hint + GetList() + "の中必ず" + (n+1)+"があります。"+DoItForMe(9,9));
		
	}
}

////////////////////////////////////////////////////////////////////////
//
// Index()
//
////////////////////////////////////////////////////////////////////////
function Index (bit)
{
	var index = 0;
	for ( ; !(bit & 1) ; bit >>= 1, index++);
	return index;
}

////////////////////////////////////////////////////////////////////////
//
// CheckSingletonDigit()
// Look for a digit with only one place to go in a row or column or block
////////////////////////////////////////////////////////////////////////
function CheckSingletonDigit (index, stride)
{
	var one = 0;
	var two = 0;
	var i, j;

	for (i = 0, j = index ; i < 9 ; i++, j += stride)
	{
		two |= (one & xpos[j]);
	  one |= xpos[j];
	}
	one &= ~two;

	while (one && stuck)
	{
		var bit = one & -one;
		one -= bit;
		for (i = 0 ; i < 9 ; i++)
		{
			square = index + i * stride;
			if (xpos[square] & bit)
			{
				if (hintOnly)
				{
//					GiveHint(GetContext(index, stride) + ", " + SquareName(square) + " must be " + (Index(bit)+1) + DoItForMe(Index(bit), square));
					GiveHint(GetContext(index, stride) + SquareName(square) + "は必ず" + (Index(bit)+1) +"です。"+ DoItForMe(Index(bit), square));
					SetHighlight(square, highlight_red);
				}
				else
					DoMove(Index(bit), square);
				break;
			}
		}
	}
}

////////////////////////////////////////////////////////////////////////
//
// DoPigeonhole()
//
////////////////////////////////////////////////////////////////////////
function DoPigeonhole (k, x, index, stride, transposed)
{
	var j;

	// Look for a set of k bitmasks with the same k bits set (or a subset)
	var i = [0, 1, 2, 3, 4, 5, 6, 7];
	while (stuck)
	{
		// OR together the current set of bitmasks
		var bits = 0;
		for (j = 0 ; j < k ; j++)
		{
			if (!x[i[j]])
				break;
			bits |= x[i[j]];
		}

		// If we found a pigeonhole set then see if it simplifies anything
		if ((j == k) && (weight[bits] == k))
		{
			for (j = 0 ; j < 9 ; j++)
			{
				if ((x[j] & bits) && (x[j] & ~bits))
				{
					if (stuck && hintOnly)
					{
//						var hint = transposed ? ("Found " + k + " digits that can only be in " + k + " squares.<br>") : ("Found " + k + " squares that can only contain " + k + " digits.<br>")
						var hint = transposed ? (k + "つの数字は" + k + "つのセルだけに入れます。<br>") : (k + "つのセルに数字が" + k + "個しかありません.<br>")
						
//						hint += GetContext(index, stride) + ", the squares ";
						hint += GetContext(index, stride) + ", <br>";
						for (l = 0 ; l < 9 ; l++)
						{
							if ((transposed && (bits & (1 << l))) || (!transposed && x[l] && ((x[l] & bits) == x[l])))
							{
								AppendList(SquareName(index + l*stride));
								SetHighlight(index + l*stride, highlight_red);
							}
						}
//						hint += GetList() + "<br>must contain the digits ";
						hint += GetList() + "の中必ず数字";
						
						
						for (l = 0 ; l < 9 ; l++)
						{
							if ((!transposed && (bits & (1 << l))) || (transposed && x[l] && ((x[l] & bits) == x[l])))
								AppendList(l+1);
						}
//						GiveHint(hint + GetList() + "があります。.");
						GiveHint(hint + GetList() + "があります。."+DoItForMe(9,9));
					}

					x[j] &= ~bits;
					stuck = false;
				}
			}
		}

		// Advance to the next set of indices
		for (j = 0 ; (j < k) && (i[k-j-1] == 8-j) ; j++);
		if (j == k)
			break;
		i[k-j-1]++;
		for (j = k-j ; j < k ; j++)
			i[j] = i[j-1] + 1;
	}
}

////////////////////////////////////////////////////////////////////////
//
// Transpose()
//
////////////////////////////////////////////////////////////////////////
function Transpose (x, y)
{
	var i, j;

	for (i = 0 ; i < 9 ; i++)
	{
		var bit = 1 << i;
		y[i] = 0;
		for (j = 0 ; j < 9 ; j++)
		{
			if (x[j] & bit)
				y[i] |= 1 << j;
		}
	}
}

////////////////////////////////////////////////////////////////////////
//
// CheckPigeonhole()
//
////////////////////////////////////////////////////////////////////////
function CheckPigeonhole (k, index, stride)
{
	var i, j;
	var x = new Array(9);
	var y = new Array(9);

	// Move the square bitmasks into x
	for (i = 0, j = index ; i < 9 ; i++, j += stride)
		x[i] = xpos[j];

	// Look for a set of k squares with the same k possible digits
	DoPigeonhole(k, x, index, stride, 0);

	// Transpose the bitmasks
	Transpose(x, y);

	// Look for a set of k digits with the same k possible squares
	DoPigeonhole(k, y, index, stride, 1);

	// Transpose back
	Transpose(y, x);

	// Restore the xpos bitmasks
	for (i = 0, j = index ; i < 9 ; i++, j += stride)
		xpos[j] = x[i];
}

////////////////////////////////////////////////////////////////////////
//
// ComputeCommonInfluence()
//
////////////////////////////////////////////////////////////////////////
function ComputeCommonInfluence (i1, i2)
{
	commonSize = 0;
	var j1 = 0;
	var j2 = 0;
	while ((j1 < 20) && (j2 < 20))
	{
		if (influence[i1][j1] == influence[i2][j2])
		{
			commonInfluence[commonSize++] = influence[i1][j1];
			j1++;
			j2++;
		}
		else if (influence[i1][j1] < influence[i2][j2])
			j1++;
		else
			j2++;
	}
}

////////////////////////////////////////////////////////////////////////
//
// SimplifyChain()
//
// Either the first or last square in the chain must be the given digit.
//
// searchType  - 0 = digit (digit is always the same)
//               1 = pairs (this should always be called for a square of weight 2)
//               2 = generalized (most aggressive)
//
////////////////////////////////////////////////////////////////////////
function SimplifyChain (chain, digit)
{	
	var i;
	var index = chain[0];
	ComputeCommonInfluence(index, firstIndex);
	var bit = 1 << digit;
	for (i = 0 ; i < commonSize ; i++)
	{
		if (xpos[commonInfluence[i]] & bit)
		{
			if (hintOnly && stuck)
			{
				var hint = "In chain ";
				var c = index;
				var c1 = chain[1];
				while (c1 != firstIndex)
				{
					c = [c1[0], c];
					c1 = c1[1];
				}
				SetHighlight(firstIndex, highlight_red);
				AppendList(SquareName(firstIndex));
				while (c != index)
				{
					SetHighlight(c[0], highlight_grey);
					AppendList(SquareName(c[0]));
					c = c[1];
				}
				SetHighlight(index, highlight_red);
				AppendList(SquareName(index));
				var context;
				if (searchType == 0)
//					context = "In chain of " + (digit+1) + "'s (";
					context = "数字" + (digit+1) + "のチェーン(";
					
				else if (searchType == 1)
//					context = "In chain of pairs (";
					context = "ダブルチェーン(";
				else
//					context = "In generalized chain (";
					context = "チェーン(";
					
					
//				GiveHint(context + GetList() + "),<br>one of " + SquareName(index) + ", " + SquareName(firstIndex) + " must be " + (digit+1));
//				GiveHint(context + GetList() + "),<br>に、" + SquareName(index) + "と" + SquareName(firstIndex) + "の中必ず" + (digit+1)+"があります。");
				GiveHint(context + GetList() + "),<br>に、" + SquareName(index) + "と" + SquareName(firstIndex) + "の中必ず" + (digit+1)+"があります。"+DoItForMe(9,9));
				
			}

			xpos[commonInfluence[i]] -= bit;
			stuck = false;
		}
	}
}

////////////////////////////////////////////////////////////////////////
//
// SearchForDigitPresent()
//
////////////////////////////////////////////////////////////////////////
function SearchForDigitPresent (len, maxlen, chain, digit, base, stride)
{
	if (!stuck || ((len == maxlen) && longerChainExists))
		return;

	var index = -1;
	var i;
	var bit = 1 << digit;

	for (i = 0 ; i < 9 ; i++)
	{
		var index2 = base + i*stride;
		if ((xpos[index2] & bit) && (index2 != chain[0]))
		{
			if (index != -1)
				return;
			index = index2;
		}
	}

	if ((index != -1) && (markPresent[digit][index] != markCounter))
	{
		if (len < maxlen)
			SearchChainDigitPresent(len+1, maxlen, [index, chain], digit);
		else
			longerChainExists = true;
	}
}

////////////////////////////////////////////////////////////////////////
//
// SearchChainDigitAbsent()
//
// Continue a chain search by assuming that 'digit' is absent at
// the current location.
//
// len         - length of current chain
// maxlen      - maximum chain length
// chain       - [currIndex, rest of chain]
// digit       - digit assumed to be absent at currIndex
// firstIndex  - first index in chain
// searchDigit - digit that we're looking for to be present
//               (we started the chain by assuming it's not present at firstIndex)
// searchType  - 0 = digit (digit is always the same)
//               1 = pairs (this should always be called for a square of weight 2)
//               2 = generalized (most aggressive)
//
////////////////////////////////////////////////////////////////////////
function SearchChainDigitAbsent (len, maxlen, chain, digit)
{
	//Trace((digit+1) + " absent in " + chain);

	var i;
	var index = chain[0];
	markAbsent[digit][index] = markCounter;

	// See if there's only two possible places for the digit in the same row, column or block
	if (searchType != 1)
	{
		var cacheIndex = 3 * (81 * digit + index);
		for (i = 0 ; stuck && (i < 3) ; i++)
		{
			var index2 = lockedPairCache[cacheIndex++];
			if (index2 == -1)
				break;
			if (markPresent[digit][index2] != markCounter)
			{
				if (len < maxlen)
					SearchChainDigitPresent(len+1, maxlen, [index2, chain], digit);
				else
					longerChainExists = true;
			}
		}
	}

	// If this is a pair then the other digit must be present
	if ((searchType != 0) && (weight[xpos[index]] == 2) && (markPresent[digit][index] != markCounter))
		SearchChainDigitPresent(len, maxlen, chain, Index(xpos[index] - (1 << digit)));
}

////////////////////////////////////////////////////////////////////////
//
// SearchChainDigitPresent()
//
// Continue a chain search by assuming that 'digit' is present at
// the current location.
//
// len         - length of current chain
// maxlen      - maximum chain length
// chain       - [currIndex, rest of chain]
// digit       - digit assumed to be present at currIndex
// firstIndex  - first index in chain
// searchDigit - digit that we're looking for to be present
//               (we started the chain by assuming it's not present at firstIndex)
// searchType  - 0 = digit (digit is always the same)
//               1 = pairs 
//               2 = generalized (most aggressive)
//
////////////////////////////////////////////////////////////////////////
function SearchChainDigitPresent (len, maxlen, chain, digit)
{
	//Trace((digit+1) + " present in " + chain);

	var i;
	var index = chain[0];
	markPresent[digit][index] = markCounter;

	if ((digit == searchDigit) && (index != firstIndex))
		SimplifyChain(chain, digit, firstIndex, searchType);

	if ((len == maxlen) && longerChainExists)
		return;

	var cacheIndex = 20 * (81 * digit + index);
	for (i = 0 ; stuck && (i < 20) ; i++)
	{
		var index2 = influenceCache[cacheIndex++];
		if (index2 == -1)
			break;
		if ((markAbsent[digit][index2] != markCounter) && ((searchType != 1) || (weight[xpos[index2]] == 2)))
		{
			if (len < maxlen)
				SearchChainDigitAbsent(len+1, maxlen, [index2, chain], digit);
			else
				longerChainExists = true;
		}
	}

	// All other digits are absent from this square
	if (searchType == 2)
	{
		for (i = 0 ; i < 9 ; i++)
		{
			if ((xpos[index] & (1 << i)) && (i != digit) && (markAbsent[i][index] != markCounter))
				SearchChainDigitAbsent(len, maxlen, chain, i);
		}
	}
}

////////////////////////////////////////////////////////////////////////
//
// SearchChain()
//
////////////////////////////////////////////////////////////////////////
function SearchChain (maxlen, _firstIndex, _searchDigit, _searchType)
{
	firstIndex = _firstIndex;
	searchDigit = _searchDigit;
	searchType = _searchType;
	markCounter++;
	//Trace("Searching for " + (_searchDigit+1) + ", searchType = " + _searchType);
	SearchChainDigitAbsent(1, maxlen, [firstIndex], searchDigit);
}

////////////////////////////////////////////////////////////////////////
//
// FindLockedPair()
//
////////////////////////////////////////////////////////////////////////
function FindLockedPair (currIndex, digit, base, stride)
{
	var index = -1;
	var i;
	var bit = 1 << digit;

	for (i = 0 ; i < 9 ; i++)
	{
		var index2 = base + i*stride;
		if ((xpos[index2] & bit) && (index2 != currIndex))
		{
			if (index != -1)
				return -1;
			index = index2;
		}
	}

	return index;
}

////////////////////////////////////////////////////////////////////////
//
// ComputeCaches()
//
////////////////////////////////////////////////////////////////////////
function ComputeCaches ()
{
	var i, j, k, l, index, bit;
	for (k = 0 ; k < 9 ; k++)
	{
		bit = 1 << k;
		for (i = 0 ; i < 81 ; i++)
		{
			if (xpos[i])
			{
				// influence cache
				index = 20 * (81 * k + i);
				l = 0;
				for (j = 0 ; j < 20 ; j++)
				{
					if (xpos[influence[i][j]] & bit)
						influenceCache[index + l++] = influence[i][j];
				}
				if (l < 20)
					influenceCache[index + l] = -1;

				// locked pair cache
				var row = Math.floor(i / 9);
				var col = i % 9;
				index = 3 * (81 * k + i);

				lockedPairCache[index] = FindLockedPair(i, k, row * 9, 1);
				lockedPairCache[index + 1] = FindLockedPair(i, k, col, 9);
				lockedPairCache[index + 2] = FindLockedPair(i, k, 27 * Math.floor(row / 3) + (col % 3), 3);

				if (lockedPairCache[index + 1] == -1)
				{
					lockedPairCache[index + 1] = lockedPairCache[index + 2];
					lockedPairCache[index + 2] = - 1;
				}
				if (lockedPairCache[index] == -1)
				{
					lockedPairCache[index] = lockedPairCache[index + 1];
					lockedPairCache[index + 1] = lockedPairCache[index + 2];
					lockedPairCache[index + 2] = - 1;
				}
			}
		}
	}
}

////////////////////////////////////////////////////////////////////////
//
// CheckChain()
//
////////////////////////////////////////////////////////////////////////
function CheckChain ()
{
	ComputeCaches();

	var n, k, i;
	longerChainExists = true;
	for (n = 3 ; stuck && longerChainExists ; n++)
	{
		longerChainExists = false;
		for (k = 0 ; stuck && (k < 81) ; k++)
		{
			// Look for a chain of pairs
			if (weight[xpos[k]] == 2)
			{
				SearchChain(n, k, Index(xpos[k]), 1);
				if (stuck)
					SearchChain(n, k, Index(xpos[k] & (xpos[k] - 1)), 1);
			}

			// Look for an alternating chain of a single digit
			if (stuck && xpos[k])
			{
				for (i = 0 ; stuck && (i < 9) ; i++)
				{
					if (xpos[k] & (1 << i))
						SearchChain(n, k, i, 0);
				}
			}
		}
	}

	// Sledgehammer
	longerChainExists = true;
	for (n = 3 ; stuck && longerChainExists ; n++)
	{
		longerChainExists = false;
		for (k = 0 ; stuck && (k < 81) ; k++)
		{
			for (i = 0 ; stuck && (i < 9) ; i++)
			{
				if (xpos[k] & (1 << i))
					SearchChain(n, k, i, 2);
			}
		}
	}
}

////////////////////////////////////////////////////////////////////////
//
// SolvePos()
//
////////////////////////////////////////////////////////////////////////
function SolvePos ()
{
	
	
	if (changed)
		GetPos()
		;
  
	var i, j, k, l;
	stuck = true;
  
	// Look for a digit with only one place to go in a row or column or block
	for (k = 0 ; k < 9 ; k++)
	{
		CheckSingletonDigit(9*k, 1);
		CheckSingletonDigit(k, 9);
		CheckSingletonDigit(27 * Math.floor(k/3) + (k%3), 3);
	}
  
	// Look for a square with only one possibility
	for (k = 0 ; (k < 81) && stuck ; k++)
	{
		var b = xpos[k];
		if (b && !(b & (b-1)))
		{
			if (hintOnly)
			{
//				GiveHint(SquareName(k) + " can only be " + (Index(xpos[k]) + 1) + DoItForMe(Index(xpos[k]), k));
				GiveHint(SquareName(k) + "は" + (Index(xpos[k]) + 1)+"でなければなりません。" + DoItForMe(Index(xpos[k]), k));
				SetHighlight(k, highlight_red);
			}
			else
				DoMove(Index(xpos[k]), k);
		}
		
	}

	// Bucket strategy: try to isolate a digit in one of three squares
	for (i = 0 ; (i < 3) && stuck ; i++)
	{
		for (j = 0 ; (j < 3) && stuck ; j++)
		{
			if (buckets[3*j+i])
			{
				for (k = 0 ; k < 3 ; k++)
				{
					var mask1, mask2, mask3;
					var index1, index2;

					// Row bucket
					mask1 = mask2 = 0;
					index1 = 27 * j + 9 * k;
					index2 = 27 * j + i;
					mask3 = xpos[index2 + 9 * k] | xpos[index2 + 9 * k + 3] | xpos[index2 + 9 * k + 6];
					for (l = 0 ; l < 9 ; l++, index1++, index2 += 3)
					{
						if ((l%3) != i)
							mask1 |= xpos[index1];
						if (Math.floor(l/3) != k)
							mask2 |= xpos[index2];
					}
					mask1 = mask3 & buckets[3*j+i] & ~(mask1 & mask2);

					if (mask1)
					{
						var isBlock = mask3 & ~mask2;
						while (mask1 && stuck)
						{
							mask2 = mask1 & -mask1;
							mask1 -= mask2;
							DoHorzBucket(Index(mask2), i, j, k, isBlock & mask2);
						}
						if (!stuck)
							break;
					}

					// Column bucket
					mask1 = mask2 = 0;
					index1 = 3 * k + i;
					index2 = 27 * j + i;
					mask3 = xpos[index2 + 3 * k] | xpos[index2 + 3 * k + 9] | xpos[index2 + 3 * k + 18];
					for (l = 0 ; l < 9 ; l++, index1 += 9, index2 += 3)
					{
						if (Math.floor(l/3) != j)
							mask1 |= xpos[index1];
						if ((l%3) != k)
							mask2 |= xpos[index2];
					}
					mask1 = mask3 & buckets[3*j+i] & ~(mask1 & mask2);

					if (mask1)
					{
						var isBlock = mask3 & ~mask2;
						while (mask1 && stuck)
						{
							mask2 = mask1 & -mask1;
							mask1 -= mask2;
							DoVertBucket(Index(mask2), i, j, k, isBlock & mask2);
						}
						if (!stuck)
							break;
					}
				}
			}
		}
	}

	// Pigeonhole strategy: Find k squares that can only contain k digits, or 
	// find k digits that can only be in k squares.
	for (k = 2 ; stuck && (k < 5) ; k++)
	{
		for (i = 0 ; i < 9 ; i++)
		{
			CheckPigeonhole(k, 9*i, 1);
			CheckPigeonhole(k, i, 9);
			CheckPigeonhole(k, 27 * Math.floor(i/3) + (i%3), 3);
		}
	}

	// Chain strategy: Find a chain of squares each with two possibilities
	// from which we can derive that one of the endpoints must be a certain
	// digit.
	if (stuck)
		CheckChain();
  
  
  
	if (numSquares == 81)
		GiveHint("パズルは解きました!");
	else if (stuck)
	{
		var count = 0;
		for (i = 0 ; i < 81 ; i++)
		{
			if (xpos[i])
				count++;
		}
		if (numSquares + count == 81)
			GiveHint("困っている！");
		else
			GiveHint("正解無し");
	}
	else if (!hintOnly)
		setTimeout("SolvePos()", 1);
	
		
}

////////////////////////////////////////////////////////////////////////
//
// Reset()
//
////////////////////////////////////////////////////////////////////////
function Reset ()
{
	if (confirm("数独をイニシャル状態にリセットしますか？"))
	{
		ResetHints();
		var i;
		for (i = 0 ; i < 81 ; i++)
			document.sudoku["s" + i].value = pos[i];
		changed = true;
		changedByJavascript = true;
		GetPos();
		SethxsAll();
		document.sudoku["hintButton"].focus();
		
	}
}

////////////////////////////////////////////////////////////////////////
//
// Erase()
//
////////////////////////////////////////////////////////////////////////
function Erase ()
{
	if (confirm("数独をクリアしますか？"))
	{
		ResetHints();
		var i;
		for (i = 0 ; i < 81 ; i++)
		{
			pos[i] = document.sudoku["s" + i].value = "";
			document.sudoku["s" + i].className='square';
		}	
		changed = true;
		changedByJavascript = true;
		document.sudoku["s0"].select();
		GetPos();
	}
}

////////////////////////////////////////////////////////////////////////
//
// Solve()
//
////////////////////////////////////////////////////////////////////////
function Solve ()
{
	ClearHighlights();
	GiveHint("考えているところ");
	hintOnly = false;
	setTimeout("SolvePos()", 1);
	
	
}

////////////////////////////////////////////////////////////////////////
//
// Hint()
//
////////////////////////////////////////////////////////////////////////
function Hint ()
{
	if (highlights)
	{
	    document.sudoku["doitforme"].click();
  }
  else
  {	
     	ClearHighlights();
     	GiveHint("考えているところ");
     	hintOnly = true;
     	setTimeout("SolvePos()", 1);
  }	
}

////////////////////////////////////////////////////////////////////////
//
// ResetHints()
//
////////////////////////////////////////////////////////////////////////
function ResetHints ()
{
	document.getElementById("hint").innerHTML = "";
	ClearHighlights();
	
//	changed = true;

	GetPos ();
	showhxs();
	changed = false;

	document.sudoku["hintButton"].focus();
}


////////////////////////////////////////////////////////////////////////
//
// Fetch()
//
////////////////////////////////////////////////////////////////////////
function FetchPosition ()
{
	var win = window.open('',"loading",'height=75,width=170');
	var doc = win.document;

//	doc.writeln("<html><frameset rows=\"74,1\">");
//	doc.writeln("<frame src=\"loading.html\">");
//	doc.writeln("<frame src=\"http://magictour.free.fr/top95\">");
//	doc.writeln("</frameset></html>");

	doc.writeln("<html><body>");
	doc.writeln("<iframe src=\"http://magictour.free.fr/top95\"></iframe>");
	doc.writeln("</body></html>");

	doc.close();

	alert(win.document.all[0].all[1].all[0].innerHTML);

	//win.close();
}

function importsudoku()
{
	var dstring;
	var actualstr='';
	var c,i,j,s,t;
	var dstring=window.prompt("数字のストリングを81個入力（ブランクは0、*、.で表示)",'');
	if( dstring === null ) return;
	if( dstring.length === 0 ) return;
	
	dstring=dstring.replace(/\*/g, '0').replace(/\./g, '0').replace(/_/g, '0')
	
	LoadPuzzle2(dstring);

}

////////////////////////////////////////////////////////////////////////
//
// WriteExamples()
//
////////////////////////////////////////////////////////////////////////
function WriteExamples ()
{
	var i;
	for (i = 0 ; i < examples.length-1 ; i++)
		document.writeln("<option value = " + i + ">" + examples[i][1] + "</option>");
}

function Gethxs(x)
{
  	var s='';
  	var i;
  	for (i = 0 ; i <= 8 ; i++) 
  	 {if (x & (1 << i)) 
  	{s=(s+(i+1));}
  	 }
  	return s;
  	}

function Gethxs2(x)
{
  	var s='';
  	var i;
  	for (i = 0 ; i <= 8 ; i++) 
  	 {if (x & (1 << i)) 
  	     {
  	     	s=(s+(i+1));
  	     	if ((i%3)==2) {s=s+'\n'} else s=s+' ';
  	     	} 
  	   else 
  	   {if ((i%3)==2) {s=s+' \n'} else s=s+'  ';}	
  	 }
  	return s;
  	}


function SethxsAll()
{
	var j
	if (document.sudoku["showhints"].checked)
	{
       for (j = 0 ; j <= 80 ; j++) 
       {
       	if (Gethxs(xpos[j]) != '') 
       	{
       	    document.sudoku["s" + j].value = Gethxs2(xpos[j]) ;
       	    document.sudoku["s" + j].className='square3';
         }
       }
  }
	else {
       for (j = 0 ; j <= 80 ; j++) 
       {
       	if (Gethxs(xpos[j]) != '') 
       	{
       	    document.sudoku["s" + j].value = '';
       	    document.sudoku["s" + j].className='square';
         }
       }
  }
}


function showhxs()
{
	   SethxsAll();
}