April.15A php implementation of Dancing Link ( Algorithm X) Sudoku problem

As an assignment of Artificial Intelligence course I have recently implemented Knuth’s Algorithm X for solving sudoku problem. You can see it in action here.

Here is the code:
<?php
/*Mamnun Hassan Bhuiyan # 0405077*/
class Node
{
public $left;
public $right;
public $up;
public $down;
public $column;
public $rowNumber;
public $label;

public function __construct($rowNumber, $label, $column)
{
$this->setLeft($this);
$this->setRight($this);
$this->setUp($this);
$this->setDown($this);
$this->setColumn($column);
$this->rowNumber = $rowNumber;
$this->label = $label;
}

public function labelOrNull($node)
{
if($node === null)
return “NULL”;
else return $node->getFullLabel();
}

public function getFullLabel()
{
return (“row “.$this->rowNumber.“, label “.$this->label);
}

public function __toString()
{
return “Node ” . $this->getFullLabel() .
“, left is (” . $this->labelOrNull($this->getLeft()) .
“), right is (” . $this->labelOrNull($this->getRight()) .
“), up is (” . $this->labelOrNull($this->getUp()) .
“), down is (” . $this->labelOrNull($this->getDown()) . “)”;
}

public function setLeft($node)
{
$this->left = $node;
}

public function getLeft()
{
return $this->left;
}

public function setRight($node)
{
$this->right = $node;
}

public function getRight()
{
return $this->right;
}

public function setUp($node)
{
$this->up = $node;
}
public function getUp()
{
return $this->up;
}

public function setDown($node)
{
$this->down = $node;
}

public function getDown()
{
return $this->down;
}

public function setColumn($node)
{
$this->column = $node;
}

public function getColumn()
{
return $this->column;
}

public function getLabel()
{
return $this->label;
}

public function getRowNumber()
{
return $this->rowNumber;
}

}

class ColumnNode extends Node
{
public $size;
public $optional;

public function addAtEnd($node)
{
$end = $this->getUp();

$node->setUp($end);
$node->setDown($this);
$end->setDown($node);
$this->setUp($node);

$this->size = $this->size +1;
}
public function __construct($label, $optional)
{
parent::__construct(0,$label,null);
$this->setColumn($this);
$this->optional = $optional;
$this->size = 0;
}

public function __toString()
{
return “Node ” . $this->getFullLabel() .
“, left is (” . $this->labelOrNull($this->getLeft()) .
“), right is (” . $this->labelOrNull($this->getRight()) .
“), up is (” . $this->labelOrNull($this->getUp()) .
“), down is (” . $this->labelOrNull($this->getDown()) .
“), count ” . $this->size;
}

public function isOptional()
{
return $this->optional;
}

public function getCount()
{
return $this->size;
}

public function incrementSize()
{
$this->size = $this->size + 1;
}

public function decrementSize()
{
$this->size = $this->size - 1;
}

}

class DancingLinks
{
public $firstColumn;
public $rowCount;
public $solution;
public $solutionIndex;
public $startingCount;
public $traveller;

public function __construct($labels, $optional=array())
{
$columns = array();

for($i=0;$i<count($labels);$i++)
{
$columns[$i] = new ColumnNode($labels[$i],$optional[$i]);
$columns[$i]->setRight(null);

if($i>0)
{
$columns[$i]->setLeft($columns[$i-1]);
$columns[$i-1]->setRight($columns[$i]);
}
}

$this->firstColumn = new ColumnNode(0,false);
$columns[0]->setLeft($this->firstColumn);
$this->firstColumn->setRight($columns[0]);
$columns[count($labels)-1]->setRight($this->firstColumn);
$this->firstColumn->setLeft($columns[count($labels)-1]);
$this->solution = array();
$this->solutionIndex = 0;
}

public function getFirstColumn()
{
return $this->firstColumn->getRight();
}

public function removeColumn(ColumnNode $columnHead)
{
$scanner = $columnHead->getDown();

while($scanner !== $columnHead)
{
$rowTraveller = $scanner->getRight();
while($rowTraveller !== $scanner)
{
$rowTraveller->getUp()->setDown($rowTraveller->getDown());
$rowTraveller->getDown()->setUp($rowTraveller->getUp());
$rowTraveller->getColumn()->decrementSize();
$rowTraveller = $rowTraveller->getRight();
}

$scanner = $scanner->getDown();
}

$columnHead->getLeft()->setRight($columnHead->getRight());
$columnHead->getRight()->setLeft($columnHead->getLeft());
}

public function reinsertColumn(ColumnNode $columnNode)
{
$scanner = $columnNode->getUp();

while($scanner !== $columnNode)
{
$rowTraveller = $scanner->getLeft();

while ($rowTraveller !== $scanner)
{
$rowTraveller->getUp()->setDown($rowTraveller);
$rowTraveller->getDown()->setUp($rowTraveller);
$rowTraveller->getColumn()->incrementSize();
$rowTraveller = $rowTraveller->getLeft();
}

$scanner = $scanner->getUp();
}

$columnNode->getLeft()->setRight($columnNode);
$columnNode->getRight()->setLeft($columnNode);
}

public function removeRow(Node $rowHead)
{
$scanner = $rowHead;
do{
$next = $scanner->getRight();
$this->removeColumn($scanner->getColumn());
$scanner = $next;
}while($scanner!==$rowHead);
}

public function reinsertRow(Node $rowHead)
{
$scanner = $rowHead;
do{
$scanner = $scanner->getLeft();
$this->reinsertColumn($scanner->getColumn());
}while($scanner!==$rowHead);
}

public function addInitialRow(array $labels, $length=null)
{
$result = null;
if($length==null)$length = count($labels);
if($length!=0)
{
$prev = null;
$first = null;

$this->rowCount = $this->rowCount + 1;

for($i=0;$i<$length;$i++)
{
$node = null;
$searcher = null;
$theColumn = null;

$searcher = $this->firstColumn;

do{
if($searcher->getLabel() == $labels[$i])
$theColumn = $searcher;
$searcher = $searcher->getRight();
}while(($searcher!==$this->firstColumn) && $theColumn==null);

if($theColumn == null)
{
echo “Couldn’t find a column labelled “.$labels[$i];
}

$node = new Node($this->rowCount,$labels[i],$theColumn);
$theColumn->addAtEnd($node);
$node->setLeft($prev);
$node->setRight(null);
if($prev!=null)
$prev->setRight($node);
else
$first = $node;

$prev = $node;
}

$first->setLeft($prev);
$prev->setRight($first);
$result = $first;
}

return $result;
}

public function getNextNonOptionalColumn(Node $node)
{
$nextColumn = $node->getColumn();
do{
$nextColumn = $nextColumn->getRight()->getColumn();
}while( ($nextColumn->getCount()==0) && ($nextColumn->isOptional()) );

return $nextColumn;
}

public function solveNonRecurse()
{
$result = array();

while($result == null)
{
$thisColumn = $this->traveller->getColumn();

if( ($thisColumn === $this->firstColumn) || ($thisColumn === $this->traveller) )
{
if($thisColumn === $this->firstColumn)
{
for($i=0;$i<$this->solutionIndex;$i++)
{
$result[$i] = $this->solution[$i]->getRowNumber() - 1;
}
}
if($this->solutionIndex == $this->startingCount)
return $result;
else
{
$this->traveller = $this->solution[--$this->solutionIndex];
$this->reinsertRow($this->traveller);
$this->traveller = $this->traveller->getDown();
}
}
else
{
$this->removeRow($this->traveller);
$this->solution[$this->solutionIndex++] = $this->traveller;
$this->traveller = $this->getNextNonOptionalColumn($this->firstColumn)->getDown();
}
}
return $result;
}

public function solve()
{
$solution = array();

if($this->traveller == null)
{
$this->traveller = $this->getNextNonOptionalColumn($this->firstColumn)->getDown();
$this->startingCount = $this->solutionIndex;
}

return $this->solveNonRecurse();
}

public function removeInitialSolutionSet(array $solutions)
{
while( ($row = array_pop($solutions)) != null)
{
$this->removeRow($row);
$this->solution[$this->solutionIndex++] = $row;
}
}

}

class DancingLinksSudoku
{
public $dla;

public function __construct(array $puzzle)
{
$labels = array();
$rowData = array();
$givenList = array();

for ($i=0;$i<324;$i++)
$labels[$i] = $i + 1;

$this->dla = new DancingLinks($labels);

for($row=0;$row<9;$row++)
{
for($column=0;$column<9;$column++)
{
for($digit=0;$digit<9;$digit++)
{
$boxrow = 0;
$boxcol = 0;
$isGiven = true;
$newRow = null;

$isGiven = ( $puzzle[$row][$column] == ($digit+1) );

$rowData[0] = 1 + ($row * 9 + $column);
$rowData[1] = 1 + 81 + ($row * 9 + $digit);
$rowData[2] = 1 + 81 + 81 + ($column * 9 + $digit);
$boxrow = floor($row / 3);
$boxcol = floor($column / 3);
$rowData[3] = 1 + 81 + 81 + 81 +(($boxrow * 3 + $boxcol) * 9 + $digit);

$newRow = $this->dla->addInitialRow($rowData);

if($isGiven)
array_push($givenList,$newRow);
}
}
}

$this->dla->removeInitialSolutionSet($givenList);
}

public function handleSolution($rowIndex)
{
$solution = array();

if($rowIndex!=null)
{
$p = 0;

for($i=0;$i<81;$i++)
{
$value = $rowIndex[$i];

$digit = $value % 9;
$value = floor($value / 9);
$column = $value % 9;
$value = floor($value / 9);
$row = $value %9;

$solution[$row][$column] = $digit + 1;
}
}

return $solution;
}

public function solveit()
{
return $this->handleSolution($this->dla->solve());
}
}

if(isset($_POST['matrix']))
{
$i = 0;
$j = 0;
$matrix = $_POST['matrix'];
for($i=0;$i<9;$i++)
{
for($j=0;$j<9;$j++)
{
if($matrix[$i][$j] == “”) $matrix[$i][$j] = 0;
$matrix[$i][$j] = (int)$matrix[$i][$j];
}
}
/*$puzzle1 = array(
array(4, 0, 3, 0, 0, 8, 0, 0, 0),
array(9, 2, 0, 0, 0, 0, 1, 0, 6),
array(0, 0, 0, 0, 0, 6, 0, 0, 0),
array(5, 0, 6, 0, 2, 0, 0, 0, 0),
array(0, 4, 0, 3, 0, 1, 0, 2, 0),
array(0, 0, 0, 0, 7, 0, 9, 0, 8),
array(0, 0, 0, 7, 0, 0, 0, 0, 0),
array(3, 0, 5, 0, 0, 0, 0, 1, 2),
array(0, 0, 0, 1, 0, 0, 5, 0, 9)
);*/
$s = new DancingLinksSudoku($matrix);
$solution = $s->solveit();
//print_r($solution);
}
?>
<html>
<head>
<title>Sudoku</title>
<style type=”text/css”>
input{width:25px;}
.btn{width:50px;}
.class1{background:#ACA899;}
</style>
</head>
<body>
<form class=”board” autocomplete=”off” method=”post” action=”">
<table cellspacing=”0″ cellpadding=”0″ border=”0″>
<?php for($i=0;$i<9;$i++) {?>
 <tr>
<?php for($j=0;$j<9;$j++) {?>
 <td><input name=”matrix[<?php echo $i;?>][<?php echo $j;?>]” value=”<?php echo $matrix[$i][$j];?>” maxlength=”1″ autocomplete=”off” class=”<?php
if($i>2 && $i<6 && $j>=0 && $j<3)
echo “class1″;
if($i>=0 && $i<3 && $j>2 && $j<6)
echo “class1″;
if($i>2 && $i<6 && $j>5 && $j<9)
echo “class1″;
if($i>5 && $i<9 && $j>2 && $j<6)
echo “class1″;

?>” /></td>
<?php } ?>
 </tr>
<?php } ?>
 <tr>
<td align=”center” colspan=”9″>
<input class=”btn” type=”reset” onclick=”window.location=<?php echo $_SERVER['REQUEST_URI']?>” />
<input class=”btn” type=”submit” />
</td>
</tr>
</table>
</form>
<table cellspacing=”0″ cellpadding=”0″>
<?php for($i=0;$i<9;$i++) {?>
 <tr>
<?php for($j=0;$j<9;$j++) {?>
 <td><input value=”<?php echo $solution[$i][$j];?>” maxlength=”1″ autocomplete=”off” class=”<?php
if($i>2 && $i<6 && $j>=0 && $j<3)
echo “class1″;
if($i>=0 && $i<3 && $j>2 && $j<6)
echo “class1″;
if($i>2 && $i<6 && $j>5 && $j<9)
echo “class1″;
if($i>5 && $i<9 && $j>2 && $j<6)
echo “class1″;

?>” /></td>
<?php } ?>
 </tr>
<?php } ?>
 <tr>
<td align=”center” colspan=”9″ id=”message”>
</td>
</tr>
</table>
</body>
</html>

Filed under: PHP, , , ,

Leave a Reply

« Type hinting in PHP Give your java application a new LookAndFeel »