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

# PHP  # 数独求解  # 问题  # Java实现解数独的小程序  # JavaScript遍历求解数独问题的主要思路小结  # python实现数独算法实例  # Go语言实现的最简单数独解法  # c++递归解数独方法示例  # JQuery开发的数独游戏代码  # PHP实现的方程求解示例分析  # PHP经典算法集锦【经典收藏】  # php编写的抽奖程序中奖概率算法  # php 大数据量及海量数据处理算法总结  # 适用于抽奖程序、随机广告的PHP概率算法实例  # php中最简单的字符串匹配算法  # php数字转汉字代码(算法)  # 数独  # 程序设计  # 操作技巧  # 相关内容  # 遍历  # 感兴趣  # 数据结构  # 给大家  # 更多关于  # 所述  # 讲述了  # matrix  # function  # __construct  # Sudoku  # var  # arr  # array  # setCell  # row 

相关文章： 北京网页设计制作网站有哪些,继续教育自动播放怎么设置？  装修招标网站设计制作流程,装修招标流程？  香港服务器部署网站为何提示未备案？  建站之星导航如何优化提升用户体验？  自助网站制作软件,个人如何自助建网站？  如何配置IIS站点权限与局域网访问？  湖南网站制作公司,湖南上善若水科技有限公司做什么的？  专业制作网站的公司哪家好,建立一个公司网站的费用.有哪些部分,分别要多少钱？  如何获取上海专业网站定制建站电话？  图片制作网站免费软件,有没有免费的网站或软件可以将图片批量转为A4大小的pdf？  网站建设制作需要多少钱费用,自己做一个网站要多少钱，模板一般多少钱？  企业网站制作公司网页,推荐几家专业的天津网站制作公司？  广州美橙建站如何快速搭建多端合一网站？  如何确保西部建站助手FTP传输的安全性？  制作门户网站的参考文献在哪,小说网站怎么建立？  购物网站制作公司有哪些,哪个购物网站比较好？  如何快速搭建高效可靠的建站解决方案？  如何通过虚拟机搭建网站？详细步骤解析  已有域名建站全流程解析：网站搭建步骤与建站工具选择  建站之星如何开启自定义404页面避免用户流失？  如何在云虚拟主机上快速搭建个人网站？  c++如何打印函数堆栈信息_c++ backtrace函数与符号名解析【方法】  微信网站制作公司有哪些,民生银行办理公司开户怎么在微信网页上查询进度？  如何使用Golang安装API文档生成工具_快速生成接口文档  已有域名能否直接搭建网站？  网站制作软件免费下载安装,有哪些免费下载的软件网站？  python的本地网站制作,如何创建本地站点？  如何在景安服务器上快速搭建个人网站？  建站主机选哪种环境更利于SEO优化？  深圳网站制作平台,深圳市做网站好的公司有哪些？  宿州网站制作公司兴策,安徽省低保查询网站？  西安大型网站制作公司,西安招聘网站最好的是哪个？  在线制作视频网站免费,都有哪些好的动漫网站？  如何有效防御Web建站篡改攻击？  北京网站制作费用多少,建立一个公司网站的费用.有哪些部分,分别要多少钱？  高端智能建站公司优选：品牌定制与SEO优化一站式服务  建站之星收费标准详解：套餐费用及年费价格表一览  建站之星下载版如何获取与安装？  制作网站外包平台,自动化接单网站有哪些？  如何快速打造个性化非模板自助建站？  义乌企业网站制作公司,请问义乌比较好的批发小商品的网站是什么？  网站插件制作软件免费下载,网页视频怎么下到本地插件？  如何基于云服务器快速搭建个人网站？  建站之星×万网：智能建站系统+自助建站平台一键生成  建站之星后台密码遗忘或太弱？如何重置与强化？  名字制作网站免费,所有小说网站的名字？  如何在IIS中新建站点并配置端口与物理路径？  如何基于云服务器快速搭建网站及云盘系统？  网站制作专业公司有哪些,如何制作一个企业网站，建设网站的基本步骤有哪些？  建站之星安装后界面空白如何解决？