Location: PHPKode > projects > Sudoku Solver > sudoku-solver/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
 * 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);
    }

}
?>
Return current item: Sudoku Solver