//// Javascript für die Erstellung eines Sudokus (inkl. Hilfsfunktionen) siehe 
//// http://heuscher.ch/Sudoku

// Einstellungen
delay = 10;//200; // in Milisekunden 
working = false; // ist true, wenn gerade etwas läuft
sudokuRegisterUrl = "http://heuscher.ch/~twiki/Main/Heuscher/Steve/Public/WebHome/SudokuRegister/";
randomSudokuUrl = "http://heuscher.ch/~twiki/Main/Heuscher/Steve/Public/WebHome/SudokuRegister/ajaxRandomSudoku.php";

// lösungsstack, die SudokuDaten und Geschichte initialisieren
solveHistory = new Array();
SudokuHistory = new Array();
emptySudoku = new Array();


singleNumber = "singleNumber";
uniqueInRow = "uniqueInRow";
uniqueInBox = "uniqueInBox";
uniqueInCol = "uniqueInCol";

// hält fest, ob eine Taste gedrückt ist
keyDown = false;

// keyboard events registieren
function onKeyDown(event) 
{
  setKeyStatus(event, false)
}
document.onkeydown = onKeyDown;

function onKeyUp(event) 
{
  setKeyStatus(event, true)
}
document.onkeyup = onKeyUp;

function setKeyStatus(event, keyUp)
{
  keyDown = !keyUp;
}

// sudoku daten füllen
for (var Zeile = 0; Zeile < 9; Zeile++)
{
  emptySudoku[Zeile] = new Array();
  for (var Zelle = 0; Zelle < 9; Zelle++)
  {
	 emptySudoku[Zeile][Zelle] = new Array();
	 for (var Zahl = 0; Zahl < 9; Zahl++)
	 {
		 emptySudoku[Zeile][Zelle][Zahl] = Zahl + 1;
	 }
  }
}

SudokuDaten = deepCopyArray(emptySudoku);


// vergleicht arrays aufgrund ihres inhalts
Array.prototype.compareArrays = function(arr) {
	 if (this.length != arr.length) return false;
	 for (var i = 0; i < arr.length; i++) {
		  if (this[i] != null && this[i].compareArrays) { //likely nested array
				if (!this[i].compareArrays(arr[i])) return false;
				else continue;
		  }
		  if (this[i] != arr[i]) return false;
	 }
	 return true;
}

// kopiert rekursiv arrays
function deepCopyArray(arrayToCopy) 
{
  if ( arrayToCopy == null )
  {
	 //alert ("deepCopyArray mit null aufgerufen");
	 return null;
  }
  var copyArray= new Array();
  for(var i = 0; i < arrayToCopy.length; i++) 
  {
	 copyArray[i] = arrayToCopy[i];
	 //if (i==0) alert( typeof copyArray[i]);
	 if (typeof arrayToCopy[i] == typeof arrayToCopy)
	 {
		copyArray[i] = deepCopyArray(copyArray[i]);
	 }
  }
  return copyArray;
}


// führt das model nach und updatet die view
function setNumber(x,y,number, sudokuStatus, showHints, updateViewAfterCalculation) 
{
  //alert('Setting node ' + y +', '+ x + ' to value:' + number );
  if (typeof number != 'number' && number.match(/[1-9]/) == null)
  {
	 //alert("bitte eine Zahl eingeben; number:" + number +", typeof number:"+typeof number);
	 return;
  }
  SudokuHistory[SudokuHistory.length] = deepCopyArray(SudokuDaten);
  
  setNumberInData(x,y,number, SudokuDaten);
  
  if (updateViewAfterCalculation != null && updateViewAfterCalculation)
  {
	 updateView(sudokuStatus, showHints);
  }
}

function setNumberInData(x,y,number, data) 
{
  for(var i = 0; i < 9; i++) {
	 data[i][x][number-1] = null;
	 data[y][i][number-1] = null;
	 data[Math.floor(y /3) * 3 + i % 3][Math.floor(x /3) * 3 + Math.floor(i / 3)][number-1] = null;
  }
  // resultat setzen
  data[y][x] = new Array();
  data[y][x][number-1] = number;
  data[y][x][9] = number;
}

// führt das model nach und updatet die view
function clearNumber(x,y,number) 
{
  //alert('Setting node ' + y +', '+ x + ' to value:' + number );
  if (typeof number != 'number' && number.match(/[1-9]/) == null)
  {
	 //alert("bitte eine Zahl eingeben; number:" + number +", typeof number:"+typeof number);
	 return;
  }
  SudokuHistory[SudokuHistory.length] = deepCopyArray(SudokuDaten);
  SudokuDaten[y][x][number-1] = null;

  updateView();
}


// updatet die view nach dem jetztigen Model
function updateView(uniqueNumbersFound, showHints) 
{
  for(var i = 0; i < 9; i++) {
	 for(var j = 0; j < 9; j++) {
		var table1to9 = document.getElementById("t" + i + '' + j);
		var parent = table1to9.parentNode; 
		var filledNumber = parent.getElementsByTagName("span")[0];
		var filledNumberText = filledNumber.firstChild;
		// alert('i:' + i + '; j:' + j + '; table:' + table1to9); 
		var tdNodes = table1to9.getElementsByTagName("td");
		var numberOfNumbers = 0;

		filledNumberText.data = " ";
		table1to9.style.zIndex = 1;
		filledNumber.style.zIndex = -1;
		parent.style.background = "#FFF";
		for(var k = 0; k < tdNodes.length; k++) {
		  tdNodes[k].style.background = "transparent";
		  numberLinkText = tdNodes[k].firstChild.firstChild;
		  if (SudokuDaten[i][j][9] == null)
		  {
			 if (SudokuDaten[i][j][k] != null) {
				numberOfNumbers++;
				numberLinkText.data = SudokuDaten[i][j][k];
			 }
			 else
				{
				numberLinkText.data = " ";
			 }
		  }
		  else
		  {
			 numberOfNumbers = 1;
			 numberLinkText.data = " ";
		  }
		}
		if (numberOfNumbers == 0)
		{
		  parent.style.background = "#F88";
		  return;
		}
		if (!(SudokuDaten[i][j][9] == null)) 
		{
		  filledNumberText.data = SudokuDaten[i][j][9];
		  parent.style.background = "#FFF";
		  table1to9.style.background = "#FFF";
		  table1to9.style.zIndex = -1;
		  //filledNumber.style.background = "#FFF";
		  filledNumber.style.zIndex = 1;
		}
	 }
  }
  if (uniqueNumbersFound != null)
  {
	 if (uniqueNumbersFound != null)
	 {
		for (var i = 0; i < uniqueNumbersFound.length; i++)
		{
		  var numberFound = uniqueNumbersFound[i];
		  var table1to9 = document.getElementById("t" + numberFound[1] + '' + numberFound[0]);
		  var parent = table1to9.parentNode; 
		  var tdNodes = table1to9.getElementsByTagName("td");
		  if (showHints != null)
		  {
			 tdNodes[numberFound[2] - 1].style.background = "#2F2";
			 parent.style.background = "#9F9";
		  }
		}
	 }
  }
  updateDisplayedStatus();
}

function updateDisplayedStatus() 
{
  var webroot = location.href;
  var search = location.search;
  var sudokuNumber = getSudokuNumber(SudokuDaten);
  if(search != null)
  {
	 webroot = webroot.substr(0, webroot.indexOf("?"));
  }
  var permalink = document.getElementById("permalinkSudoku");
  if (permalink != null)
  {
	 var permalinkHref = webroot + '?source=permalink&sudoku=' + escape(sudokuNumber) + "#sudoku";
	 permalink.setAttribute("href", permalinkHref);
  }
  var statusField = document.getElementById('status');
  if (statusField != null)
  {
	 statusField.value = sudokuNumber;
  }
  var difficultyField = document.getElementById('remainingDifficulty');
  if (difficultyField != null && document.getElementById('getDifficulty') != null)
  {
	 var justNumbers = sudokuNumber.replace(/[^0-9]/g, "0");
	 setTimeout("if (working == false) document.getElementById('remainingDifficulty').firstChild.data = (new Board().solve(15,'"+justNumbers+"')) + '';", delay);
  }
}
// macht in der history einen schritt zurück und zeigt den stand an. 
function goBack () 
{
  if (SudokuHistory.length == 0)
  {
	 return;
  }
  SudokuDaten = SudokuHistory[SudokuHistory.length -1];
  updateView();
  SudokuHistory.length = SudokuHistory.length -1 ;
}

// setzt das sudoku auf den ausgangsstand zurück
function clearSudoku () 
{
  if (SudokuHistory.length == 0)
  {
	 return;
  }
  SudokuHistory.length = 1 ;
  goBack ();
}

// gibt zurück, ob das sudoku legal ist (array mit eindeutigen Zahlen)
// sonst null (-> in einem Feld kann keine Zahl mehr vorkommen)
function getSudokuStatus (data) 
{
  if (data == null)
  {
	 data = SudokuDaten;
  }
  var uniqueNumbersFound = new Array();
  var numbersInRows =  new Array();
  var numbersInColumns =  new Array();
  var numbersInBlocks =  new Array();
  // leere arrays für löser generieren 
  // zugriff: numbersInBlocks[0][1] = Array von Arraxys(Numberfound[x][y][nummer]), welche 1 enthalten)
  for(var i = 0; i < 9; i++) 
  {
	 numbersInRows[i] =  new Array();
	 numbersInColumns[i] =  new Array();
	 numbersInBlocks[i] =  new Array();
	 for(var j = 1; j < 10; j++) 
	 {
		numbersInRows[i][j] =  new Array();
		numbersInColumns[i][j] =  new Array();
		numbersInBlocks[i][j] =  new Array();
	 } 
  }
  for(var i = 0; i < 9; i++) 
  {
	 for(var j = 0; j < 9; j++) 
	 {
		var numbersPresent = 0;
		var onlyNumber = null;
		for(var k = 0; k < 9; k++) 
		{
		  if ( data[i][j][k] != null) {
			 numbersPresent++;
			 onlyNumber = data[i][j][k];
			 if (data[i][j][9] == null)
			 {
				numbersInRows[i][onlyNumber].push(new Array(j,i,onlyNumber, uniqueInRow));
				numbersInColumns[j][onlyNumber].push(new Array(j,i,onlyNumber, uniqueInCol));
				numbersInBlocks[Math.floor(j / 3) + 3 * Math.floor(i / 3)][onlyNumber].push(new Array(j,i,onlyNumber, uniqueInBox));
			 }
		  }
		}
		// check ob der status legal ist
		if (numbersPresent == 0)
		{
		  /*var table1to9 = document.getElementById("t" + i + '' + j);
		  var parent = table1to9.parentNode; 
		  parent.style.background = "#F88";
		  //alert ("keine nummer in " + i +", "+j+" gefunden: " + data[i][j]);
		  */
		  return null;
		}
		if (numbersPresent == 1 && data[i][j][9] != onlyNumber)
		{
		  // alert('Nummer gefunden: '+ onlyNumber);
		  var numberFound = new Array(j,i,onlyNumber,singleNumber);
		  uniqueNumbersFound[uniqueNumbersFound.length] = numberFound;
		}
	 }
  }
  for(var i = 0; i < 9; i++) 
  {
	 for(var j = 1; j < 10; j++) 
	 {
		if (numbersInColumns[i][j].length == 1)
		{
		  //alert('Nummer '+j+' in Spalte '+i+' gefunden: '+ numbersInColumns[i][j][0]);
		  addUniqueNumberIfNotPresent(uniqueNumbersFound, numbersInColumns[i][j][0]);
		}
		if (numbersInBlocks[i][j].length == 1)
		{
		  //alert('Nummer '+j+' in Block '+i+' gefunden: '+ numbersInBlocks[i][j][0]);
		  addUniqueNumberIfNotPresent(uniqueNumbersFound, numbersInBlocks[i][j][0]);
		}
		if (numbersInRows[i][j].length == 1)
		{
		  //alert('Nummer '+j+' in Zeile '+i+' gefunden: '+ numbersInRows[i][j][0]);
		  addUniqueNumberIfNotPresent(uniqueNumbersFound, numbersInRows[i][j][0]);
		}
	 }
  }
  return uniqueNumbersFound;
}

function addUniqueNumberIfNotPresent(uniqueNumbersFound, newUniqueNumber)
{
  var isDuplicate = false;
  for(var i = 0; !isDuplicate && i < uniqueNumbersFound.length; i++) 
  {
	 isDuplicate = (uniqueNumbersFound[i][0] == newUniqueNumber[0] && uniqueNumbersFound[i][1] == newUniqueNumber[1] && uniqueNumbersFound[i][2] == newUniqueNumber[2]);
  }
  if (isDuplicate)
  {
	 return;
  }
  else
  {
	 uniqueNumbersFound.push(newUniqueNumber);
  }
}

function backtrackPopupText()
{
  return "Der Startpunkt führt nicht zu einer Lösung.\nIhre letzte Eingabe wird zurückgenommen.";
}
// löst rekursiv das sudoku
// der status der rekursion wird in der variable solveHistory gehalten
// wieder-aufruf durch timer
function solveSudoku()
{
  working = true;
  var uniqueNumbersFound = getSudokuStatus();
  updateView(uniqueNumbersFound, true);
  if (uniqueNumbersFound == null)
  {
	 goBack();
	 if (solveHistory.length > 0)
	 {
		var lastSet = solveHistory[solveHistory.length-1];
		SudokuDaten[lastSet[1]][lastSet[0]][lastSet[2]-1] = null;
		solveHistory.length = solveHistory.length - 1;
		//alert("Solution not found, backtracking. solveHistory.length: "+solveHistory.length +"; last set:" + lastSet);
	 }
	 else
	 {
		alert(backtrackPopupText());
	 }
	 setTimeout("solveSudoku()", delay);
	 return;
  }
  var hasUniqueNumbers = false;
  var oldSudokuHistory = deepCopyArray(SudokuHistory);
  //alert("solveHistory.length: "+solveHistory.length +"; uniqueNumbersFound.length: " + uniqueNumbersFound.length);
  while (uniqueNumbersFound.length > 0)
  {
	 hasUniqueNumbers = true;
	 var nextNumber = uniqueNumbersFound[uniqueNumbersFound.length -1];
	 uniqueNumbersFound.length = uniqueNumbersFound.length -1;
	 setNumber(nextNumber[0],nextNumber[1],nextNumber[2]);
  }
  if (hasUniqueNumbers)
  {
	 // die automatisch gefundenen Zahlen gelten nicht als Eintrag in der History, sie sind
	 // mehr die logische Fortsetzung der gesetzten Zahl, weshalb die history zurückgesetzt wird
	 SudokuHistory = oldSudokuHistory;
	 setTimeout("solveSudoku()", delay);
	 return;
  }
  for(var i = 0; i < 9; i++) 
  {
	 for(var j = 0; j < 9; j++) 
	 {
		for(var k = 0; SudokuDaten[i][j][9] == null && k < 9; k++) 
		{
		  if ( SudokuDaten[i][j][k] != null) {
			 nextRecursion(new Array(j,i,k+1));
			 return;
		  }
		}
	 }
  }
  updateView();
  working = false;
}

// setzt die nächste rekursion auf
function nextRecursion(nextSetNumber, uniqueNumbersFound)
{
  //alert("nextRecursion, nextSetNumber[0]: "+nextSetNumber[0]+", nextSetNumber[1]: "+nextSetNumber[1]+", nextSetNumber[2]: "+nextSetNumber[2]+", ");
  solveHistory[solveHistory.length] = nextSetNumber;
  setNumber(nextSetNumber[0],nextSetNumber[1],nextSetNumber[2], uniqueNumbersFound, true, true);
  setTimeout("solveSudoku()", delay);
}

// füllt "rekursiv" die eindeutigen Felder
// wieder-aufruf durch timer
function fillUniqueFields(callFromTimer) 
{
  working = true;
  var uniqueNumbersFound = getSudokuStatus();
  if (callFromTimer == false && uniqueNumbersFound != null && uniqueNumbersFound.length > 0)
  { 
	 SudokuHistory[SudokuHistory.length] = deepCopyArray(SudokuDaten);
	 oldSudokuHistory = deepCopyArray(SudokuHistory)
  }
  if (uniqueNumbersFound != null && uniqueNumbersFound.length > 0)
  {
	 updateView(uniqueNumbersFound, true);
	 while (uniqueNumbersFound.length > 0)
	 {
		var nextNumber = uniqueNumbersFound[uniqueNumbersFound.length -1];
		uniqueNumbersFound.length = uniqueNumbersFound.length - 1;
		setNumber(nextNumber[0], nextNumber[1], nextNumber[2]);
	 }
	 setTimeout("fillUniqueFields(true)", delay);
	 return;
  }
  updateView();
  SudokuHistory = oldSudokuHistory;
  working = false;
}

// füllt die in location.search vor-definierten oder übergebenen felder aus 
function fillPredefinedNumbers(definitionString)
{
  working = true;
  clearSudoku();
  SudokuHistory[SudokuHistory.length] = deepCopyArray(SudokuDaten);
  oldSudokuHistory = deepCopyArray(SudokuHistory)
  if (definitionString == null)
  {
	 //alert("location.search : " + location.search);
	 definitionString = unescape(location.search);
	 definitionString = definitionString.replace(/^[^- 0-9]*(sudoku=)?/gi,"");
	 //alert("definitionString : " + definitionString);
  }
  if (definitionString.indexOf("=") < 0)
  {
	 var deletedNumbersStringArray = (definitionString).split(" ");
	 var deletedNumbersArray = new Array();
	 if(deletedNumbersStringArray.length == 2)
	 {
		deletedNumbersArray = deletedNumbersStringArray[1].split("-").reverse();
		//alert(deletedNumbersArray);
		// kill first empty string ("-3-2".split("-") -> ["", "3", "2"])
		deletedNumbersArray.pop();
	 }
	 // set the selected numbers and gather the deleted ones (still encoded)
	 for(var i = 0; i < 81; i++)
	 {
		var x = i % 9;
		var y = Math.floor(i / 9);
		var valueCellEncoded = definitionString.substr(i, 1);
		if(valueCellEncoded.match(/[1-9]/) != null)
		{
			setNumberInData(x,y, valueCellEncoded, SudokuDaten);
		}
		else if(valueCellEncoded == "-")
		{
		 var deletedNumbers = deletedNumbersArray.pop().split("");
		 //alert(deletedNumbers);
		 for(var j = 0; j < deletedNumbers.length; j++)
			{
			 removeNumberInData(x,y,deletedNumbers[j],SudokuDaten);
		  }
		}
	 }
  }
  else
  {
	 if (definitionString != null && definitionString.length > 0)
	 {
		for(var lastI = 0; lastI < 9; lastI++) 
		{
		  for(var lastJ = 0; lastJ < 9; lastJ++) 
		  {
			 var coord = (lastJ+1)+''+(lastI+1);
			 var coordIndex = definitionString.indexOf(coord) ;
			 if ( coordIndex> 0)
			 {
				setNumber(lastI,lastJ, definitionString.substr(coordIndex + 3, 1));
			 }
		  }
		}
	 }
  }
  updateView();
  SudokuHistory = oldSudokuHistory;
  working = false;
}

function removeNumberInData(x,y,number,data)
{
	if (typeof number != 'number' && number.match(/[1-9]/) == null)
	{
		return;
	}
	data[y][x][number-1] = null;
}

function setBackground(sudokuNumberElement)
{
	var filledNumber = sudokuNumberElement.firstChild.nodeValue;
	if (filledNumber != null && filledNumber.match(/[1-9]/) != null)
	{
		if (keyDown)
		{
			 sudokuNumberElement.style.background = "#F99";
		}
		else
		{
			 sudokuNumberElement.style.background = "#9F9";
		}
	}
}


function clearBackground(sudokuNumberElement)
{
	sudokuNumberElement.style.background = "transparent";
}

// Background-Farben um komplexe Abhängikeiten zu markieren
var colorForNumber = new Array();
colorForNumber[0] = "";
colorForNumber[1] = "#665CCC";
colorForNumber[2] = "#837CCC";
colorForNumber[3] = "#D4C91E";
colorForNumber[4] = "#A39D38";
colorForNumber[5] = "#8F870B";
colorForNumber[6] = "#EBE156";
colorForNumber[7] = "#D48D1E";
colorForNumber[8] = "#A37938";
colorForNumber[9] = "#8F5B0B";

// hier werden die tabellen erstellt
// die internen tabellen stellen die möglichen Zahlen dar und sie sind über
// die id tXY identifiziert
document.writeln('<table class="sudokuTable" style="border: 3px #000 solid; border-collapse: collapse; margin-left:auto; margin-right:auto;">');
for(i = 0; i < 9; i++) {
  document.writeln('<tr style="border: 0px;">');
  for(j = 0; j < 9; j++) {
	 document.write('<td style="border: 1px #000 solid; '); 
	 if (j % 3 == 0 && j != 0)
	 {
		document.write('  border-left: 3px #000 solid; ');
	 }
	 if (i % 3 == 0 && i != 0)
	 {
		document.write('  border-top: 3px #000 solid; ');
	 }
	 document.write('"><span style="z-index:-1; position:absolute; padding-left:0.4em; padding-top:0.55em; font-size:24pt; font-weight:bold; font-family: courier new, fixed; ">&nbsp;</span>');
	 document.write('<table style="z-index:0; empty-cells:show; font-size:11pt; line-height: 85%; border: 0px #000 solid; border-collapse: collapse;" ');
	 document.write('  id="t'+ i + '' + j +'">');
	 for (var k=0; k<3; k++)
	 {
		document.writeln('<tr style="border: 0px #000 solid; border-collapse: collapse;">');
		for (var l=0; l<3; l++)
		{ // TODO font family überprüfen
		  var number = k * 3 + l + 1;
		  document.write('<td style="height:1.3em; width:1em; border: 0px #FFF solid; padding: 0px; margin: 0px;  border-collapse: collapse; font-family: courier new, fixed;">');
		  document.write('<a class="sudoku" style="display:block; margin: 0px; padding: 2px; text-decoration:none; color:black;" href="#" ');
		  document.write(' onmouseover="setBackground(this); return false;" onmouseout="clearBackground(this); return false;" ');
		  document.write(' oncontextmenu="if (!keyDown) { clearNumber('+ j +', '+ i +', ' + number + ');} ');
		  document.write(' else {var backgroundNode = this.parentNode.parentNode.parentNode; if (backgroundNode.style.background  == backgroundNode.parentNode.style.background) {backgroundNode.style.background = colorForNumber[' + number + '];} else {backgroundNode.style.background = colorForNumber[0]}} return false;" ');
		  document.write(' onclick="if(working) {return false }; if (!keyDown) {setNumber('+ j +', '+ i +', this.firstChild.data, null, null, true); var backgroundNode = this.parentNode.parentNode.parentNode; backgroundNode.style.background = colorForNumber[0];} ');
		  document.write(' else {clearNumber('+ j +', '+ i +', ' + number + ');} return false;" >'+ number + '</a></td>');
		}
		document.writeln('</tr>');
	 }
	 document.writeln('</table></td>');
  }
  document.writeln('</tr>');
}
document.write('</table>');


// Variabeln für den Background Sudoku Generator
computeSudokusInBackground = true;
NewSudokuDaten = SudokuDaten;
NewSudokuHistory = new Array();
newSolveHistory = new Array();
lastNewSudokuFound = null;
backgroundDelay = 10;
maxBacktracks = 100;
numberOfBacktracks = 0;
lastNumberUndone = null;

NewSudokuHistory[0] = deepCopyArray(SudokuDaten);

// diese variabel zeigt ob die suche neu gestartet werden soll
function backgroundCalculateNewSudoku(start)
{
  if (start != null)
  {
	 numberOfBacktracks = 0;
	 lastNewSudokuFound = null;
	 newSolveHistory.length = 0;
	 NewSudokuHistory.length = 1;
	 NewSudokuDaten = deepCopyArray(NewSudokuHistory[0]);
	 //alert("Starte background sudoku kalkulation");
	 // minimale anzahl Zahlen in einem eindeutigen Sudoku sind 17
	 for (var i = 0; i < 17; i++)
	 {
		setRandomNumberInNewSudoku();
	 }
  }
			 // todo: nächste zwei Zeilen auskommentieren
			 //SudokuDaten = NewSudokuDaten;
			 //updateView();
  setTimeout("tryForUniqueSudokuSolution()", backgroundDelay );
}


function illegalNewSudokuFound()
{
  var illegalSudokusCount = document.getElementById("illegalSudokusCount");
  setTimeout("backgroundCalculateNewSudoku(true)", backgroundDelay);
  if (illegalSudokusCount != null)
  {
	 illegalSudokusCount.firstChild.data++;
  }
}

function backtrackNewSudoku()
{
  numberOfBacktracks++;
  NewSudokuDaten = deepCopyArray(NewSudokuHistory[NewSudokuHistory.length - 1]);
  NewSudokuHistory.length = NewSudokuHistory.length -1;
  lastNumberUndone = newSolveHistory[newSolveHistory.length-1];
  NewSudokuDaten[lastNumberUndone[1]][lastNumberUndone[0]][lastNumberUndone[2]-1] = null;
  NewSudokuDaten[lastNumberUndone[1]][lastNumberUndone[0]][9] = null;
  newSolveHistory.length = newSolveHistory.length - 1;
  //alert("Solution not found, backtracking. newSolveHistory.length: "+newSolveHistory.length +"; last set:" + lastSet);
  var backtrackCount = document.getElementById("backtrackCount");
  if (backtrackCount != null)
  {
	 backtrackCount.firstChild.data = numberOfBacktracks;
  }
}

function sendSudokuSolution(callFrom)
{
  // es gibt eine lösung, und es wurde keine zweite gefunden -> eindeutige Lösung
  //alert(callFrom + ": sudoku hat nur eine Lösung, sollte gespeichert werden");
  var startSudoku = getSudokuNumber(NewSudokuHistory[1]);
  var endSudoku = getSudokuNumber(lastNewSudokuFound);
  var difficulty = "";
  if (document.getElementById('getDifficulty') != null)
  {
	 difficulty = "&difficulty=" + (new Board().solve(15,getSudokuNumber(NewSudokuHistory[1])));
  }

  var legalSudokusCount = document.getElementById("legalSudokusCount");
  if (legalSudokusCount != null)
  {
	 legalSudokusCount.firstChild.data++;
	 var generatedSudokus = document.getElementById("generatedSudokus");
	 if (generatedSudokus != null)
	 {
		var newSudokuLink = document.createElement("a");
		newSudokuLink.setAttribute("href", "#sudoku");
		newSudokuLink.setAttribute("onclick", "fillPredefinedNumbers('" + startSudoku + "'); return true;");
		newSudokuLink.appendChild(document.createTextNode("" + legalSudokusCount.firstChild.data));
		generatedSudokus.appendChild(newSudokuLink);
		generatedSudokus.appendChild(document.createTextNode(" "));
	 }
  }

  executeRemoteJavascript( sudokuRegisterUrl +"?sudoku_start="+startSudoku+"&sudoku_solution=" + endSudoku  + difficulty + "&source=xmlhttp&SudokuPageLastModified=" + document.lastModified); 
}

function setNextFunctionAccordingToBacktrackCount()
{
  if (numberOfBacktracks >= maxBacktracks)
  {
	 setTimeout("backgroundCalculateNewSudoku(true)", backgroundDelay);
  }
  else
  {
	 backtrackNewSudoku();
	 setTimeout("tryForUniqueSudokuSolution()", backgroundDelay);
  }
}

function tryForUniqueSudokuSolution()
{
  if (working == true || computeSudokusInBackground == false)
  {
	 setTimeout("tryForUniqueSudokuSolution()", backgroundDelay );
	 return;
  }
  var uniqueNumbersFound = getSudokuStatus(NewSudokuDaten);
			 // todo: nächste zwei Zeilen auskommentieren
			 //SudokuDaten = NewSudokuDaten;
			 //updateView(uniqueNumbersFound, true);
  if (uniqueNumbersFound == null)
  {
	 if (newSolveHistory.length > 0)
	 {
		setNextFunctionAccordingToBacktrackCount();
		return;
	 }
	 if (lastNewSudokuFound != null)
	 {
		setTimeout("backgroundCalculateNewSudoku(true)", backgroundDelay);
		sendSudokuSolution("top");
		return;
	 }
	 else
	 {
		//alert("illegales sudoku");
		illegalNewSudokuFound();
		return;
	 }
  }
  //alert("nächste runde");
  var uniqueNumbers = false;
  while (uniqueNumbersFound != null && uniqueNumbersFound.length > 0)
  {
	 uniqueNumbers = true;
	 var nextNumber = uniqueNumbersFound[uniqueNumbersFound.length -1];
	 uniqueNumbersFound.length = uniqueNumbersFound.length -1;
	 setNumberInData(nextNumber[0],nextNumber[1],nextNumber[2], NewSudokuDaten);
  }
  if (uniqueNumbers == true)
  {
	 setTimeout("tryForUniqueSudokuSolution()", backgroundDelay);
	 return;
  }
  for(var i = 0; i < 9; i++) 
  {
	 for(var j = 0; j < 9; j++) 
	 {
		for(var k = 0; NewSudokuDaten[i][j][9] == null && k < 9; k++) 
		{
		  if ( NewSudokuDaten[i][j][k] != null) {
			 // vor dem setzen die history speichern
			 NewSudokuHistory.push(deepCopyArray(NewSudokuDaten));
			 nextSetNumber = new Array(j,i,k+1);
			 newSolveHistory.push(nextSetNumber);
			 // alert("setze " + nextSetNumber);
			 setNumberInData(j,i,k+1, NewSudokuDaten);
			 setTimeout("tryForUniqueSudokuSolution()", backgroundDelay);
			 return;
		  }
		}
	 }
  }
  // wenn es bis hier durchläuft, ist alles gesetzt
  if (lastNewSudokuFound == null)
  {
	 lastNumberUndone = null;
	 lastNewSudokuFound = deepCopyArray(NewSudokuDaten);
	 if (newSolveHistory.length == 0)
	 {
		setTimeout("backgroundCalculateNewSudoku(true)", backgroundDelay);
		sendSudokuSolution("bottom");
		return;
	 }
	 else
	 {
		//alert("eine lösung gefunden");
		setNextFunctionAccordingToBacktrackCount();
		return;
	 }
  }
  else
  {
	 //alert("zwei lösungen gefunden, füge eine zahl hinzu");
	 // setze die letzte legale zahl um ein eindeutiges sudoku hinzukriegen 
	 var setNumber = lastNumberUndone;
	 //alert("setze nummer für eindeutigkeit: " + setNumber);
	 newSolveHistory.length = 0;
	 NewSudokuDaten = deepCopyArray(NewSudokuHistory[1]);
	 NewSudokuHistory.length = 1;
	 lastNewSudokuFound = null;
	 setNumberInData(setNumber[0],setNumber[1],setNumber[2], NewSudokuDaten);
	 NewSudokuHistory.push(deepCopyArray(NewSudokuDaten));
	 setTimeout("tryForUniqueSudokuSolution()", backgroundDelay);
	 return;
  }
}

function getSudokuNumber(data)
{
  var defaultFilledSudoku = deepCopyArray(emptySudoku);
  for(var i = 0; i < 9; i++) 
  {
	 for(var j = 0; j < 9; j++) 
	 {
		var uniqueNumber = data[i][j][9];
		if (uniqueNumber != null)
		{
			setNumberInData(j,i,uniqueNumber, defaultFilledSudoku);
		}
	 }
  }
  var numbers = "";
  var deletedNumbers = "";
  for(var i = 0; i < 9; i++) 
  {
	 for(var j = 0; j < 9; j++) 
	 {
		var uniqueNumber = data[i][j][9];
		if (uniqueNumber != null)
		{
			numbers += uniqueNumber;
		}
		else
		{
		  var accumulatedDeletions = "";
		  for(var k = 0; k < 9; k++) 
		  {
			 if (defaultFilledSudoku[i][j][k] != null && data[i][j][k] == null)
			 {
				// wenn gelöscht, dann momentane "Lösch-Zahl" als gelöscht hinzufügen
				accumulatedDeletions += (k+1);
			 }
		  }
		  if(accumulatedDeletions.length != 0)
		  {
			 numbers += "-";
			 deletedNumbers += "-" + accumulatedDeletions;
		  }
		  else
		  {
			  numbers += 0;
		  }
		}
	 }
  }
  if (deletedNumbers.length != 0)
  {
	 numbers += " " + deletedNumbers;
  }
  return numbers;
}

function setRandomNumberInNewSudoku()
{
  var number = null;
  var randX;
  var randY;
  var randNumber;
  while (number == null)
  {
	 randX = Math.floor(Math.random()*9);
	 randY = Math.floor(Math.random()*9);
	 randNumber = Math.floor(Math.random()*9);
	 if (NewSudokuDaten[randY][randX][randNumber] != null && NewSudokuDaten[randY][randX][9] == null)
	 {
		number = NewSudokuDaten[randY][randX][randNumber];
		//alert ("nummer gefunden: "+number+" in "+randY+","+randX+": "+ NewSudokuDaten[randY][randX]);
	 }
  }
  setNumberInData(randX, randY, number, NewSudokuDaten);
  return new Array(randX, randY, number);
}

function isSudokuSolved(data)
{
  for(var i = 0; i < 9; i++) 
  {
	 for(var j = 0; j < 9; j++) 
	 {
		if( data[i][j][9] == null)
		{
		  return false;
		}
	 }
  }
  //alert ("sudoku gelöst");
  return true;
}

// Füllen von der Nummern welche im Link übergeben wurden
setTimeout("fillPredefinedNumbers()",20);

// update den permalink und den status
setTimeout("updateDisplayedStatus()", 1000);

/////////////////////////////////////////
// Starte background sudoku kalkulation
setTimeout("backgroundCalculateNewSudoku(true)", 1000);

////////////////////////////////////////////////////////////////////////////
// AJAX Part
////////////////////////////////////////////////////////////////////////////

function emptyHandler(){}

function randomSudokuHandler()
{
	 // Make sure the request is loaded (readyState = 4)
	 if (req && req.readyState == 4)
	 {
		  // Make sure the status is "OK"
		  if (req.status == 200)
		  {
				var data = req.responseXML.getElementById('sudoku').getAttribute('data');
				fillPredefinedNumbers(data);
		  }
	 }
}
/**
 * Open a connection to the specified URL, which is
 * intended to respond with an XML message.
 * 
 * @param string method The connection method; either "GET" or "POST".
 * @param string url	 The URL to connect to.
 * @param string toSend The data to send to the server; must be URL encoded.
 * @param function responseHandler The Javascript function handling server response.
 */
function xmlOpen(method, url, toSend, responseHandler)
{
	 if (window.XMLHttpRequest)
	 {
		  // browser has native support for XMLHttpRequest object
		  req = new XMLHttpRequest();
	 }
	 else if (window.ActiveXObject)
	 {
		  // try XMLHTTP ActiveX (Internet Explorer) version
		  req = new ActiveXObject("Microsoft.XMLHTTP");
	 }
	 
	 if(req)
	 {
		  try
		  {
			 req.onreadystatechange = responseHandler;
			 req.open(method, url, true);
			 req.setRequestHeader("content-type","application/x-www-form-urlencoded");
			 req.send(toSend);
		  }
		  catch (e) 
		  {
			  // fehler beim senden oder empfangen
		  }
	 }
}

// Verschiedene Utility-Funktionen, welche von Buttons und ähnlichem aufgerufen werden können
function loadRandomSudoku(randomDiffuculty)
{
  executeRemoteJavascript(randomSudokuUrl  + '?' + (new Date()).getTime() + randomDiffuculty + "&javascript=true");
}

// loads and executes javascript from given url 
function executeRemoteJavascript(url)
{
  var script = document.createElement("script");
  script.src = url;
  document.body.appendChild(script);
}

function getSudokuNumberEncoded(data)
{
  var defaultFilledSudoku = deepCopyArray(SudokuHistory[0] != null ? SudokuHistory[0] : SudokuDaten);
  for(var i = 0; i < 9; i++) 
  {
	 for(var j = 0; j < 9; j++) 
	 {
		var uniqueNumber = data[i][j][9];
		if (uniqueNumber != null)
		{
			setNumberInData(j,i,uniqueNumber, defaultFilledSudoku);
		}
	 }
  }
  var numbers = "";
  for(var i = 0; i < 9; i++) 
  {
	 for(var j = 0; j < 9; j++) 
	 {
		var uniqueNumber = data[i][j][9];
		if (uniqueNumber != null)
		{
			numbers += uniqueNumber;
		}
		else
		{
		  var currentDeletedNumber = 1;
		  var accumulatedDeletions = 0;
		  for(var k = 0; k < 9; k++) 
		  {
				if (defaultFilledSudoku[i][j][k] != null)
				{
				  // check ob in data zusätzliche ziffern gelöscht wurden
				  //alert("defaultFilledSudoku["+i+"]["+j+"] = " + defaultFilledSudoku[i][j]);
				  if(data[i][j][k] == null)
				  {
					  // wenn ja, dann momentane "Lösch-Zahl" als gelösch hinzufügen
					  accumulatedDeletions += currentDeletedNumber;
				  }
				  currentDeletedNumber *= 2;
				}
		  }
		  // wenn keine zusätzlichen Zahlen gelöscht wurden -> "0" hinzufügen
		  if (accumulatedDeletions == 0)
		  {
				numbers += "0";
		  }
		  else
		  {
				alert("accumulatedDeletions : "+ accumulatedDeletions + "\ndata["+i+"]["+j+"] : " + data[i][j] + "\ndefaultFilledSudoku["+i+"]["+j+"] : " + defaultFilledSudoku[i][j]);
				numbers += String.fromCharCode(160 + accumulatedDeletions);
		  }
		}
	 }
  }
  return numbers;
}