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

php  /  管理员 发布于 7年前   336

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

一、数独问题描述：

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

二、实现代码：

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程序设计有所帮助。

您可能感兴趣的文章:

• Java实现解数独的小程序
• JavaScript遍历求解数独问题的主要思路小结
• python实现数独算法实例
• Go语言实现的最简单数独解法
• c++递归解数独方法示例
• JQuery开发的数独游戏代码
• PHP实现的方程求解示例分析
• PHP经典算法集锦【经典收藏】
• php编写的抽奖程序中奖概率算法
• php 大数据量及海量数据处理算法总结
• 适用于抽奖程序、随机广告的PHP概率算法实例
• php中最简单的字符串匹配算法
• php数字转汉字代码(算法)