Fishtrap

It may not be the most elegant class I’ve ever written but it does work suprisingly well. The basic idea is that the inital state of the grid is input in the form of an array of arrays where each of the inner arrays represents a row of the grid. The answer will then be found using a depth first search arriving at the first solution to satisfy the initial grid.

<?php
/**
 * Description of Sodoku
 *
 * @author nathanielmchugh
 */
class Sodoku {
 public $answer = false;
 public function __construct($grid)
 {
 $this-&gt;solve($grid);
 }
 public function createTrigrams($grid){
 $rows = $this-&gt;createRows($grid);
 $columns = $this-&gt;createColumns($grid);
 $blocks = $this-&gt;createBlocks($grid);
 $trigrams = array();
 foreach ($grid as $sqNo =&gt; $value) {
 if ($value == 0) {
 list($x, $y) = $this-&gt;convertSqNoTocood($sqNo);
 $trigrams[$sqNo]['col'] = $columns[$x];
 $trigrams[$sqNo]['row'] = $rows[$y];
 $trigrams[$sqNo]['block'] = $blocks[$this-&gt;getBlockNoSqNo($sqNo)];
 $trigrams[$sqNo]['sqNo'] = $sqNo;
 }
 }
 $lowest[] = 9;
 foreach ($trigrams as $trigram) {
 $possibles = $this-&gt;getUnused($trigram);
 if (count($possibles) &lt; current($lowest)) {
 $lowest = array($trigram['sqNo'] =&gt; count($possibles));
 }
 }
 return $trigrams[key($lowest)];
 }
 public function solve($grid) {
 //        accept
 if ($this-&gt;answer) {
 return;
 }
 if (!$this-&gt;containsZeros($grid)) {
 $this-&gt;answer = $grid;
 return $grid;
 }
 $square = $this-&gt;createTrigrams($grid);
 $sqNo = $square['sqNo'];
 $possible = $this-&gt;getUnused($square);
 $newGrid = $grid;
 foreach ($possible as $pos) {
 $newGrid[$sqNo] = $pos;
 $this-&gt;solve($newGrid);
 }
 }
function containsZeros($grid)
{
 return in_array(0, $grid);
}
public function convertSqNoTocood($sqNo)
{
 $x = ($sqNo) % 9;
 $y = (int) floor(($sqNo)/9);
 return array( $x,  $y);
}
public function convertCoodToSq($x, $y)
{
 return $y*9 + $x;
}
public function getBlockNoSqNo($SqNo)
{
 global $blockKey;
 return $blockKey[$SqNo];
}
public function createColumns($grid)
{
 $cols = array();
 foreach ($grid as $sqNo =&gt; $value) {
 $colNum = $sqNo%9;
 $cols[$colNum][$sqNo] = $value;
 }
 return $cols;
}
public function createRows($grid)
{
 $rows = array();
 foreach ($grid as $sqNo =&gt; $value) {
 $rowNum = (int) floor($sqNo/9);
 $rows[$rowNum][$sqNo] = $value;
 }
 return $rows;
}
public function createBlocks($grid)
{
 global $blockKey;
 $blocks = array();
 $blockKey = array();
 $leftOffset = 0;
 $topOffset = 0;
 $sqNo = 0;
 for ($block = 0; $block &lt; 9; $block++) {
 for ($i = $leftOffset; $i &lt; ($leftOffset + 3); $i++) {
 for ($j = $topOffset; $j &lt; ($topOffset + 3); $j++) {
 $sqNo = $this-&gt;convertCoodToSq($j, $i);
 $blocks[$block][$sqNo] = (int) $grid[$sqNo];
 $blockKey[$sqNo] = $block;
 }
 }
 if ($leftOffset == 6) {
 $leftOffset = 0;
 $topOffset += 3;
 } else {
 $leftOffset += 3;
 }
 }
 return $blocks;
}
public function getUnused(Array $trigram) {
 $onetoNine = range(1,9);
 foreach ($trigram as $description =&gt; $listOfValues) {
 if ('sqNo' == $description) {
 continue 1;
 }
 foreach ($listOfValues as $value) {
 if  (($key = array_search($value, $onetoNine)) !== false) {
 unset($onetoNine[$key]);
 }
 }
 }
 return $onetoNine;
}
}