/* * * * * * * * * * * * * * * * * * * * * *\
* O R D E R - 8  S Q U A R E  B U I L D E R *
\* * * * * * * * * * * * * * * * * * * * * */
//The initial order-8 magic square on the page
var tableBases = new Array(
	new Array( 1, 57,  2, 58, 16, 56, 15, 55),
	new Array(23, 47, 24, 48, 26, 34, 25, 33),
	new Array(46, 22, 45, 21, 35, 27, 36, 28),
	new Array(60,  4, 59,  3, 53, 13, 54, 14),
	new Array(17, 41, 18, 42, 32, 40, 31, 39),
	new Array( 7, 63,  8, 64,  10, 50,  9, 49),
	new Array(62,  6, 61,  5, 51, 11, 52, 12),
	new Array(44, 20, 43, 19, 37, 29, 38, 30)
);

var masterBaseLines = new Array(
	new Array( 0, 56,  1, 57, 15, 55, 14, 54),
	new Array( 0, 22, 45, 59, 16,  6, 61, 43)
);

var featureList = new Array('selectcompact','select3x3','select5x5','selectcomplete','selectzigzag','selectassociated','selectfranklinv','selectfranklinw','selectorder4','selecthalfrows');

var baseLines = new Array;//list of all valid base lines
var baseSquares = new Array;//list of all valid base squares
var baseSquareSet = new Array //list of currently valid base squares
var features = new Array;//mask for all features present in base squares

//Creates valid base lines.
function getBaseLines()
{
	for (var i = 15; i<121; i++)
	{
		var count = 0;
		for (var j = 0; j<8; j++)
		{
			count += ((i >> j) & 1);
		}
		if (count == 4)
		{
			baseLines.push(i);
		}
	}
}

//Determines if base squares are valid.
function validateSquare(square)
{
	for (var v = 0; v < 8; v++)
	{
		var sum = 0;
		for (var w = 0; w < 8; w++)
		{
			sum += square[w][(v+w)%8];
		}
		if (sum != 4)
		{
			return false;
		}
		var sum = 0;
		for (var w = 0; w < 8; w++)
		{
			sum += square[w][(7-w+v)%8];
		}
		if (sum != 4)
		{
			return false;
		}
	}
	return true;
}

//Creates valid base squares.
function getBaseSquares()
{
	for(var i = 0; i < baseLines.length; i++)
	{
		for(var j = i+1; j < baseLines.length; j++)
		{
			var square = new Array();
			for(var y = 0; y < 8; y++)
			{
				var line = new Array();
				for(var x = 0; x < 8; x++)
				{
					line.push(((baseLines[i] >> (7-y)) & 1) ^ ((baseLines[j] >> (7-x)) & 1));
				}
				square.push(line);
			}
			if (validateSquare(square))
			{
				baseSquares.push(square);
				var square = new Array();
				for(var y = 0; y < 8; y++)
				{
					var line = new Array();
					for(var x = 0; x < 8; x++)
					{
						line.push(((baseLines[j] >> (7-y)) & 1) ^ ((baseLines[i] >> (7-x)) & 1));
					}
					square.push(line);
				}
				baseSquares.push(square);
			}
		}
	}
}

//Creates compact mask.
function getCompact(square)
{
	for(var y = 0; y < 8; y++)
	{
		for(var x = 0; x < 8; x++)
		{
			var sum = square[x][y] + square[(x+1)%8][y] + square[x][(y+1)%8] + square[(x+1)%8][(y+1)%8];
			if (sum !=2)
			{
				return false;
			}
		}
	}
	return true;
}

//Creates compact3 mask.
function getCompact3(square)
{
	for(var y = 0; y < 8; y++)
	{
		for(var x = 0; x < 8; x++)
		{
			var sum = square[x][y] + square[(x+2)%8][y] + square[x][(y+2)%8] + square[(x+2)%8][(y+2)%8];
			if (sum !=2)
			{
				return false;
			}
		}
	}
	return true;
}

//Creates compact5 mask.
function getCompact5(square)
{
	for(var y = 0; y < 8; y++)
	{
		for(var x = 0; x < 8; x++)
		{
			var sum = square[x][y] + square[(x+4)%8][y] + square[x][(y+4)%8] + square[(x+4)%8][(y+4)%8];
			if (sum !=2)
			{
				return false;
			}
		}
	}
	return true;
}

//Creates zigzag2 mask.
function getZigzag(square)
{
	for(var y = 0; y < 8; y++)
	{
		for(var x = 0; x < 2; x++)
		{
			var sum = square[x][y] + square[(x+1)%8][(y+1)%8] + square[(x+2)%8][y] + square[(x+3)%8][(y+1)%8] + square[(x+4)%8][y] + square[(x+5)%8][(y+1)%8] + square[(x+6)%8][y] + square[(x+7)%8][(y+1)%8];
			if (sum !=4)
			{
				return false;
			}
			var sum = square[y][x] + square[(y+1)%8][(x+1)%8] + square[y][(x+2)%8] + square[(y+1)%8][(x+3)%8] + square[y][(x+4)%8] + square[(y+1)%8][(x+5)%8] + square[y][(x+6)%8] + square[(y+1)%8][(x+7)%8];
			if (sum !=4)
			{
				return false;
			}
		}
	}
	return true;
}

//Creates associated mask.
function getAssociated(square)
{
	for(var y = 0; y < 4; y++)
	{
		for(var x = 0; x < 8; x++)
		{
			var sum = square[x][y] + square[7-x][7-y];
			if (sum !=1)
			{
				return false;
			}
		}
	}
	return true;
}

//Creates FranklinV mask.
function getFranklinV(square)
{
	for(var x = 0; x < 8; x++)
	{
		var sum = square[x][0] + square[(x+1)%8][1] + square[(x+2)%8][2] + square[(x+3)%8][3] + square[(x+3)%8][4] + square[(x+2)%8][5] + square[(x+1)%8][6] + square[x][7];
		if (sum !=4)
		{
			return false;
		}
		var sum = square[x][0] + square[(x+7)%8][1] + square[(x+6)%8][2] + square[(x+5)%8][3] + square[(x+5)%8][4] + square[(x+6)%8][5] + square[(x+7)%8][6] + square[x][7];
		if (sum !=4)
		{
			return false;
		}
		var sum = square[0][x] + square[1][(x+1)%8] + square[2][(x+2)%8] + square[3][(x+3)%8] + square[4][(x+3)%8] + square[5][(x+2)%8] + square[6][(x+1)%8] + square[7][x];
		if (sum !=4)
		{
			return false;
		}
		var sum = square[0][x] + square[1][(x+7)%8] + square[2][(x+6)%8] + square[3][(x+5)%8] + square[4][(x+5)%8] + square[5][(x+6)%8] + square[6][(x+7)%8] + square[7][x];
		if (sum !=4)
		{
			return false;
		}
	}
	return true;
}

//Creates FranklinW mask.
function getFranklinW(square)
{
	for(var x = 0; x < 8; x++)
	{
		var sum = square[x][0] + square[(x+1)%8][1] + square[(x+1)%8][2] + square[x][3] + square[x][4] + square[(x+1)%8][5] + square[(x+1)%8][6] + square[x][7];
		if (sum !=4)
		{
			return false;
		}
		var sum = square[x][0] + square[(x+7)%8][1] + square[(x+7)%8][2] + square[x][3] + square[x][4] + square[(x+7)%8][5] + square[(x+7)%8][6] + square[x][7];
		if (sum !=4)
		{
			return false;
		}
		var sum = square[0][x] + square[1][(x+1)%8] + square[2][(x+1)%8] + square[3][x] + square[4][x] + square[5][(x+1)%8] + square[6][(x+1)%8] + square[7][x];
		if (sum !=4)
		{
			return false;
		}
		var sum = square[0][x] + square[1][(x+7)%8] + square[2][(x+7)%8] + square[3][x] + square[4][x] + square[5][(x+7)%8] + square[6][(x+7)%8] + square[7][x];
		if (sum !=4)
		{
			return false;
		}
	}
	return true;
}

//Creates order4 mask.
function getOrder4(square)
{
	for(var x = 0; x < 4; x++)
	{
		var sum = square[x][0] + square[x][1] + square[x][2] + square[x][3];
		if (sum !=2)
		{
			return false;
		}
		var sum = square[0][x] + square[1][x] + square[2][x] + square[3][x];
		if (sum !=2)
		{
			return false;
		}
		var sum = square[0][x] + square[1][(x+1)%4] + square[2][(x+2)%4] + square[3][(x+3)%4];
		if (sum !=2)
		{
			return false;
		}
		var sum = square[0][(8-x)%4] + square[1][(7-x)%4] + square[2][(6-x)%4] + square[3][(5-x)%4];
		if (sum !=2)
		{
			return false;
		}
		var sum = square[x][4] + square[x][5] + square[x][6] + square[x][7];
		if (sum !=2)
		{
			return false;
		}
		var sum = square[0][x+4] + square[1][x+4] + square[2][x+4] + square[3][x+4];
		if (sum !=2)
		{
			return false;
		}
		var sum = square[0][x+4] + square[1][((x+1)%4)+4] + square[2][((x+2)%4)+4] + square[3][((x+3)%4)+4];
		if (sum !=2)
		{
			return false;
		}
		var sum = square[0][((8-x)%4)+4] + square[1][((7-x)%4)+4] + square[2][((6-x)%4)+4] + square[3][((5-x)%4)+4];
		if (sum !=2)
		{
			return false;
		}
	}
	return true;
}

//Creates halfrows mask.
function getHalfRows(square)
{
	for(var x = 0; x < 8; x++)
	{
		var sum1 = square[x][0] + square[x][1] + square[x][2] + square[x][3];
		var sum2 = square[x][4] + square[x][5] + square[x][6] + square[x][7];
		var sum3 = square[0][x] + square[1][x] + square[2][x] + square[3][x];
		var sum4 = square[4][x] + square[5][x] + square[6][x] + square[7][x];
		if (sum1 !=2 || sum2 !=2 || sum3 !=2 || sum4 !=2)
		{
			return false;
		}
	}
	return true;
}

//Creates all valid base squares and makes feature mask.
function loadBaseSquares()
{
	getBaseLines();
	getBaseSquares();
	for (var i=0; i<17; i++)
		{
			features.push(new Array());
		}
	for(var i = 0; i < baseSquares.length; i++)
	{
		if (getCompact(baseSquares[i]))
		{
			features[0].push(1);
		}
		else
		{
			features[0].push(0);
		}
		if (getCompact3(baseSquares[i]))
		{
			features[1].push(1);
		}
		else
		{
			features[1].push(0);
		}
		if (getCompact5(baseSquares[i]))//and complete
		{
			features[2].push(1);
			features[3].push(1);
		}
		else
		{
			features[2].push(0);
			features[3].push(0);
		}
		if (getZigzag(baseSquares[i]))
		{
			features[4].push(1);
		}
		else
		{
			features[4].push(0);
		}
		if (getAssociated(baseSquares[i]))
		{
			features[5].push(1);
		}
		else
		{
			features[5].push(0);
		}
		if (getFranklinV(baseSquares[i]))
		{
			features[6].push(1);
		}
		else
		{
			features[6].push(0);
		}
		if (getFranklinW(baseSquares[i]))
		{
			features[7].push(1);
		}
		else
		{
			features[7].push(0);
		}
		if (getOrder4(baseSquares[i]))
		{
			features[8].push(1);
		}
		else
		{
			features[8].push(0);
		}
		if (getHalfRows(baseSquares[i]))
		{
			features[9].push(1);
		}
		else
		{
			features[9].push(0);
		}
	}
// gather valid base squares into baseSquareSet
	baseSquareSet = new Array();
	for (var y=0; y<baseSquares.length; y++)
	{
		baseSquareSet.push(baseSquares[y]);
	}
}

//Makes it impossible to check the associated box.
function disableBox(boxId)
{
	document.getElementById(boxId).disabled = true;
}

//Makes it possible to check the associated box.
function enableBox(boxId)
{
	document.getElementById(boxId).disabled = false;
}

//Unchecks the associated box.
function uncheckBox(boxId)
{
	document.getElementById(boxId).checked = false;
}

//Determines if features selected and assigns them a sequence number.
function enumerateChecked(boxId,matrixNum)
{
	if (document.getElementById(boxId).checked == true)
	{
		matrix.push(matrixNum);
	}
}

//Determines if the current square has even integral distribution.
function consecutive(tableBases, base)
{
	var count = new Array();
	for (var x=0; x < (1 << base); x++)
	{
		count.push(0);
	}
	for (var y=0; y<8; y++)
	{
		for (var x=0; x<8; x++)
		{
			var val = tableBases[y][x];
			if(count[val] < (64 >> base))
			{
				count[val]++;
			}
			else
			{
				return false;
			}
		}
	}
	return true;
}

function findCombo(outSquare, oldMagicSquare, oldBaseSquareSet, depth)
{
	// initialize
	var magicSquare = new Array();
	baseSquareSet = oldBaseSquareSet.slice();
	for(var y = 0; y < 8; y++)
	{
		magicSquare.push(new Array());
		for(var x = 0; x < 8; x++)
		{
			magicSquare[y].push(0);
		}
	}
	// iterate through possible base squares randomly until a valid one is found
	while(baseSquareSet.length > 0)
	{
		var randomIndex = Math.floor(Math.random() * baseSquareSet.length);
		var baseSquare = baseSquareSet[randomIndex];
		for(var y = 0; y < 8; y++)
		{
			for(var x = 0; x < 8; x++)
			{
				magicSquare[y][x] = oldMagicSquare[y][x] | baseSquare[y][x];
			}
		}
		if(consecutive(magicSquare, depth))
		{
			// test for validity
			if(depth < 6)
			{
				for(var y = 0; y < 8; y++)
				{
					for(var x = 0; x < 8; x++)
					{
						magicSquare[y][x] <<= 1;
					}
				}
				if(findCombo(outSquare, magicSquare, baseSquareSet, depth + 1))
				{
					return true;
				}
				else
				{
					baseSquareSet.splice(randomIndex, 1);
				}
			}
			else
			{
				// copy
				for(var y = 0; y < 8; y++)
				{
					for(var x = 0; x < 8; x++)
					{
						outSquare[y][x] = magicSquare[y][x];
					}
				}
				return true;
			}
		}
		else
		{
			baseSquareSet.splice(randomIndex, 1);
		}
	}
	return false;
}

//Determines if features selected can be checked and still yield a valid square.
function checkableFeatures(boxId,matrixNum)
{
	if(!document.getElementById(boxId).checked && !document.getElementById(boxId).disabled)
	{
		baseSquareSet = new Array();
		matrix.push(matrixNum);
		// gather valid base squares into baseSquareSet
		for (var y=0; y<baseSquares.length; y++)
		{
			var isValid = true;
			for (var x = 0; x < matrix.length; x++)
			{
				if (features[matrix[x]][y] == 0)
				{
					isValid = false;
					break;
				}
			}
			if (isValid)
			{
				baseSquareSet.push(baseSquares[y]);
			}
		}
		//failure to have enough base squares
		if (baseSquareSet.length < 6)
		{
			disableBox(boxId);
		}
		//determine if there is more than one position that is always zero
		else
		{
			for(var z = 0; z < 8; z++)
			{
				for(var y = 0; y < 8; y++)
				{
					var sum = 0;
					for(var x = 0; x < baseSquareSet.length; x++)
					{
						sum += baseSquareSet[x][y][z];
					}
					if ((y + z > 0) && sum == 0)
					{
						disableBox(boxId);
						matrix.pop();		
						return false;
					}
				}
			}
		}
		matrix.pop();		
	}
}

//Writes the new magic square on the page.
function updateTable()
{
	for (var y=0; y<8; y++) {
		document.getElementById('masterx' + y + 'y' + 0).innerHTML = tableBases[0][y];
		document.getElementById('masterx' + y + 'y' + 1).innerHTML = tableBases[y][0];
		for (var x=0; x<8; x++) {
		document.getElementById('magicx' + x + 'y' + y).innerHTML = (tableBases[y][x] + 1);
		}
	}
}

//Builds a new magic square with the features selected.
function build()
{
	var magicSquare = new Array();
	for(var y = 0; y < 8; y++)
	{
		magicSquare.push(new Array());
		for(var x = 0; x < 8; x++)
		{
			magicSquare[y].push(0);
		}
	}
	var tempBaseSquareSet = baseSquareSet;
	if(findCombo(tableBases, magicSquare, baseSquareSet, 1))
	{
		baseSquareSet = tempBaseSquareSet;
		updateTable();
	}
	else
	{
		alert("Search was unsuccessful. It is not be possible to make a square with this combination of features with the restrictions of this builder.");
	}
}

//Determines which boxes are checked and which boxes are disabled after each check or uncheck.
function checkCompatibility(boxChecked)
{
	for (var index=0; index<featureList.length; index++)
	{
		enableBox(featureList[index]);
	}
	if (document.getElementById(boxChecked).checked == true && (boxChecked == 'selectcomplete' || boxChecked == 'select5x5'))
	{
		document.getElementById('selectcomplete').checked = true;
		document.getElementById('select5x5').checked = true;
	}
	if (document.getElementById(boxChecked).checked == false && (boxChecked == 'selectcomplete' || boxChecked == 'select5x5'))
	{
		document.getElementById('selectcomplete').checked = false;
		document.getElementById('select5x5').checked = false;
	}
	matrix = new Array();
	for (var index=0; index<featureList.length; index++)
	{
		enumerateChecked(featureList[index],index);
	}
	for (var index=0; index<featureList.length; index++)
	{
		checkableFeatures(featureList[index],index);
	}
	// gather valid base squares into baseSquareSet
	baseSquareSet = new Array();
	for (var y=0; y<baseSquares.length; y++)
	{
		var isValid = true;
		for (var x = 0; x < matrix.length; x++)
		{
			if (features[matrix[x]][y] == 0)
			{
				isValid = false;
				break;
			}
		}
		if (isValid)
		{
			baseSquareSet.push(baseSquares[y]);
		}
	}
	build();
}

//resets all buttons to unchecked and enabled
function reset()
{
	for (var index=0; index<featureList.length; index++)
	{
		enableBox(featureList[index]);
	}
	for (var index=0; index<featureList.length; index++)
	{
		uncheckBox(featureList[index]);
	}
	baseSquareSet = baseSquares;
	matrix = new Array();
	build();
}