PHP 数独求解的程序实现

本文介绍了PHP 数独求解的程序实现。分享给大家供大家参考，欢迎大家的学习。

数独问题

数独是一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，

推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复。

对于给出的数字二维数组，要求每行每列的数字不能重复。

PHP代码

/*
 * 数独求解程序
 */
class Sudoku
{
    var $matrix;

    function __construct($arr = null)
    {
        if ($arr == null) {
            $this->clear();
        } else {
            $this->matrix = $arr;
        }
    }

    function clear()
    {
        for ($i = 0; $i < 9; $i++) {
            for ($j = 0; $j < 9; $j++) {
                $this->matrix[$i][$j] = array();
                for ($k = 1; $k <= 9; $k++) {
                    $this->matrix[$i][$j][$k] = $k;
                }
            }
        }
    }

    function setCell($row, $col, $value)
    {
        $this->matrix[$row][$col] = array($value => $value);    //row
        for ($i = 0; $i < 9; $i++) {
            if ($i != $col) {
                if (!$this->removeValue($row, $i, $value)) {
                    return false;
                }
            }
        }    //col
        for ($i = 0; $i < 9; $i++) {
            if ($i != $row) {
                if (!$this->removeValue($i, $col, $value)) {
                    return false;
                }
            }
        }    //square
        $rs = intval($row / 3) * 3;
        $cs = intval($col / 3) * 3;
        for ($i = $rs; $i < $rs + 3; $i++) {
            for ($j = $cs; $j < $cs + 3; $j++) {
                if ($i != $row && $j != $col) {
                    if (!$this->removeValue($i, $j, $value)) return false;
                }
            }
        }
        return true;
    }

    function removeValue($row, $col, $value)
    {
        $count = count($this->matrix[$row][$col]);
        if ($count == 1) {
            $ret = !isset($this->matrix[$row][$col][$value]);
            return $ret;
        }
        if (isset($this->matrix[$row][$col][$value])) {
            unset($this->matrix[$row][$col][$value]);
            if ($count - 1 == 1) {
                return $this->setCell($row, $col, current($this->matrix[$row][$col]));
            }
        }
        return true;
    }

    function set($arr)
    {
        for ($i = 0; $i < 9; $i++) {
            for ($j = 0; $j < 9; $j++) {
                if ($arr[$i][$j] > 0) {
                    $this->setCell($i, $j, $arr[$i][$j]);
                }
            }
        }
    }

    function dump()
    {
        for ($i = 0; $i < 9; $i++) {
            for ($j = 0; $j < 9; $j++) {
                $c = count($this->matrix[$i][$j]);
                if ($c == 1) {
                    echo " " . current($this->matrix[$i][$j]) . " ";
                } else {
                    echo "(" . $c . ")";
                }
            }
            echo "<br/>";
        }
        echo "<br/>";
    }

    function dumpAll()
    {
        for ($i = 0; $i < 9; $i++) {
            for ($j = 0; $j < 9; $j++) {
                echo implode('', $this->matrix[$i][$j]), "/t";
            }
            echo "<br/>";
        }
        echo "<br/>";
    }

    function calc($data)
    {
        $this->clear();
        $this->set($data);
        $this->_calc();
        $this->dump();
    }

    function _calc()
    {
        for ($i = 0; $i < 9; $i++) {
            for ($j = 0; $j < 9; $j++) {
                if (count($this->matrix[$i][$j]) == 1) {
                    continue;
                }
                foreach ($this->matrix[$i][$j] as $v) {
                    $flag = false;
                    $t = new Sudoku($this->matrix);
                    if (!$t->setCell($i, $j, $v)) {
                        continue;
                    }
                    if (!$t->_calc()) {
                        continue;
                    }
                    $this->matrix = $t->matrix;
                    return true;
                }
                return false;
            }
        }
        return true;
    }
}

$re = new Sudoku();
//数组元素为0的，需要求解
$re->calc(array(
    array(0, 5, 0, 0, 0, 6, 0, 9, 0),
    array(0, 4, 7, 0, 8, 2, 6, 0, 0),
    array(0, 8, 0, 0, 0, 7, 0, 5, 2),
    array(7, 0, 1, 0, 3, 4, 0, 0, 6),
    array(0, 3, 0, 0, 2, 0, 0, 8, 0),
    array(2, 0, 0, 0, 0, 1, 9, 0, 4),
    array(4, 7, 0, 1, 0, 0, 0, 6, 0),
    array(0, 0, 9, 4, 6, 0, 3, 7, 0),
    array(0, 1, 0, 2, 0, 0, 0, 4, 0),
    )
);
$re->calc(array(
    array(1, 0, 0, 0, 0, 6, 9, 0, 0),
    array(0, 0, 0, 9, 0, 0, 0, 0, 5),
    array(2, 0, 0, 1, 0, 0, 0, 0, 3),
    array(0, 0, 5, 3, 0, 7, 0, 2, 0),
    array(3, 0, 0, 6, 0, 0, 0, 0, 1),
    array(0, 1, 0, 4, 0, 0, 8, 0, 0),
    array(9, 0, 0, 0, 0, 2, 0, 0, 7),
    array(5, 0, 0, 0, 0, 9, 0, 0, 0),
    array(0, 0, 3, 7, 0, 0, 0, 0, 4),
    )
);

输出如下：

更多关于PHP相关专题：《PHP数据结构与算法教程》、《PHP数组(Array)操作技巧大全》、《php字符串(string)用法总结》、《php程序设计算法总结》、《php排序算法总结》、《PHP常用遍历算法与技巧总结》、《PHP数学运算技巧总结》及《php常见数据库操作技巧汇总》

以上就是本文PHP 数独求解的程序实现的全部内容，希望本文所述对大家PHP程序设计有所帮助。