<?php

/*
 * Author: Francisco José García Rico
 * Created on 12-oct-2005
 * Filename: sudokusolver2.php
 * 
 */

//Check the possible values for the blank cells, seeing only the values for its square
function check_square($row, $column, $minirow, $minicolumn) {
	//echo "Function check_square: ";
	$array_square = array();
	for ($i = 1; $i <= 3; $i ++)
		for ($j = 1; $j <= 3; $j ++){
			$value = $_POST["pSudoku_".$row."_".$column."_".$i."_".$j]; 
			if ($value != "")
				$array_square[$value] = -1;
		}

	return $array_square;
}

//Check the possible values for the blank cells, seeing only the values for its row
function check_row($row, $column, $minirow, $minicolumn){
	//echo "Function check row: ";
	$array_row = array();
	for ($i=1;$i<=3;$i++)
		for ($j = 1; $j <= 3; $j ++){
			$value = $_POST["pSudoku_".$row."_".$i."_".$minirow."_".$j]; 
			if ($value != "")
				$array_row[$value] = -1;
		}
	return $array_row;
} 

//Check the possible values for the blank cells, seeing only the values for its column
function check_column($row, $column, $minirow, $minicolumn){
	//echo "Function check column: ";
	$array_column = array();
	for ($i=1;$i<=3;$i++)
		for ($j = 1; $j <= 3; $j ++){
			$value = $_POST["pSudoku_".$i."_".$column."_".$j."_".$minicolumn]; 
			if ($value != "")
				$array_column[$value] = -1;
		}
	return $array_column;
}

//Check the values from 1 to 9 which aren't in the passed array
function other_values($array_values){
	$str_return;
	for ($i=1;$i<=9;$i++){
		if ($array_values[$i]!=-1)
			$str_return.= $i;
	}
	return $str_return;
}

//This function obtain the different values that can put in a blank cell
function blank_values($row,$column,$minirow,$minicolumn){
	$array_square = check_square($row,$column,$minirow,$minicolumn);
	$array_row = check_row($row,$column,$minirow,$minicolumn);
	$array_column = check_column($row,$column,$minirow,$minicolumn);
	$array_total = $array_square + $array_row + $array_column;
	return other_values($array_total);
}

//This functions return the relationship between two positions
//Posible return values;
// 0: no relationship
// 1: the same group
// 5: the same row
// 3: the same column
// 6: the same row and the same group
// 4: the same column and the same group
function relationship_positions($pos1, $pos2){
	$return_value = 0;
	if ((substr($pos1,0,1)==substr($pos2,0,1)) && (substr($pos1,1,1)==substr($pos2,1,1))){//it belongs to the same group
		$return_value += 1;
	}
	
	if ((substr($pos1,0,1)==substr($pos2,0,1)) && (substr($pos1,2,1)==substr($pos2,2,1))){//it belongs to the same row
		$return_value += 5;
	}
	else if ((substr($pos1,1,1)==substr($pos2,1,1)) && (substr($pos1,3,1)==substr($pos2,3,1))){//it belongs to the same column
		$return_value += 3;
	}
	
	return $return_value;
}

//Function to print the sudoku
function print_sudoku($table){
	$str_salida = "<table width=\"300\" align=\"center\">";	
	for ($i=1;$i<=3;$i++){
		$str_salida .= "<tr>";		
		for ($j=1;$j<=3;$j++){
			$str_salida .=  "<td>";
			$str_salida .=  "<table align=\"center\" border=\"3\" bordercolor=\"#000000\">";			
			for ($k=1;$k<=3;$k++){
				$str_salida .=  "<tr>";				
				for ($l=1;$l<=3;$l++){
					$str_salida .=  "<td>";
					$num_values = strlen($table["pSudoku_".$i."_".$j."_".$k."_".$l]);					
					$str_salida .=  "<input type=\"text\" name=\"pSudoku_".$i."_".$j."_".$k."_".$l."\" size=\"4\" class=\"cell_".$num_values."\" value=\"".$table["pSudoku_".$i."_".$j."_".$k."_".$l]."\">";
					$str_salida .=  "</td>";					
				}
				$str_salida .=  "</tr>";
			}
			$str_salida .=  "</table>";
			$str_salida .=  "</td>";			
		}
		$str_salida .=  "</tr>";
	}
	$str_salida .= "<tr>";
	$str_salida .= "<td colspan=\"3\" align=\"center\"><input type=\"submit\" name=\"pCalculateSudoku\" value=\"SOLVE SUDOKU\"></td>";
	$str_salida .= "</tr>";	
	$str_salida .= "</table>";
	echo $str_salida;
}

echo "<html>";
echo "<head>";
echo "<title>Sudoku Solver</title>";
echo "<link rel=\"stylesheet\" type=\"text/css\" href=\"styles2.css\" />";
echo "</head>";
echo "<body>";
echo "<form name=\"formi\" method=\"POST\" action=\"sudokusolver2.php\">";
echo "<table width=\"300\" align=\"center\">";
$cells_solver = 0;
$there_is_changes = true;
$tablas_sudokus = array();
$cells_with_two_values = array();
while ($there_is_changes){
	$there_is_changes = false;
	for ($i = 1; $i <= 3; $i ++) {
		$str_salida .= "<tr>";
		for ($j = 1; $j <= 3; $j ++) {
			$str_salida .=  "<td>";
			$str_salida .=  "<table align=\"center\" border=\"3\" bordercolor=\"#000000\">";
			for ($k = 1; $k <= 3; $k ++) {
				$str_salida .=  "<tr>";
				for ($l = 1; $l <= 3; $l ++) {
					$str_salida .=  "<td>";
					if (sizeof($_POST)>0){
						$value_cell = $_POST["pSudoku_".$i."_".$j."_".$k."_".$l];
						$num_values = strlen($value_cell);
						if ($value_cell=="" || $num_values>1){
							$new_value_cell = blank_values($i,$j,$k,$l);
							if ($value_cell!=$new_value_cell)
								$there_is_changes = true;
							$_POST["pSudoku_".$i."_".$j."_".$k."_".$l] = $new_value_cell;
						}
						$num_values = strlen($value_cell);
						$cells_solved += $num_values;
						if ($num_values==2)//almaceno la posición de estos valores en un array
							$cells_with_two_values[$i.$j.$k.$l] = $new_value_cell;
					}
					else{
						$value_cell = "";
						$num_values = 1;
					}
					$str_salida .=  "<input type=\"text\" name=\"pSudoku_".$i."_".$j."_".$k."_".$l."\" size=\"4\" class=\"cell_".$num_values."\" value=\"$value_cell\">";
					$str_salida .=  "</td>";
				}
				$str_salida .=  "</tr>";
			}
			$str_salida .=  "</table>";
			$str_salida .=  "</td>";
		}
	}
	if ($there_is_changes){
		$str_salida ="";
		$cells_solved = 0;
		$cells_with_two_values = array();
	}
	else if (!($cells_solved==81)){//todavia no está solucionado el sudoku
		//Realizo una segunda pasada para eliminar aquellos valores en los que se produzca 
		//una incongruencia del siguiente tipo:
		//39 739 39
		//si en la primera y la tercera celda los valores a repartir son 39, en la segunda
		//no podrá haber ningúno de estos dos valores
		//print_r($cells_with_two_values);
		//Obtengo todas las posiciones en las que se encuentran dos posibles valores
		$posiciones = array_keys($cells_with_two_values);
		for ($b=0;$b<count($posiciones);$b++){
			for ($g=0;$g<count($posiciones);$g++){
				if (($b!=$g) && ($cells_with_two_values[$posiciones[$g]]==$cells_with_two_values[$posiciones[$b]])){
					//echo "Mismo valor en ".$posiciones[$b]." y en ".$posiciones[$g].": ".relationship_positions($posiciones[$b],$posiciones[$g])."<br>";
					switch (relationship_positions($posiciones[$b],$posiciones[$g])){
						case 0://no relationship
							;
							break;
						
						case 1://the same group
							for ($q=1;$q<=3;$q++)
								for ($w=1;$w<=3;$w++){
									if ((!(($q==substr($posiciones[$b],2,1)) && ($w==substr($posiciones[$b],3,1)))) && (!(($q==substr($posiciones[$g],2,1)) && ($w==substr($posiciones[$g],3,1))))){
										$_POST["pSudoku_".substr($posiciones[$b],0,1)."_".substr($posiciones[$b],1,1)."_".$q."_".$w] = str_replace(substr($cells_with_two_values[$posiciones[$g]],0,1),"",$_POST["pSudoku_".substr($posiciones[$b],0,1)."_".substr($posiciones[$b],1,1)."_".$q."_".$w]);
										$_POST["pSudoku_".substr($posiciones[$b],0,1)."_".substr($posiciones[$b],1,1)."_".$q."_".$w] = str_replace(substr($cells_with_two_values[$posiciones[$g]],1,1),"",$_POST["pSudoku_".substr($posiciones[$b],0,1)."_".substr($posiciones[$b],1,1)."_".$q."_".$w]);
										//$there_is_changes = true;
									}
								}	
							break;
							
						case 3://the same column
							for ($q=1;$q<=3;$q++)
								for ($w=1;$w<=3;$w++){
									if ((!(($q==substr($posiciones[$b],0,1)) && ($w==substr($posiciones[$b],2,1)))) && (!(($q==substr($posiciones[$g],0,1)) && ($w==substr($posiciones[$g],2,1))))){
										$_POST["pSudoku_".$q."_".substr($posiciones[$b],1,1)."_".$w."_".substr($posiciones[$b],3,1)] = str_replace(substr($cells_with_two_values[$posiciones[$g]],0,1),"",$_POST["pSudoku_".$q."_".substr($posiciones[$b],1,1)."_".$w."_".substr($posiciones[$b],3,1)]);
										$_POST["pSudoku_".$q."_".substr($posiciones[$b],1,1)."_".$w."_".substr($posiciones[$b],3,1)] = str_replace(substr($cells_with_two_values[$posiciones[$g]],1,1),"",$_POST["pSudoku_".$q."_".substr($posiciones[$b],1,1)."_".$w."_".substr($posiciones[$b],3,1)]);
										//$there_is_changes = true;
									}
								}						
							break;
						
						case 4://the same column and the same group
							//code for the same group
							for ($q=1;$q<=3;$q++)
								for ($w=1;$w<=3;$w++){
									if ((!(($q==substr($posiciones[$b],2,1)) && ($w==substr($posiciones[$b],3,1)))) && (!(($q==substr($posiciones[$g],2,1)) && ($w==substr($posiciones[$g],3,1))))){
										$_POST["pSudoku_".substr($posiciones[$b],0,1)."_".substr($posiciones[$b],1,1)."_".$q."_".$w] = str_replace(substr($cells_with_two_values[$posiciones[$g]],0,1),"",$_POST["pSudoku_".substr($posiciones[$b],0,1)."_".substr($posiciones[$b],1,1)."_".$q."_".$w]);
										$_POST["pSudoku_".substr($posiciones[$b],0,1)."_".substr($posiciones[$b],1,1)."_".$q."_".$w] = str_replace(substr($cells_with_two_values[$posiciones[$g]],1,1),"",$_POST["pSudoku_".substr($posiciones[$b],0,1)."_".substr($posiciones[$b],1,1)."_".$q."_".$w]);
										//$there_is_changes = true;
									}
								}							
							//code for the same columne						
							for ($q=1;$q<=3;$q++)
								for ($w=1;$w<=3;$w++){
									if ((!(($q==substr($posiciones[$b],0,1)) && ($w==substr($posiciones[$b],2,1)))) && (!(($q==substr($posiciones[$g],0,1)) && ($w==substr($posiciones[$g],2,1))))){
										$_POST["pSudoku_".$q."_".substr($posiciones[$b],1,1)."_".$w."_".substr($posiciones[$b],3,1)] = str_replace(substr($cells_with_two_values[$posiciones[$g]],0,1),"",$_POST["pSudoku_".$q."_".substr($posiciones[$b],1,1)."_".$w."_".substr($posiciones[$b],3,1)]);
										$_POST["pSudoku_".$q."_".substr($posiciones[$b],1,1)."_".$w."_".substr($posiciones[$b],3,1)] = str_replace(substr($cells_with_two_values[$posiciones[$g]],1,1),"",$_POST["pSudoku_".$q."_".substr($posiciones[$b],1,1)."_".$w."_".substr($posiciones[$b],3,1)]);
										//$there_is_changes = true;
									}
								}						
							break;
						
						case 5://the same row
							for ($q=1;$q<=3;$q++)
								for ($w=1;$w<=3;$w++){
									if ((!(($q==substr($posiciones[$b],1,1)) && ($w==substr($posiciones[$b],3,1)))) && (!(($q==substr($posiciones[$g],1,1)) && ($w==substr($posiciones[$g],3,1))))){
										$_POST["pSudoku_".substr($posiciones[$b],0,1)."_".$q."_".substr($posiciones[$b],2,1)."_".$w] = str_replace(substr($cells_with_two_values[$posiciones[$g]],0,1),"",$_POST["pSudoku_".substr($posiciones[$b],0,1)."_".$q."_".substr($posiciones[$b],2,1)."_".$w]);
										$_POST["pSudoku_".substr($posiciones[$b],0,1)."_".$q."_".substr($posiciones[$b],2,1)."_".$w] = str_replace(substr($cells_with_two_values[$posiciones[$g]],1,1),"",$_POST["pSudoku_".substr($posiciones[$b],0,1)."_".$q."_".substr($posiciones[$b],2,1)."_".$w]);
										//$there_is_changes = true;
									}
								}								
							break;
						
						case 6://the same row and the same group
							//code for the same group
							for ($q=1;$q<=3;$q++)
								for ($w=1;$w<=3;$w++){
									if ((!(($q==substr($posiciones[$b],2,1)) && ($w==substr($posiciones[$b],3,1)))) && (!(($q==substr($posiciones[$g],2,1)) && ($w==substr($posiciones[$g],3,1))))){
										$_POST["pSudoku_".substr($posiciones[$b],0,1)."_".substr($posiciones[$b],1,1)."_".$q."_".$w] = str_replace(substr($cells_with_two_values[$posiciones[$g]],0,1),"",$_POST["pSudoku_".substr($posiciones[$b],0,1)."_".substr($posiciones[$b],1,1)."_".$q."_".$w]);
										$_POST["pSudoku_".substr($posiciones[$b],0,1)."_".substr($posiciones[$b],1,1)."_".$q."_".$w] = str_replace(substr($cells_with_two_values[$posiciones[$g]],1,1),"",$_POST["pSudoku_".substr($posiciones[$b],0,1)."_".substr($posiciones[$b],1,1)."_".$q."_".$w]);
										//$there_is_changes = true;
									}
								}			
							
							//code for the same row
							for ($q=1;$q<=3;$q++)
								for ($w=1;$w<=3;$w++){
									if ((!(($q==substr($posiciones[$b],1,1)) && ($w==substr($posiciones[$b],3,1)))) && (!(($q==substr($posiciones[$g],1,1)) && ($w==substr($posiciones[$g],3,1))))){
										$_POST["pSudoku_".substr($posiciones[$b],0,1)."_".$q."_".substr($posiciones[$b],2,1)."_".$w] = str_replace(substr($cells_with_two_values[$posiciones[$g]],0,1),"",$_POST["pSudoku_".substr($posiciones[$b],0,1)."_".$q."_".substr($posiciones[$b],2,1)."_".$w]);
										$_POST["pSudoku_".substr($posiciones[$b],0,1)."_".$q."_".substr($posiciones[$b],2,1)."_".$w] = str_replace(substr($cells_with_two_values[$posiciones[$g]],1,1),"",$_POST["pSudoku_".substr($posiciones[$b],0,1)."_".$q."_".substr($posiciones[$b],2,1)."_".$w]);
										//$there_is_changes = true;
									}
								}											
							break;	
					}
				}
			}
		}
	}
	
}//end while
//echo $str_salida;
print_sudoku($_POST);
echo "</form>";
echo "</body>";
echo "</html>";
?>

