var num = 9;
var subsize = 3; 
var maxpos = num * num - 1;
var rowIndexes = new Array(maxpos + 1);
var colIndexes = new Array(maxpos + 1);
var subIndexes = new Array(maxpos + 1);
var board = new Array(maxpos + 1);

init();

function sudoku()
{
  if(confirm('Wollen Sie wirklich schon aufgeben?'))
  {
		if(getFormData())
		{
			if(! validate())
			{
				statusMessage("Das Sudoku ist nicht lösbar, da nicht alle Felder regelkonform ausgefüllt wurden.!");
				return;
			}
			
			statusMessage("Beginne Lösung...");
			var startTime = new Date();
			
			if(solve(0))
			{
				var duration = new Date().getTime() - startTime.getTime();
				setFormData();
				statusMessage("Das Sudoku wurde in " + duration + " ms gelöst.");
			}
			else
			{
				statusMessage("Für dieses Sudoku konnte keine Lösung gefunden werden!");
			}
		}
  }
}

function init()
{
  for(var i = 0; i < maxpos + 1; ++i)
  { 
    board[i] = 0;
  }
  
  for(var row = 0; row < num; ++row)
  {
    for(var col = 0; col < num; ++col)
    {
      var pos = row * num + col;
      rowIndexes[pos] = new Array(num - 1);
      colIndexes[pos] = new Array(num - 1);
      subIndexes[pos] = new Array(num - 1);
      var i = 0;
      
      for(var c = 0; c < num; ++c)
      {
        if(c != col)
        {
          rowIndexes[pos][i++] = row * num + c;
        }
      }
      
      i = 0;
      
      for(var r = 0; r < num; ++r)
      {
        if (r != row)
        {
          colIndexes[pos][i++] = num * r + col;
        }
      }
      
      var subrow = Math.floor(row / subsize);
      var subcol = Math.floor(col / subsize);
      i = 0;
     
      for(var sr = 0; sr < subsize; ++sr)
      {
        for(var sc = 0; sc < subsize; ++sc)
        {
          var index = (((subrow * subsize) + sr) * num) + (subcol * subsize) + sc; 
          
          if (index != pos)
          {
            subIndexes[pos][i++] = index;
          }
        }
      }
    }
  }
}

function getFormData()
{
  for(var i = 0; i < maxpos + 1; ++i)
  { 
    var value = document.forms["sudokuForm"].elements[i].value;
    
    if(isNaN(value) || value < 0 || value > 9)
    {
      statusMessage("Eingabefehler: Nur Zahlen von 1 bis 9 sind erlaubt!");
      return false;
    }
    
    var node = document.getElementById("p".concat(i));
    
    if(value != 0)
    {
      node.style.backgroundColor = "#eeeeee";
      node.parentNode.style.backgroundColor = "#eeeeee";
    }
    else
    {
			node.style.backgroundColor = "#ffffff";
      node.parentNode.style.backgroundColor = "#ffffff";
    }
    
    board[i] = value;
  }
  
  return true;
}

function setFormData()
{
  for(var i = 0; i < maxpos + 1; ++i)
  { 
    document.forms["sudokuForm"].elements[i].value = board[i]; 
  }
}

function statusMessage(msg)
{
  document.forms["sudokuForm"].elements["status"].value = msg; 
}

function clearBoard()
{
  if(confirm('Sollen wirklich alle Felder gelöscht werden?'))
  {
		for(var i = 0; i < maxpos + 1; ++i)
		{ 
			document.forms["sudokuForm"].elements[i].value = ""; 
			var node = document.getElementById("p".concat(i));
			
			if(node)
			{
				node.style.backgroundColor = "#ffffff";
				node.parentNode.style.backgroundColor = "#ffffff";
				node.disabled = false;
			}
		}
		
		statusMessage("");
  }
}
  
function solve(pos)
{
  if(pos > maxpos)
  {
    return true;
  }
  
  if(board[pos] == 0)
  {
    for (var i = 1; i <= num; ++i)
    {
      if(possibleEntry(pos, i))
      {
        board[pos] = i;
       
        if(solve(pos + 1))
        {
          return true;
        }
        else
        {
          board[pos] = 0;
        }
      }
    }
    
    return false;
  }
  else
  {
    return solve(pos + 1);
  }
}

function possibleEntry(pos, value)
{
  for(var i = 0; i < num - 1; ++i)
  {
    if(board[rowIndexes[pos][i]] == value)
      return false;

    if(board[colIndexes[pos][i]] == value)
      return false;

    if(board[subIndexes[pos][i]] == value)
      return false;
  }
  return true;
}

function possibleEntryShowError(pos, value)
{
  for(var i = 0; i < num - 1; ++i)
  {
    if(board[rowIndexes[pos][i]] == value)
    {
	  	var node = document.getElementById("p".concat(pos));
      node.style.backgroundColor = "#ff0000";
      node.parentNode.style.backgroundColor = "#ff0000";
      
      node = document.getElementById("p".concat(rowIndexes[pos][i]));
      node.style.backgroundColor = "#ff0000";
      node.parentNode.style.backgroundColor = "#ff0000";
      
      return false;
    }
    
    if(board[colIndexes[pos][i]] == value)
    {
      var node = document.getElementById("p".concat(pos));
      node.style.backgroundColor = "#ff0000";
      node.parentNode.style.backgroundColor = "#ff0000";
      
      node = document.getElementById("p".concat(colIndexes[pos][i]));
      node.style.backgroundColor = "#ff0000";
      node.parentNode.style.backgroundColor = "#ff0000";
      
      return false;
    }
    
    if(board[subIndexes[pos][i]] == value)
    {
	  	var node = document.getElementById("p".concat(pos));
      node.style.backgroundColor = "#ff0000";
      node.parentNode.style.backgroundColor = "#ff0000";
      
      node = document.getElementById("p".concat(subIndexes[pos][i]));
      node.style.backgroundColor = "#ff0000";
      node.parentNode.style.backgroundColor = "#ff0000";
      
      return false;
    }
  }
  
  return true;
}

function validate()
{
  for(var pos = 0; pos <= maxpos; ++pos)
  {
    if(board[pos] != 0)
    {
      if(!possibleEntry(pos, board[pos]))
      {
        return false;
      }
    }
  }
  
  return true;
}

function showValidation()
{
	if(getFormData())
	{
		for(var pos = 0; pos <= maxpos; ++pos)
		{
			if(board[pos] != 0)
			{
				if(!possibleEntryShowError(pos, board[pos]))
				{
					statusMessage("Die rot markierten Felder wurden nicht regelkonform befüllt!");
					return false;
				}
			}
		}
		
		statusMessage("Das Sudoku wurde regelkonform befüllt.");
	}
}