Location: PHPKode > scripts > Sudoku Solver > sudoku4/Solver.class.php
```<?php
/**********************************************************************
* Copyright (c)- 2005 - Bronstee.com Software & Services and others.
* All rights reserved.   This program and the accompanying materials
* 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:
* http://www.opensource.org/licenses/gpl-license.php
*
* Contributors:
* Ghica van Emde Boas - original author, Sept 2005
* <contributor2> - <description of contribution>
*     ...
*********************************************************************/
require "NumberField.class.php";

class Solver {
var \$nfields = array ();
var \$csvtext;
var \$valueFound = true;

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

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;
\$seqno = \$field->seqno;
\$this->nfields[\$seqno-1] = \$field;
}
}
}

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

/*
* show blank fields
*/
function emptyFields() {
foreach (\$this->nfields as \$field) {
\$field->setValue('');
\$seqno = \$field->seqno;
\$this->nfields[\$seqno-1] = \$field;
}
//        foreach (\$this->nfields as \$field) {
//            \$dval = implode(' ', \$field->possibleValues);
////            echo "<br/>field: ", \$field->seqno, " value: ", \$field->fieldValue, " pvals: \$dval";
//        }
}

/*
* go back to initial state
*/
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
*/
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
*/
function &getField(\$pos) {
return \$this->nfields[\$pos -1];
}

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

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

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

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

/*
* Check the possible values for all fields
*/
function checkValuesRecurse() {
do {
//            echo "<br/>checking values";
\$this->valueFound = false;
\$this->checkFieldSet(range(1,81), true);
} while (\$this->valueFound);
}

/*
* Check the possible values for a set of fields
*/
function checkFieldSet(\$fieldnos, \$recurse) {
foreach (\$fieldnos as \$fno) {
\$field = \$this->nfields[\$fno-1];
if (\$field->hasValue())
continue;
\$pvals = implode(',', \$field->possibleValues);
//            echo "<br/>checking: \$field->seqno - \$field->row, \$field->column - pvals: \$pvals";
\$this->checkSet('row',\$fno, \$recurse);
\$this->checkSet('column', \$fno, \$recurse);
\$this->checkSet('block', \$fno, \$recurse);
}
}

function finishCheck() {
//        echo "<br/>checking values";
\$i = 0;
while (\$this->valueFound && \$i < 10) {
\$this->valueFound = false;
\$i ++;
foreach (range(1,81) as \$fno) {
\$this->checkSet('row',\$fno);
\$this->checkSet('column', \$fno);
\$this->checkSet('block', \$fno);
}
//            echo "<br/>check values: \$i times";
}
}

function checkUnique(\$type) {
//        echo "<br/>checking unique \$type";
for (\$i = 1; \$i < 10; \$i ++) {
\$this->checkValuesRecurse();
\$occurVals = array (0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
\$fieldnos = \$this->getRCB(\$i, \$type);
foreach (\$fieldnos as \$fno) {
\$field = \$this->nfields[\$fno-1];
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(\$fieldnos, \$occurVals);
}
}

function checkOccursOnce(\$fieldnos, \$occurVals) {
\$occ = implode(' ', \$occurVals);
for (\$j = 1; \$j < 10; \$j ++) {
if (\$occurVals[\$j] == 1) {
foreach (\$fieldnos as \$fno) {
\$field = \$this->nfields[\$fno-1];
\$vals = implode(' ', \$field->possibleValues);
if (in_array(\$j, \$field->possibleValues)) {
\$field->possibleValues = array(\$j);
\$this->setValue(\$field, \$j);
\$this->valueFound = true;
break;
}
}
}

}
}

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');
\$fieldnos = \$this->getRCB(\$i, 'block');
foreach (\$fieldnos as \$fno) {
\$field = \$this->nfields[\$fno-1];
//           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(\$fieldnos, \$occurVals);
}
}

function checkOccursDouble(\$fieldnos, \$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 ();
\$fieldnos = \$this->getRCB(\$i, \$type);
foreach (\$fieldnos as \$fno) {
\$field = \$this->nfields[\$fno-1];

//                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
\$ifieldnos = \$this->getRCB(\$firstR, 'row');
\$rowFieldnos = array_diff(\$ifieldnos, \$fieldnos);
\$this->diffOneValue(\$rowFieldnos, \$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
\$ifieldnos = \$this->getRCB(\$firstR, 'column');
\$colFieldnos = array_diff(\$ifieldnos, \$fieldnos);
\$this->diffOneValue(\$colFieldnos, \$j);
}
}

}
}

function diffOneValue(\$fieldnos, \$value) {
\$valArray[] = \$value;
foreach (\$fieldnos as \$fno) {
\$rfield = \$this->nfields[\$fno-1];
// 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));
\$seqno = \$rfield->seqno;
\$this->nfields[\$seqno-1] = \$rfield;
if (count(\$rfield->possibleValues) == 1) {
\$this->setValue(\$rfield, \$rfield->possibleValues[0]);
break;
}
}
}
}

function checkSet(\$type, \$fno, \$recurse) {
\$field = \$this->nfields[\$fno-1];
if (\$field->hasValue())
return;
\$sno = \$field->\$type;
\$fieldnos = \$this->getRCB(\$sno, \$type);
\$sfieldnos = array_diff(\$fieldnos, array (\$field->seqno));
\$this->diffValues(\$sfieldnos, \$fno, \$recurse);
}

function diffValues(\$fieldnos, \$fno, \$recurse) {
\$field = \$this->nfields[\$fno-1];
foreach (\$fieldnos as \$rno) {
\$rfield = \$this->nfields[\$rno-1];
// 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));
\$seqno = \$field->seqno;
\$this->nfields[\$seqno-1] = \$field;
}
if (count(\$field->possibleValues) == 1) {
if (\$recurse)
\$this->setValue(\$field, \$field->possibleValues[0]);
else {
\$field->setValue(\$field->possibleValues[0]);
\$seqno = \$field->seqno;
\$this->nfields[\$seqno-1] = \$field;
}
break;
}
}
}

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

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);
\$fieldnos = \$this->getRCB(\$i, \$type);
\$pairs = array();
foreach (\$fieldnos as \$fno) {
\$field = \$this->nfields[\$fno-1];
// 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];
\$pfieldnos = array_diff(\$fieldnos, array(\$fld1->seqno, \$fld2->seqno));
\$this->diffOneValue(\$pfieldnos, \$fld1->possibleValues[0]);
\$this->diffOneValue(\$pfieldnos, \$fld1->possibleValues[1]);
}
}

}
}
}
}

function setValue(\$field, \$value) {
\$field->setValue(\$value);
\$seqno = \$field->seqno;
\$this->nfields[\$seqno-1] = \$field;
\$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);
}

}
?>```
Return current item: Sudoku Solver