PHP实现的数独求解问题示例
更新时间:2017年4月26日 22:11 点击:1313
本文实例讲述了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程序设计有所帮助。
相关文章
- 这篇文章主要介绍了源码分析系列之json_encode()如何转化一个对象,对json_encode()感兴趣的同学,可以参考下...2021-04-22
- PHP去除html、css样式、js格式的方法很多,但发现,它们基本都有一个弊端:空格往往清除不了 经过不断的研究,最终找到了一个理想的去除html包括空格css样式、js 的PHP函数。...2013-08-02
- index.php怎么打开?初学者可能不知道如何打开index.php,不会的同学可以参考一下本篇教程 打开编辑:右键->打开方式->经文本方式打开打开运行:首先你要有个支持运行PH...2017-07-06
PHP中func_get_args(),func_get_arg(),func_num_args()的区别
复制代码 代码如下:<?php function jb51(){ print_r(func_get_args()); echo "<br>"; echo func_get_arg(1); echo "<br>"; echo func_num_args(); } jb51("www","j...2013-10-04- 这篇文章主要介绍了PHP编程 SSO详细介绍及简单实例的相关资料,这里介绍了三种模式跨子域单点登陆、完全跨单点域登陆、站群共享身份认证,需要的朋友可以参考下...2017-01-25
- 这篇文章主要介绍了PHP实现创建以太坊钱包转账等功能,对以太坊感兴趣的同学,可以参考下...2021-04-20
- 这篇文章主要为大家详细介绍了php微信公众账号开发之五个坑,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2016-10-02
- 这篇文章主要介绍了PHP如何通过date() 函数格式化显示时间,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-11-13
ThinkPHP使用心得分享-ThinkPHP + Ajax 实现2级联动下拉菜单
首先是数据库的设计。分类表叫cate.我做的是分类数据的二级联动,数据需要的字段有:id,name(中文名),pid(父id). 父id的设置: 若数据没有上一级,则父id为0,若有上级,则父id为上一级的id。数据库有内容后,就可以开始写代码,进...2014-05-31- 这篇文章主要介绍了golang与php实现计算两个经纬度之间距离的方法,结合实例形式对比分析了Go语言与php进行经纬度计算的相关数学运算技巧,需要的朋友可以参考下...2016-07-29
- 这篇文章主要介绍了PHP正则表达式过滤html标签属性的相关内容,实用性非常,感兴趣的朋友参考下吧...2016-05-06
- 这篇文章主要为大家详细介绍了php构造方法中析构方法在继承中的表现,感兴趣的小伙伴们可以参考一下...2016-04-15
- 这篇文章主要介绍了thinkPHP中多维数组的遍历方法,以简单实例形式分析了thinkPHP中foreach语句的使用技巧,需要的朋友可以参考下...2016-01-12
- 这篇文章主要介绍了PHP如何使用cURL实现Get和Post请求,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-07-11
- 今天我给大家分享的是在不刷新页面的前提下,使用PHP+jQuery+Ajax实现多图片上传的效果。用户只需要点击选择要上传的图片,然后图片自动上传到服务器上并展示在页面上。...2015-03-15
- 这篇文章主要介绍了PHP简单实现生成txt文件到指定目录的方法,简单对比分析了PHP中fwrite及file_put_contents等函数的使用方法,需要的朋友可以参考下...2016-04-28
- 这篇文章主要介绍了php判断邮箱地址是否存在的方法,php判断邮箱地址是否存在的方法有两种,感兴趣的朋友可以参考一下...2016-02-18
- 下面小编就为大家带来一篇thinkphp自定义权限管理之名称判断方法。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2017-04-03
- 在php中switch是选择,if else也有同理,但是它们肯定是有区别的,那么我们来看看它们两者的区别在哪里呢,下面先看switch case语句吧。 switch($id){ case 1: ...2016-11-25
- Sodium 出现的目的也是为了代替Mcrypt这个原来的加密扩展。在 PHP7.2 之后,Mcrypt已经被移除,在PHP7.1时就已经被标记为过时。不过,Sodium扩展的应用也并不是很多,大部分情况下我们都会使用OpenSSL来进行加密操作,所以,我们这篇文章只做了解即可。...2021-06-17