<?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
* 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);
}
}
?>