PHP实现的数独求解问题示例

本文实例讲述了PHP实现的数独求解问题。分享给大家供大家参考，具体如下：

一、数独问题描述：

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

二、实现代码：

    <?php
    /* 数独求解程序
     * Created on 2017-4-18
     *
     */
     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 "\n";
        }
        echo "\n";
      }
      function dumpAll() {
        for($i = 0; $i < 9; $i++){
          for($j = 0; $j < 9; $j++){
            echo implode('', $this->matrix[$i][$j]), "\t";
          }
          echo "\n";
        }
        echo "\n";
      }
      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;
      }
    }
    $sd=new Sudoku;
    $sd->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),
    ));
    $sd->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),
    ));
    $sd->calc(array(
    array(7,0,0,1,0,0,0,0,5),
    array(0,0,6,0,4,0,0,8,0),
    array(0,0,1,0,0,0,0,0,0),
    array(0,6,0,0,8,0,0,0,3),
    array(0,8,0,0,0,9,0,7,0),
    array(1,0,0,0,0,0,0,5,0),
    array(0,0,0,0,0,0,9,0,0),
    array(0,4,0,0,3,0,1,0,0),
    array(9,0,0,0,0,7,0,0,2),
    ));
    $sd->calc(array(
    array(0,5,0,0,0,0,0,2,0),
    array(0,0,3,1,0,0,5,0,0),
    array(0,0,6,0,0,8,0,0,0),
    array(6,0,0,0,0,0,0,1,0),
    array(8,0,0,6,0,0,0,0,4),
    array(0,3,0,0,0,9,0,0,7),
    array(0,0,0,5,0,0,3,0,0),
    array(0,0,8,0,0,6,9,0,0),
    array(0,9,0,0,0,0,0,7,0),
    ));
    ?>

运行结果如下：

     1 5 2 3 4 6 7 9 8 
     9 4 7 5 8 2 6 1 3 
     3 8 6 9 1 7 4 5 2 
     7 9 1 8 3 4 5 2 6 
     5 3 4 6 2 9 1 8 7 
     2 6 8 7 5 1 9 3 4 
     4 7 3 1 9 8 2 6 5 
     8 2 9 4 6 5 3 7 1 
     6 1 5 2 7 3 8 4 9 

     1 3 7 2 5 6 9 4 8 
     4 6 8 9 7 3 2 1 5 
     2 5 9 1 8 4 6 7 3 
     6 8 5 3 1 7 4 2 9 
     3 9 4 6 2 8 7 5 1 
     7 1 2 4 9 5 8 3 6 
     9 4 6 5 3 2 1 8 7 
     5 7 1 8 4 9 3 6 2 
     8 2 3 7 6 1 5 9 4 

     7 3 8 1 9 6 4 2 5 
     2 9 6 3 4 5 7 8 1 
     4 5 1 2 7 8 3 9 6 
     5 6 9 7 8 4 2 1 3 
     3 8 2 5 1 9 6 7 4 
     1 7 4 6 2 3 8 5 9 
     6 2 7 4 5 1 9 3 8 
     8 4 5 9 3 2 1 6 7 
     9 1 3 8 6 7 5 4 2 

     9 5 1 3 6 7 4 2 8 
     7 8 3 1 4 2 5 6 9 
     2 4 6 9 5 8 7 3 1 
     6 2 9 4 7 5 8 1 3 
     8 7 5 6 1 3 2 9 4 
     1 3 4 2 8 9 6 5 7 
     4 6 7 5 9 1 3 8 2 
     3 1 8 7 2 6 9 4 5 
     5 9 2 8 3 4 1 7 6 

更多关于PHP相关内容感兴趣的读者可查看本站专题：《PHP数据结构与算法教程》、《PHP数组(Array)操作技巧大全》、《php字符串(string)用法总结》、《php程序设计算法总结》、《php排序算法总结》、《PHP常用遍历算法与技巧总结》、《PHP数学运算技巧总结》及《php常见数据库操作技巧汇总》

希望本文所述对大家PHP程序设计有所帮助。