// File defines what is necesarry for the sudodu solver.
// Copyright by P'tit Yeti (2009)
// Released under a CC-BY-SA-NC licence
// Please contact me (ptityeti@gmail.com) for any other use.
// Solver can be found on http://blog.ptityeti.be/rest/sudoku
//////////////////////////////////////////////////////////////////////////////


// Creation of an object that contains the raster
// Properties:
// N (size of the raster [3 for regular sudoku])
// mogelijkheden (Array containing Arrays with the different remaining possibilities for each field)
// huidig (Array containing the present values in each field, 0 if no value is set)
// minMog (int with the minimum length of mogelijkheden Array for fields with present value 0)
// groepeer (Array with Arrays of the somehow grouped fields [squares, rows and columns])
// groupsOfField (inverse of groepeer; Array with Arrays that for each field give the groups to which it belongs)
//                 the definition of groupsOfField requires more memory but should imply a significant speed-up
// guesses (list of couples with field where guess was made and position of the guess in the mogelijkheden Array)
//
// Methods:
// setValue (sets the value of a certain field)
// unsetValue (unsets the value of a certain field)
// init (initiates the empty raster)
// solve (the name says everything)
// printRaster (quick-and-dirty output of the raster for debugging purpose)
//
//
// Numbering on the raster is as follows: first row with field 0,1,...,N^2-1, second row with fields N^2,...,2*N^2-1, etc.
function raster(N)
{
	this.N=N;
	this.mogelijkheden=new Array(N^4);
	this.huidig=new Array(N^4);
	this.minMog=N^2;
	this.groepeer=new Array(3*N^2);
	this.guesses=new Array();
	this.groupsOfField=new Array(N^4)
	this.setValue=setValue;
	this.unsetValue=unsetValue;
	this.init=init;
	this.solve=solve;
	this.printRaster=printRaster;
}

// function that sets a specific value for a certain point
// input: val=value to set; pos=number of the field to set; fixed=1 if input value, fixed=2 if certain value and fixed=0 if guessed value
// function updates the properties huidig, mogelijkheden en guesses
// function outputs 0 if the choice was invalid and 1 after success
function setValue(val,pos,fixed)
{
	var presentGroups; // contains the groups to which the field belongs
	var group; // iteration variable over the different element in presentGroups
	var i,j;
	var mogPos; // local variable indicating the index of a certain value in some mogelijkheden Array
	var testnow; //
	
	// first of all a check if this value is a valid choice
	presentGroups=this.groupsOfField[pos];
	if(!(this.mogelijkheden[pos].isInArray(val)+1))
	{
		return 0;
	}
	for (i=0;i<presentGroups.length;i++) // loops over all the groups that contain the field pos.
	{
		for(j=0;j<this.groepeer[presentGroups[i]].length;j++) // loops inside each of those groups over the positions in those groups
		{
			testnow=this.groepeer[presentGroups[i]][j];
			if(this.huidig[testnow]==val) // if one of the positions in the group contains the value I would like to set...
			{
				// this should never happen. The pervious if-statement should have returned 0.
				// Means the sudoku is inconsistent.
				alert('Error 2: bug in het algoritme (functie setValue). Gelieve mij de opgegeven sudoku door te sturen, zodat ik dit kan corrigeren.');
				alert('position '+pos+', setting value '+val+'in group '+presentGroups[i]+' that contains the fields '+this.groepeer[presentGroups[i]]);
				return 0;
			}
			//check if any of those positions would result in an empty array mogelijkheden
			// we can not let that happen of course
			if(this.mogelijkheden[testnow].length==1 && this.mogelijkheden[testnow][0]==val && testnow!=pos)
			{
				return 0;
			}
		}
	}
	// OK, valid. Now set the value and update what must be updated.
	// Array mogelijkheden should only be updated for positions with present value 0. 
	//                           Values for all others are considered to be correct!!
	// Start with the element on position pos
	this.huidig[pos]=val;
	mogPos=this.mogelijkheden[pos].isInArray(val);
	switch(fixed)
	{
	case 1:
		geefKleur(pos,"#339933");
		geefCijfer(pos,val);
		break;
	case 2:
		geefKleur(pos,"#33ff33");
		geefCijfer(pos,val);
		break;
	default:
		geefKleur(pos,"#cccccc");
		geefCijfer(pos,val);
	}
	// if it is  a guess (i.e. if fixed is 0) the array guesses must be updates, else it must be emptied
	if(fixed==0)
	{
		nextguess=new Array();
		nextguess[0]=pos;
		nextguess[1]=mogPos
		this.guesses.push(nextguess);
	}
	else // should in fact have happened due to array.pop() when correcting a guess, but it doesn't harm to write it expecitely.
	{
		this.guesses=new Array()
	}
	// iterate over groups containing pos
	for (i=0;i<presentGroups.length;i++)
	{
		// iterate over the positions in each group
		for(j=0;j<this.groepeer[presentGroups[i]].length;j++)
		{
			testnow=this.groepeer[presentGroups[i]][j];
			mogPos=this.mogelijkheden[testnow].isInArray(val);
			if(mogPos>=0 && !this.huidig[testnow])
			{
				this.mogelijkheden[testnow].splice(mogPos,1);
			}
		}
	}
	// if it is one of the certanities, remove the array mogelijkheden entirely
	if (fixed)
	{
		this.mogelijkheden[pos]= new Array();
	}
	return 1;
}


// Function to unset the guesses
// This implies: * setting the value of huidig[pos] to 0
//               * removing the last element from the Array guesses
//               * adding the value again to the array mogelijkheden for positions in same group as pos with value 0 in huidig
function unsetValue(pos)
{
	var val; // value at position pos that will be unset
	var laatste; // the final element of the array guesses
	var group; // iteration variable over the different groups that contain pos
	var i,j,k,l; // iteration variable in each group
	var testnow; // position that is currently being checked
	var somewherePresent; //indicates if occurence remains prohibited due to otherwise imposed restrictions
	val=this.huidig[pos];
	this.huidig[pos]=0;
	geefKleur(pos,"#cccccc"); // arrange colorfull output
	geefCijfer(pos,"");
	laatste=this.guesses.pop();
	if (this.mogelijkheden[pos][laatste[1]]!=val)
	{
		alert('Error 3: Ola, dat kan niet. Er is blijkbaar een probleem in het algoritme (functie unsetValue)');
		return "";
	}
	// iteration over the groups that contain pos
	for (j=0;j<this.groupsOfField[pos].length;j++)
	{
		group=this.groupsOfField[pos][j];
		// iteration inside the group
		for(i=0;i<this.groepeer[group].length;i++)
		{
			testnow=this.groepeer[group][i];
			// the array mogelijkheden was only changed for positions with 0 as present value
			// so for unsetting we only have to consider those same positions (excluding the position pos)
			if(!this.huidig[testnow] && testnow != pos)
			{
				// Check if possibility is not yet present. This can happen if testnow has more than one group in common with pos
				if ( this.mogelijkheden[testnow].isInArray(val) == -1 )
				{
					// OK, now I know that testnow is not pos and val is not present in the array mogelijkheden
					// Now we have to add val to mogelijkheden ONLY AND ONLY IF no other restriction inhibits the presence of val in mogelijkheden
					// So first check if any position having a group in common with testnow has at present the value val
					somewherePresent=0; // indicates if val is somewhere present; inhibiting its occurence in testnow
					// Loop over the groups that contain testnow
					for (k=0;k<this.groupsOfField[testnow].length;k++)
					{
						// Loop over the positions in this group
						for(l=0;l<this.groepeer[this.groupsOfField[testnow][k]].length;l++)
						{
							// Check the present value at this position
							if(this.huidig[this.groepeer[this.groupsOfField[testnow][k]][l]]==val)
							{
								somewherePresent=1;
							}
						}
					}
					// if we didn't find val somewhere, include it in the array mogelijkheden
					if(!somewherePresent)
					{
						this.mogelijkheden[testnow].push(val);
						this.mogelijkheden[testnow].sort();
					}
				}
			}
		}
	}
}

// Function that initiates an empty raster
// The input is an Array with the given fields of the form [[field nr., value],[field nr., value],...,[field nr., value]]
// function returns 1 on success and 0 if it was unable to set the input values
function init(input)
{
	var i,j,k,l;
	var Ngroup,Nfield;
	var N2=this.N*this.N; //N^2
	var N3=this.N*N2; // N^3;
	var N4=N2*N2; //N^4
	// initiate the different Arrays
	for(i=0;i<N4;i++)
	{
		this.mogelijkheden[i]=new Array();
		for (j=1;j<=N2;j++)
		{
			this.mogelijkheden[i][j-1]=j;
		}
		this.huidig[i]=0;
		this.groepeer[i]=new Array();
		this.groupsOfField[i]=new Array()
	}
	// construct the different groups of fields
	// construct the subsquares
	// two outermost loops loop over the N^2 subsquares
	for (i=0;i<this.N;i++)
	{
		for(j=0;j<this.N;j++)
		{
			//two innermost loops loop inside subsquare N*j+i-1
			for(k=0;k<this.N;k++)
			{
				for(l=0;l<this.N;l++)
				{
					// upperleft field of each square is i*N^3+j*N
					// shifting k rows lower moves k*N^2 positions
					// shifting l columns to the right moves l positions
					Ngroup=this.N*j+i;
					Nfield=i*N3+k*N2+j*this.N+l;
					this.groepeer[Ngroup][k*this.N+l]=Nfield;
					this.groupsOfField[Nfield].push(Ngroup);
				}
			}
		}
	}
	// construct the different rows
	for (i=0;i<N2;i++)
	{
		for (j=0;j<N2;j++)
		{
			Ngroup=N2+i;
			Nfield=i*N2+j;
			this.groepeer[Ngroup][j]=Nfield;
			this.groupsOfField[Nfield].push(Ngroup);
		}
	}
	// construct the different columns
	for (i=0;i<N2;i++)
	{
		for (j=0;j<N2;j++)
		{
			Ngroup=2*N2+i;
			Nfield=j*N2+i;
			this.groepeer[Ngroup][j]=Nfield;
			this.groupsOfField[Nfield].push(Ngroup);
		}
	}
	// set output sudoku to empty one graphically
	for (i=0;i<N4;i++)
	{
		veldId="soltd"+i;
		veldNu=document.getElementById(veldId);
		veldNu.innerHTML="&nbsp;";
	}
	
	// this was the initialisation as zero
	// now set the different values from the input!
	for (i=0;i<input.length;i++)
	{
		koppel=input[i];
		if(!this.setValue(koppel[1],koppel[0],1))
		{
			alert('De opgegeven sudoku is ongeldig!!');
			return 0;
		}
	}
	return 1;
}// end of the init function

// function that checks if an element belongs to an array
// returns the position of the element and -1 if element is not found
Array.prototype.isInArray=isInArray;
function isInArray(needle)
{
	var i;
	for(i=0;i<this.length;i++)
	{
		if(this[i] == needle)
		{
			return i;
		}
	}
	return -1;
}

// function that solves the sudoku and takes care of the output.
// This is where all the action is happening! Yieha.
//
// Outline of the algoritm:
// * Check if for a certain position only one value is possible. Repeat this in a while loop until nothing changes any more
// * Try to fill out positions by elemination (check if in a group a certain value can only occur on one position)
// * After this check if a guess has to be made
// * Check where the number of possibilities is minimal
// * Sort the positions by number of possibilties and store this in an array
// * Start making guesses from position with minimal possibilities an move up the array with positions.
function solve()
{
	var position,minimum; // indicate position and #possibilities for optimal place
	var i,j,m;
	var k=0; // times I have been guessing at a certain position
	var vorige=-1,vorigeval;
	var nogwerk=0;
	var N2=this.N*this.N;
	var N4=N2*N2;
	var Nmog,testnu,testnuval; // needed when removing guesses
	var possibleValues; // array with the possible value for a certain point
	var doEleminate; // checks if I should proceed with the method of elimination
	var didAction; // checks if a certainity has been filled out
	var inNGroups,posNr,testpos; // variables used in method of elemination
	var l=0; // testing variable
		// firstly, check if the raster is not completed
		nogwerk=0;
		for(j=0;j<N4;j++)
		{
			if(!this.huidig[j])
			{
				nogwerk=1;
			}
		}
		// if everything is filled out, return 1
		if(!nogwerk)
		{
			return 1;
		}
/*
		// First part of the algoritm
		// Loop over all positions and check if multiple values are possible
		didAction=1;
		while(didAction)
		{
			didAction=0;
			for(i=0;i<N4;i++) //loop over all points
			{
				if(!this.huidig[i]) // check if value is not yet set
				{
					possibleValues=Array();
					for(j=0;j<N2;j++)
					{
						possibleValues[j]=j+1;
					}
					for(j=0;j<this.groupsOfField[i].length;j++) //loop over all groups in which the point is contained
					{
						for(k=0;k<N2;) //loop over all the point that share group j with point i
						{
							if(this.huidig[this.groepeer[this.groupsOfField[i][j]][k]]) // check if point to test has a value
							{
								for(l=0;l<possibleValues.lenght;l++)
								{
									if(possibleValues[l]==this.huidig[this.groepeer[this.groupsOfField[i][j]][k]])
									{
										possibleValues.splice(l,1); //remove the element from possibleValues
									}
								}
							}
						}
					}
					//If only one value possible, fill it out
					if(possibleValues.length==1)
					{
						this.setValue(possibleValues[0],i,2);
						didAction=1;
					}
				}
			}
		}
*/
		//Fill out the parts that are certain
		//the code for decision by elemination
		didAction=1;
		while(didAction)
		{
			didAction=0;
			doEleminate=1;
			while(doEleminate)
			{
				doEleminate=0;
				for(i=0;i<this.groepeer.length;i++) // loop over all groups
				{
					for(j=1;j<=N2;j++) // loop over all possible values
					{
						inNGroups=0;
						for(m=0;m<this.groepeer[i].length;m++) // loop over all postions in the group
						{
							testpos=this.groepeer[i][m];
							if(this.huidig[testpos]==0 && this.mogelijkheden[testpos].isInArray(j)>=0) // if position is not yet set and tested value is in array mogelijkheden
							{
								inNGroups++;
								posNr=testpos;
							}
						}
						if(inNGroups==1)
						{
							if(!this.setValue(j,posNr,2))
							{
								alert('Ongeldige Sudoku!');
								return 0;
							}
							doEleminate=1; //something has changed, so we should start over at the end
						}
					}
				}
			}
			// Fill out the places where the array mogelijkheden contains only one element
			doCertain=1;
			while(doCertain)
			{
				doCertain=0;
				for(i=0;i<N2;i++)
				{
					for(j=0;j<N2;j++)
					{
						if(this.huidig[i*N2+j]==0 && this.mogelijkheden[i*N2+j].length==1)
						{
							// set the value!
							if(this.setValue(this.mogelijkheden[i*N2+j][0],i*N2+j,2))
							{
								doCertain=1;
							}
							else
							{
								alert('Ongeldige sudoku!');
								return 0;
							}
						}
					}
				}
			}
			
		}// end of outermost while
		
		
		// if the certain methods do not work (anymore) take the method of guessing

		// before starting the method by guessing, check if something remains to be done
		//alert('begin guessing');
		nogwerk=0;
		for(j=0;j<N4;j++)
		{
			if(!this.huidig[j])
			{
				nogwerk=1;
			}
		}
		// if everything is filled out, return 1
		if(!nogwerk)
		{
			return 1;
		}
		// Create an array with the order in which the guesses will be made.
		// This is from the points which have at this moment shortest array mogelijkheden, to the points where this array is at the moment the longest.
		// Order will not change afterwards. This is not optimal, but the easiest way to make sure we do not guess at the same position over and over again.
		makeOrder=new Array(); // array with subarrays that group positions with same mogelijkheden.length.
		for(i=0;i<N2-1;i++)
		{
			makeOrder[i]=new Array();
		}
		// loop over all points and put them in the right subarray
		for(i=0;i<N2;i++)
		{
			for(j=0;j<N2;j++)
			{
				if(this.huidig[i*N2+j]==0)
				{
					makeOrder[this.mogelijkheden[i*N2+j].length - 2].push(i*N2+j);
				}
			}
		}
		// make a long array out of all the subarrays
		isOrder = new Array();
		for(i=0;i<N2-1;i++)
		{
			for(j=0;j<makeOrder[i].length;j++)
			{
				isOrder.push(makeOrder[i][j]);
			}
		}

		// OK, I know how I will make the guesses
		nogwerk=1;
		guessPos=0; // position in the array isOrder at which I am guessing.
		guessNr=0; // position in the array mogelijkheden at which I am guessing
		lastChance=-1; // position in the array isOrder at which I tried the very last possibility
		while(nogwerk)
		{
			if(guessPos==isOrder.length)
			{
				//everything is filled out!!
				nogwerk=0;
				return 1;
			}
			if(guessPos <= lastChance+1 && guessNr+1 >= this.mogelijkheden[isOrder[guessPos]].length)
			{
				lastChance++;
			}
			//check if guessNr is not to high
			if(guessNr < this.mogelijkheden[isOrder[guessPos]].length)
			{
				if(this.setValue( this.mogelijkheden[isOrder[guessPos]][guessNr] , isOrder[guessPos] , 0))
				{
					// guess is possible, make guess at next position
					guessPos++;
					guessNr=0;
				}
				else
				{
					if(guessNr < this.mogelijkheden[isOrder[guessPos]].length-1)
					{
						// if I can make another guess at this position
						guessNr++;
					}
					else
					{
						if(!guessPos || guessPos-1 <= lastChance)
						{
							// No way to move a position back
							alert('Ongeldige sudoku');
							return 0;
						}
						// if I have to move a position back
						guessPos--;
						guessValue=this.huidig[isOrder[guessPos]];
						this.unsetValue(isOrder[guessPos]);
						guessNr=this.mogelijkheden[isOrder[guessPos]].isInArray(guessValue) +1;
					}
				}
			}
			else // if guessNr is to high => unset and move back a position
			{
				if(!guessPos || guessPos-1 <= lastChance)
				{
					// No way to move a position back
					alert('Ongeldige sudoku');
					return 0;
				}
				// if I have to move a position back
				guessPos--;
				guessValue=this.huidig[isOrder[guessPos]];
				this.unsetValue(isOrder[guessPos]);
				guessNr=this.mogelijkheden[isOrder[guessPos]].isInArray(guessValue) +1;
			}
		}
}

// Function to output the raster
// No fancy output, just the different rows
// Only for debugging purpose
// Returns a string with htlm
// Disadvantage: destroys the raster, so only to be used of the end of what needs to be tested.
function printRaster()
{
	var row;
	var output="";
	var stop=this.N*this.N;
	for (i=0;i<stop;i++)
	{
		row=this.huidig.splice(0,stop);
		output+=row.join("-")+"<br />";
	}
	return output;
}

// function to hide and display the solution raster
// Input: boolean that indicates whether solution should be hidden or displayed
function zieOplossing(ja)
{
	sol=document.getElementById("solcontainer");
	if(ja)
	{
		sol.style.visibility="visible";
	}
	else
	{
		sol.style.visibility="hidden";
	}
}

// adapts the color in the solution raster
function geefKleur(veld,kleur)
{
	var veldId;
	var veldNu;
	veldId="soltd"+veld;
	veldNu=document.getElementById(veldId);
	veldNu.style.backgroundColor=kleur;
}

// adapts the value in the solution raster
function geefCijfer(veld,value)
{
	var veldId;
	var veldNu;
	veldId="soltd"+veld;
	veldNu=document.getElementById(veldId);
	veldNu.innerHTML=value;
}

// Function that reads the form
// Returns an array of the form [[pos,value],[pos,value],...,[pos,value]] as required by the function init()
function readInput(N)
{
	var N2=N*N;
	var N4=N2*N2;
	var i;
	var tempInput;
	var fieldNu;
	var inputArray=new Array();
	var subArray;
	for (i=0;i<N4;i++)
	{
		fieldNu=document.getElementById("formfield"+i);
		tempInput=Math.round(fieldNu.value);
		if (tempInput>0 && tempInput<=N2)
		{
			subArray=new Array();
			subArray[0]=i;
			subArray[1]=tempInput;
			inputArray.push(subArray);
		}
	}
	return inputArray;
}


// Finally the function that does all the work
function findSolution(N)
{
	rooster=new raster(N);
	if(rooster.init(readInput(N)))
	{
		zieOplossing(1);
		rooster.solve();
	}
}