时间:2021-07-01 10:21:17 帮助过:33人阅读
本文实例讲述了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的Yii框架中行为的定义与绑定方法讲解_php技巧
PHP的Yii框架中移除组件所绑定的行为的方法_php技巧
详解PHP的Yii框架中组件行为的属性注入和方法注入_php技巧
以上就是PHP实现数独求解问题的方法的详细内容,更多请关注Gxl网其它相关文章!