Location: PHPKode > projects > Sudoku Solver > sudoku-solver/Solver.class.php
```<?php
/**********************************************************************
* Copyright (c)- 2005 - Bronstee.com Software & Services and others.
* are made available under the terms of the
* GNU General Public License (GPL) Version 2, June 1991,
* which accompanies this distribution, and is available at:
*
* Contributors:
* Ghica van Emde Boas - original author, Sept 2005
* Ton Meuleman - added the checkGrouping solution, March 2007
* <contributor2> - <description of contribution>
*     ...
*********************************************************************/
require "NumberField.class.php";

class Solver {
protected \$nfields = array ();
protected \$csvtext;
protected \$valueFound = true;
protected \$enumber;
protected \$gfields = array ();
protected \$gnumber;
protected \$cx;

/*
* create the 9x9 grid of number fields
*/
public function __construct() {
for (\$i = 1; \$i < 82; \$i ++) {
\$name = "f\$i";
\$pstring = trim(\$_POST[\$name]);
\$this->nfields[] = new NumberField(\$name, "\$i", \$pstring);
}
}

public function setUndoValues(\$us) {
\$this->emptyFields();
foreach (\$us as \$seq => \$pstring) {
\$name = "f\$seq";
\$pstring = trim(\$pstring);
if (\$pstring != '') {
\$field = \$this->getField(\$seq);
\$pvals = explode(' ', \$pstring);
\$cnt = count(\$pvals);
if(\$cnt == 1) \$field->setValue(\$pvals[0]);
\$field->possibleValues = \$pvals;
}
}
}

/*
* clear all the values in the grid
*/
public function clearFields() {
foreach (\$this->nfields as \$field) {
\$field->setValue('');
\$field->possibleValues = range(1, 9);
}
}

/*
* show blank fields
*/
public function emptyFields() {
foreach (\$this->nfields as \$field) {
\$field->setValue('');
}
}

/*
* go back to initial state
*/
public function resetFields() {
if (count(\$_SESSION['undostack'])>0){
\$this->setUndoValues(\$_SESSION['undostack'][0]);
unset(\$_SESSION['undostack']);
}
else echo "<br/>no reset data available.";
}

/*
* show blank fields
*/
public function undo() {
if (count(\$_SESSION['undostack'])>1){
\$last = array_pop(\$_SESSION['undostack']);
\$last = array_pop(\$_SESSION['undostack']);
\$this->setUndoValues(\$last);
}
else {
echo "<br/>nothing to undo!";
\$this->resetFields();
}
}

/*
* find the field that corresponds to a certain position
*/
public function getField(\$pos) {
return \$this->nfields[\$pos -1];
}

public function getFields() {
return \$this->nfields;
}

public function setFields(\$fields) {
\$this->nfields = \$fields;
}

public function getRCB(\$nr, \$type) {
\$rcb = array ();
foreach (\$this->nfields as \$field) {
if (\$field-> \$type == \$nr)
\$rcb[] = \$field;
}
return \$rcb;
}

/*
* Check the possible values for all fields
*/
public function checkValues() {
//        echo "<br/>checking values";
\$this->checkFieldSet(\$this->nfields, false);
}

/*
* Check the possible values for all fields
*/
public function checkValuesRecurse() {
//        echo "<br/>checking values";
\$this->checkFieldSet(\$this->nfields, true);
}

/*
* Check the possible values for a set of fields
*/
public function checkFieldSet(\$fields, \$recurse) {
foreach (\$fields as \$field) {
//                  echo "<br/>checking: \$field->seqno - row: \$field->row - hasvalue: ", \$field->hasValue(), " - val: \$field->fieldValue";
\$this->checkSet('row',\$field, \$recurse);
\$this->checkSet('column', \$field, \$recurse);
\$this->checkSet('block', \$field, \$recurse);
}
}

public function finishCheck() {
//        echo "<br/>checking values";
\$i = 0;
while (\$this->valueFound && \$i < 10) {
\$this->valueFound = false;
\$i ++;
foreach (\$this->nfields as \$field) {
//            echo "<br/>checking: \$field->seqno - row: \$field->row - hasvalue: ", \$field->hasValue(), " - val: \$field->fieldValue";
\$this->checkSet('row',\$field);
\$this->checkSet('column', \$field);
\$this->checkSet('block', \$field);
//            \$this->checkRow(\$field);
//            \$this->checkColumn(\$field);
//            \$this->checkBlock(\$field);
}
//            echo "<br/>check values: \$i times";
}
}

public function checkUnique(\$type) {
//      echo "<br/>checking unique rows, columns or blocks";
for (\$i = 1; \$i < 10; \$i ++) {
//            \$this->checkValues();
\$occurVals = array (0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
\$uFields = \$this->getRCB(\$i, \$type);
foreach (\$uFields as \$field) {
for (\$j = 1; \$j < 10; \$j ++) {
if (!\$field->hasValue() && in_array(\$j, \$field->possibleValues)) {
\$occurVals[\$j]++;
}
}
}
// is there a unique one?
\$occ = implode(' ', \$occurVals);
//            echo "<br/>uniquecheck: \$type no: \$i, occurs: \$occ ";
\$this->checkOccursOnce(\$uFields, \$occurVals);
}
}

protected function checkOccursOnce(\$uFields, \$occurVals) {
\$occ = implode(' ', \$occurVals);
for (\$j = 1; \$j < 10; \$j ++) {
if (\$occurVals[\$j] == 1) {
foreach (\$uFields as \$field) {
\$vals = implode(' ', \$field->possibleValues);
//                    echo "<br/>checking: \$field->row,\$field->column vals: \$vals";
if (in_array(\$j, \$field->possibleValues)) {
//                        echo "<br/>setting: \$field->row,\$field->column to: \$j-- ";
\$this->setValue(\$field, \$j);
\$this->valueFound = true;
break;
}
}
}

}
}

public function checkDouble() {
//      echo "<br/>checking double values in rows, columns or blocks";
for (\$i = 1; \$i < 10; \$i ++) {
//            \$this->checkValues();
\$occurVals = array (0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
\$uFields = \$this->getRCB(\$i, 'block');
foreach (\$uFields as \$field) {
for (\$j = 1; \$j < 10; \$j ++) {
if (!\$field->hasValue() && in_array(\$j, \$field->possibleValues)) {
\$occurVals[\$j]++;
}
}
}
// is there a unique one?
\$occ = implode(' ', \$occurVals);
//            echo "<br/>doublecheck: block no: \$i, occurs: \$occ ";
\$this->checkOccursDouble(\$uFields, \$occurVals);
}
}

protected function checkOccursDouble(\$uFields, \$occurVals) {
\$occ = implode(' ', \$occurVals);
// look through all numbers
for (\$j = 1; \$j < 10; \$j ++) {
if (\$occurVals[\$j] > 1) {
\$val = \$occurVals[\$j];
\$rows = Array ();
\$cols = Array ();
foreach (\$uFields as \$field) {
\$vals = implode(' ', \$field->possibleValues);
if (in_array(\$j, \$field->possibleValues)) {
\$rows[] = \$field->row;
\$cols[] = \$field->column;
}
}
\$firstR = \$rows[0];
\$firstC = \$cols[0];
\$rEqual = true;
\$cEqual = true;
foreach (\$rows as \$row) {
if (\$row != \$firstR) {
\$rEqual = false;
break;
}
}
foreach (\$cols as \$col) {
if (\$col != \$firstC) {
\$cEqual = false;
break;
}
}
if (\$rEqual) {
//                    echo "<br/>\$j occurs \$val times";
//                    echo '<br/> rows: ', implode(' ', \$rows);
// find the fields in the row, but not in the block
\$rowFields = array_diff(\$this->getRCB(\$firstR, 'row'), \$uFields);
\$this->diffOneValue(\$rowFields, \$j);
}
if (\$cEqual) {
//                    echo "<br/>\$j occurs \$val times";
//                    echo '<br/> columns: ', implode(' ', \$cols);
// find the fields in the column, but not in the block
\$colFields = array_diff(\$this->getRCB(\$firstC, 'column'), \$uFields);
\$this->diffOneValue(\$colFields, \$j);
}
}

}
}

protected function diffOneValue(\$fields, \$value) {
\$valArray[] = \$value;
foreach (\$fields as \$rfield) {
// if the field has a value, this value will be the only one in possibleValues
if (!\$rfield->hasValue()) {
\$rfield->possibleValues = array_values(array_diff(\$rfield->possibleValues, \$valArray));
//                echo "<br/> with: \$rfield->row - \$rfield->column";
if (count(\$rfield->possibleValues) == 1) {
\$this->setValue(\$rfield, \$rfield->possibleValues[0]);
break;
}
}
}
}

public function checkSet(\$type, \$field, \$recurse) {
if (\$field->hasValue())
return;
//        echo "<br/>checking \$type: \$field->row - \$field->column";
\$sno = \$field->\$type;
\$sFields = \$this->getRCB(\$sno, \$type);
\$sFields = array_diff(\$sFields, array (\$field));
\$this->diffValues(\$sFields, \$field, \$recurse);
}

protected function diffValues(\$fields, \$field, \$recurse) {
foreach (\$fields as \$rfield) {
// if the field has a value, this value will be the only one in possibleValues
if (\$rfield->hasValue()) {
\$field->possibleValues = array_values(array_diff(\$field->possibleValues, \$rfield->possibleValues));
//                echo "<br/> with: \$rfield->seqno - \$rfield->row";
}
if (count(\$field->possibleValues) == 1) {
if (\$recurse)
\$this->setValue(\$field, \$field->possibleValues[0]);
else \$field->setValue(\$field->possibleValues[0]);
break;
}
}
}

public function checkPairs() {
\$this->checkPairsByType('row');
\$this->checkPairsByType('column');
\$this->checkPairsByType('block');
}

public function checkPairsByType(\$type) {
//        echo "<br/>checking for pairs in \${type}s";
for (\$i = 1; \$i < 10; \$i ++) {
//            \$this->checkValues();
\$occurVals = array (0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
\$uFields = \$this->getRCB(\$i, \$type);
\$pairs = array();
foreach (\$uFields as \$field) {
// is there a pair?
if (count(\$field->possibleValues) == 2) {
\$pval = implode(' ', \$field->possibleValues);
//                    echo "<br/>paircheck: \$type no: \$i, pair: \$pval ";
\$pairs[] = array(\$pval, \$field);
}
}
if (count(\$pairs) > 1) {
//                echo "<br/>paircheck: \$type no: \$i";
foreach (\$pairs as \$pair) {
\$fieldStr = \$pair[1]->toString();
//                    echo "<br/>\$pair[0] -- \$fieldStr";
\$pstr = \$pair[0];
foreach (\$pairs as \$ipair) {
if (\$pstr == \$ipair[0] && \$pair[1]->seqno != \$ipair[1]->seqno) {
//                            echo "<br/>found pairs: ", \$pair[1]->toString(), " and: ", \$ipair[1]->toString();
\$fld1 = \$pair[1];
\$fld2 = \$ipair[1];
\$pFields = array_diff(\$uFields, array(\$fld1, \$fld2));
\$this->diffOneValue(\$pFields, \$fld1->possibleValues[0]);
\$this->diffOneValue(\$pFields, \$fld1->possibleValues[1]);
}
}

}
}
}
}

public function checkGrouping() {
\$this->checkGroupingByNumber(3);
\$this->checkGroupingByNumber(4);
\$this->checkGroupingByNumber(5);
}

protected function checkGroupingByNumber(\$gn) {
\$this->gnumber = \$gn;
\$this->checkGroupingByType('row');
\$this->checkGroupingByType('column');
\$this->checkGroupingByType('block');
}

protected function checkGroupingByType(\$type) {

//        echo "<br/>checking for grouping in \${type}s for \$this->gnumber<br/>";

for (\$i = 1; \$i < 10; \$i ++) {

\$uFields = \$this->getRCB(\$i, \$type);
\$groups[] = array(array());

foreach (\$uFields as \$field) {
\$groups[] = array(\$field);
}

\$this->gfields = array (10, 9, 8, 7, 6, 5, 4, 3, 2, 1);
\$this->cx = \$this->gnumber-1;
\$this->gfields[\$this->cx] = 1;
\$this->enumber = 9;
\$avail = \$this->isAvailable(\$groups);
if (\$avail > \$this->gnumber) {
\$this->checkOnGrouping(\$groups);
}
unset(\$groups);
}
}

protected function checkOnGrouping(\$groups) {

while(\$this->gfields[\$this->cx] <= \$this->enumber-\$this->cx) {
\$this->gfields[\$this->cx-1] = \$this->gfields[\$this->cx] + 1;
if (\$this->cx-1 == 0) {
\$this->checkThisGrouping(\$groups); }
else {
\$this->cx = \$this->cx-1;
\$this->checkOnGrouping(\$groups);
}
\$this->gfields[\$this->cx]++;
}
\$this->cx++;
}

protected function checkThisGrouping(\$groups) {

while(\$this->gfields[0] <= \$this->enumber) {
\$brk = false;
\$possibleValues = array();
\$groupedCells = array();
\$n = \$this->gnumber-1;
while(\$n >= 0) {
\$groupedCells[] = \$this->gfields[\$n];
\$cell = \$groups[\$this->gfields[\$n]];
foreach (\$cell as \$field) {
if (count(\$field->possibleValues) < 2) {
\$brk = true;
break;
}
foreach (\$field->possibleValues as \$value) {
if (!in_array(\$value,\$possibleValues)) {
\$possibleValues[] = \$value;
}
}
}
if (\$brk) {
break;
}
\$n = \$n-1;
}
if ((count(\$possibleValues)<= \$this->gnumber) and !\$brk)  {
\$this->procesTheResult(\$groups, \$groupedCells, \$possibleValues);
}
\$this->gfields[0]++;
}
}

protected function procesTheResult(\$groups, \$groupedCells, \$possibleValues) {

for (\$i = 1; \$i < 10; \$i ++) {
if (!in_array(\$i, \$groupedCells)) {
\$cell = \$groups[\$i];
foreach (\$cell as \$field) {
if (count(\$field->possibleValues) > 1) {
\$result = array_diff(\$field->possibleValues, \$possibleValues);
if (count(\$result) == 1) {
\$field->setValue(implode(' ', \$result));
}
else {
\$field->possibleValues = \$result;
}
}
}
}
}
}

protected function isAvailable(\$groups) {

\$n = 0;
foreach (\$groups as \$cell) {
foreach (\$cell as \$field) {
if (count(\$field->possibleValues) > 1) {
\$n++;
}
}
}
return(\$n);
}

protected function setValue(\$field, \$value) {
\$field->setValue(\$value);
\$this->valueFound = true;
\$rno = \$field->row;
\$rfields = \$this->getRCB(\$rno, 'row');
\$this->checkFieldSet(\$rfields, true);
\$cno = \$field->column;
\$cfields = \$this->getRCB(\$cno, 'column');
\$this->checkFieldSet(\$cfields, true);
\$bno = \$field->block;
\$bfields = \$this->getRCB(\$bno, 'block');
\$this->checkFieldSet(\$bfields, true);
}

}
?>```