时间:2021-05-26
本文实例讲述了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程序设计有所帮助。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文实例讲述了Java基于二维数组实现的数独问题。分享给大家供大家参考,具体如下:这里利用Java二维数组实现数独问题。(1)生成简易数独(2)生成数独问题**
什么是求素数素数指的是因子只有1和本身的数(1不是素数),求解素数在数学上应用非常广泛,而求解n以内的素数也是我们编程时常遇到的问题,在这个问题上,筛选法求解素
前言数独是一种有趣的智力游戏,但是部分高难度数独在求解过程中经常出现大量单元格有多个候选数字可以填入,不得不尝试填写某个数字然后继续推导的方法。不幸的是这种方法
如何用php生成1-10之间的不重复随机数?例1,使用shuffle函数生成随机数。例2,使用array_unique函数生成随机数。php随机数生成函数示例
本文实例讲述了PHP实现求两个字符串最长公共子串的方法。分享给大家供大家参考,具体如下:前面一篇PHP实现求解最长公共子串问题的方法是基于java改进而来,这里