<?php 
/**This page displays a soduku (sudoku) board, as a set of text boxes. The user can enter an arbitrary problem, and this script will solve it, or indicate that there exists no solution.

See http://langabi.name/soduku_soln.html for more details of the algorithm.
Copyright 2005 Paul Cook. But feel free to use the algorithm anywhere you'd like.
*/

/**Recursively solves for missing values in the trial solution.
*
*$which is the index in $queue of the square currently being solved for
*/
function recurse($which) {
	global $check, $vals, $goto, $output, $options, $queue;
	if ($which >= sizeof($queue)) {
		//we have a solution! exit the recursion
		$output = $vals;
		return true;
	}
	list($x, $y) = $queue[$which];
	foreach ($options[$x][$y] as $i) {
		if ((!$check[$goto[$x][$y][0]][$i]) && (!$check[$goto[$x][$y][1]][$i]) && (!$check[$goto[$x][$y][2]][$i])) {
			$check[$goto[$x][$y][0]][$i] = true;
			$check[$goto[$x][$y][1]][$i] = true;
			$check[$goto[$x][$y][2]][$i] = true;
			$vals[$x][$y] = -$i;
			if (recurse($which + 1)) {
				return true; //exit recursion if we have a solution
			}
			$check[$goto[$x][$y][0]][$i] = false;
			$check[$goto[$x][$y][1]][$i] = false;
			$check[$goto[$x][$y][2]][$i] = false;
			$vals[$x][$y] = 0;
		}
	}
	return false; //no solution here
}

if (isset($_POST['Submit'])) {
	/**27-element array, one for each group of squares. Each element is a 9-element array of which values have been used already within that group*/
	$check = array();	
		
	/**array that gives the three groups that a square belongs to. The first two indices are the (x,y) of the square, and the third runs from 1..3 for the groups that square is in. The value is the index in $check of the given group.*/
	$goto = array(); 
	
	/**9x9 array of the current values of each square*/
	$vals = array();
	
	foreach (array_keys($_POST) as $var) {
		//find all squares in the board
		if (substr($var, 0, 1) == 'f') {
			$split = preg_split('/_/', $var); //find the three groups that the current square is in
			if (($_POST[$var]) || ($_POST[$var] === '0')) {
				if ((!is_numeric($_POST[$var])) || ($_POST[$var] < 1) || ($_POST[$var] > 9) || ($_POST[$var] === '0')) {
					die('Entries need to be numbers between 1 and 9, inclusive. Use the "back" button on your browser to correct the problem.');
				}
				if ($check[$split[1]][$_POST[$var]]) { die('The provided problem has the same number appearing twice in one of the rows. Use the "back" button on your browser to correct the problem.'); }
				if ($check[$split[2]+9][$_POST[$var]]) { die('The provided problem has the same number appearing twice in one of the columns. Use the "back" button on your browser to correct the problem.'); }
				if ($check[$split[3]+18][$_POST[$var]]) { die('The provided problem has the same number appearing twice in one of the 3x3 blocks. Use the "back" button on your browser to correct the problem.'); }
				//mark the current square's number used for each of the groups that the square is in
				$check[$split[1]][$_POST[$var]] = true;
				$check[$split[2]+9][$_POST[$var]] = true;
				$check[$split[3]+18][$_POST[$var]] = true;
				$vals[$split[1]][$split[2]] = $_POST[$var];
			} else {
				$vals[$split[1]][$split[2]] = 0;
			}
			//set up the redirect from squares to groups.
			$goto[$split[1]][$split[2]][] = $split[1];
			$goto[$split[1]][$split[2]][] = $split[2]+9;
			$goto[$split[1]][$split[2]][] = $split[3]+18;
		}
	}
	//eliminate all squares which can be worked out immediately
	do {
		$changed = false;
		
		/**List of squares which still need to be solved, using the recurse() function. This gets sorted in increasing order, by number of options each square still has available*/
		$queue = array();
		
		for ($i = 1; $i <= 9; $i++) {
			for ($j = 1; $j <= 9; $j++) {
				if ($vals[$i][$j] == 0) {
					$count = 0;
					/**Array of what numbers are still possible for each square*/
					$options[$i][$j] = array();
					for ($k = 1; $k <= 9; $k++) {
						//count how many numbers are still available for this square
						if ((!$check[$goto[$i][$j][0]][$k]) && (!$check[$goto[$i][$j][1]][$k]) && (!$check[$goto[$i][$j][2]][$k])) {
							$options[$i][$j][] = $k;
							$count++;
							$curr = $k;
						}
					}
					if ($count == 0) {
						die('Problem is not solvable! Please use the "back" button on your browser to change it.');
					} elseif ($count == 1) {
						//we've found the solution for this particular square
						$changed = true;
						$check[$goto[$i][$j][0]][$curr] = true;
						$check[$goto[$i][$j][1]][$curr] = true;
						$check[$goto[$i][$j][2]][$curr] = true;
						$vals[$i][$j] = -$curr;
					} else {
						//add square to the queue for recursive solving
						$queue[$count][] = array($i, $j);
					}
				}
			}
		}						
	} while ($changed); //loop for as long as new squares were filled
	
	//solve remaining squares recursively
	ksort($queue); //sort so that we recurse first through squares with the least number of available options
	//now flatten $queue a level of indices -- we don't want to track the $count index any more:
	$queue2 = array();
	foreach ($queue as $arr) {
		$queue2 = array_merge($queue2, $arr);
	}
	$queue = $queue2;
	recurse(0);
	if (!$output) {
		die('Problem has no solution! Please use the "back" button on your browser to change it.');
	}
}

//PHP ADODB document - made with PHAkt 2.8.2?>
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"><html><!-- InstanceBegin template="/Templates/general.dwt" codeOutsideHTMLIsLocked="false" -->
<head>
<!-- InstanceBeginEditable name="doctitle" -->
<title>Soduku</title>
<!-- InstanceEndEditable --><meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<link href="/styles/langabi.css" rel="stylesheet" type="text/css">
<script language="JavaScript" type="text/JavaScript" src="/langabi.js"></script>
<!-- InstanceBeginEditable name="head" --><!-- InstanceEndEditable -->
</head>

<body onLoad="MM_preloadImages('/images/button_forward_rollover.png')">
<div class="wrap">
<script language="JavaScript" type="text/JavaScript">
constructMenuTop();
</script>
<script language="JavaScript" type="text/JavaScript">
<!--
document.write('<img id="pagetopimage" width="760" height="180">'); //allow for graceful degradation for browsers with no javascript
choosePageTopImage();
//-->
</script>
<noscript>
<img id="pagetopimage" src="/images/tops/top1_merged.jpg" width="760" height="180">
</noscript>
<img class="pagetopimage_topleft_offset" src="/images/langabi.png" width="249" height="22">
<img class="pagetopimage_topleft" src="/images/shader_top.png" width="473" height="26">
<div class="pagetopimage_topright">
<a onMouseOut="MM_swapImgRestore(); hideTopImageName();" onMouseOver="MM_swapImage('button_forward','','images/button_forward_rollover.png',1); showTopImageName();" onClick="choosePageTopImage(); showTopImageName();"><img src="images/button_forward.png" alt="[>]" name="button_forward" width="19" height="18" border="0"></a>
</div>
<script language="JavaScript" type="text/JavaScript">
constructMenus();
</script>
<div id="content">
<!-- InstanceBeginEditable name="body" -->
<h1>Soduku (Sudoku) Solver</h1>
<?php if ($output) { ?>
<p>Below is the solution to the problem:</p>
<table border="1" width="500" style="font-weight: bold; text-align: center;">
    <tr>
		<?php
			for ($i = 1; $i <= 9; $i++) {
				for ($j = 1; $j <= 9; $j++) { 
					echo '<td>';
					if ($output[$i][$j] < 0) {
						echo '<font color="red">' . (-$output[$i][$j]) .'</font>';
					} else {
						echo $output[$i][$j];
					}
					echo "</td>\n";
				}
				if ($i < 9) {
					echo "</tr><tr>\n";
				}
			}
		?>
	</tr>
</table>
<hr><br/>
<?php } ?>
<p>Enter your problem in the table below. Entries can be numbers between 1 and 9 (inclusive). Click submit, and the solution will be displayed!</p>
<p>Solutions satisfy: each row and column has all the numbers from 1 to 9 exactly once each. Also, the table is made up of 9 3x3 subsections (top-left, top-middle, top-right, etc.). Each of these blocks also has each of the numbers from 1 to 9 exactly once.</p>
<form name="form1" method="post" action="soduku.php">
  <table border="1">
    <tr>
		<?php
			for ($i = 1; $i <= 9; $i++) {
				for ($j = 1; $j <= 9; $j++) { 
					//find which 3x3 subsection the square is in
					$k = floor(($j-1) / 3) + 1;
					$k += floor (($i-1) / 3) * 3;
					?>
					<td><input name="f_<?php echo $i . '_' . $j . '_' . $k; ?>" type='text' size="4" maxlength="1" value="<?php echo $_POST["f_${i}_${j}_${k}"]; ?>"></td>
					<?php
				}
				if ($i < 9) {
					?>
					</tr><tr>
					<?php
				}
			}
		?>
    </tr>
  </table>
  <p>
    <input type="submit" name="Submit" value="Submit">
</p>
</form>
<!-- InstanceEndEditable --></div>
<div id="menu">
<!-- InstanceBeginEditable name="menu (sidebar)" -->
<ul>
    <li><strong>Soduku solver : </strong>
    <ul>
  <li><a href="soduku_soln.html">Description of the method this solver uses </a><br>
    &nbsp;
  </li>
  <li><a href="soduku.phps">View the full source code</a><br>&nbsp;
  </li>
  <li><a href="http://langabi.name/blog/2005/07/15/soduku-solver">Comments? Leave them here</a></li>
  </ul></li>
</ul>
<!-- InstanceEndEditable -->
</div>
<div id="footer">
<!-- InstanceBeginEditable name="footer" --><!-- InstanceEndEditable -->
<br>
[ <a href="http://langabi.name">Home</a> | <a href="http://langabi.name/blog">Blog</a> | <a href="http://langabi.name/gallery">Photo Album</a> | <a href="http://langabi.name/links.php">Links</a> ]
</div>
</div>
</body>
<!-- InstanceEnd --></html>