<?

	class Sudoku	{
		public $Grid = array();
		
		public $RW;		//Region Width (=Region height)
		public $RW2;	//RW Square
	
		public function __construct($RW=3) {
			$this->RW = $RW;
			$this->RW2 = $RW * $RW;
			$this->CreateGrid();
		}
		
		public function CreateGrid() {
		
			//default possibilities in order
			for ($v=0; $v<$this->RW2; $v++) $t[$v] = $v;
			
			//foreach cell...
			for ($y=0; $y<$this->RW2; $y++) {
				for ($x=0; $x<$this->RW2; $x++) {
					//shuffle possibilities
					for ($v=0; $v<$this->RW2; $v++) {
						$p1 = rand(0, $this->RW2-1);
						$n = $t[$p1];
						$t[$p1] = $t[$v];
						$t[$v] = $n;
					}
					//attach possibilities to cell
					for ($v=0; $v<$this->RW2; $v++) {
						$this->Grid[$y][$x][$t[$v]] = true;
					}
				}
			}
			
			//start filling at row, column (0,0)
			$this->Fill($this->Grid,0,0);
		}
		
		public function DrawGrid() {
			echo "<table border=1>";
			for ($y=0; $y<$this->RW2; $y++) {
				echo "<tr>";
				for ($x=0; $x<$this->RW2; $x++) {
					//draw cell
					echo sprintf("<td align=center width=40px height=40px bgcolor=#%s>", (($x/$this->RW ^ $y/$this->RW) & 1)?"AAAAAA":"FFFFFF");
					for ($v=0; $v<$this->RW2; $v++) {
						if (isset($this->Grid[$y][$x][$v]) ) echo $v+1;
					}
					echo "</td>";
				}
				echo "</tr>";
			}
			echo "</table>";
			echo "<hr>";
		}
		
		
		public function Fill($Grid, $px, $py) {
			//stopcondition: py is out of order
			if ($py==$this->RW2) {
				$this->Grid = $Grid;
				return true;
			}
			
			foreach($Grid[$py][$px] as $v=>$status) {
				$tmp = $Grid;
			
				//reduce possibilities
				for ($c=0; $c<$this->RW2; $c++) {
					//horizontal row
					unset($tmp[$py][$c][$v]);
					//vertical column
					unset($tmp[$c][$px][$v]);
					//region
					unset($tmp[floor($py/$this->RW)*$this->RW+floor($c/$this->RW)]  [floor($px/$this->RW)*$this->RW+($c % $this->RW)][$v]);
				}
				//append current possibility
				$tmp[$py][$px][$v] = true;
				
				//proceed to the next cell
				if ($px == $this->RW2-1) {	
					if ($this->Fill($tmp, 0, $py+1)) return true;
				} else {
					if ($this->Fill($tmp, $px+1, $py)) return true;
				}
			}
			return false;
		}
	}
	
?>