• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

数独 php

原作者: [db:作者] 来自: [db:来源] 收藏 邀请
 

数独求解程序 php版



1
<?php 2 class Sudoku { 3 var $matrix; 4 5 function __construct($arr = null) { 6 if ($arr == null) { 7 $this->clear(); 8 } else { 9 $this->matrix = $arr; 10 } 11 } 12 13 function clear() { 14 for($i=0; $i<9; $i++) { 15 for($j=0; $j<9; $j++) { 16 $this->matrix[$i][$j] = array(); 17 for ($k = 1; $k <= 9; $k++) { 18 $this->matrix[$i][$j][$k] = $k; 19 } 20 } 21 } 22 } 23 24 function setCell($row, $col, $value){ 25 $this->matrix[$row][$col] = array($value => $value); 26 //row 27 for($i = 0; $i < 9; $i++){ 28 if($i != $col){ 29 if(! $this->removeValue($row, $i, $value)) { 30 return false; 31 } 32 } 33 } 34 //col 35 for($i = 0; $i < 9; $i++){ 36 if($i != $row){ 37 if(! $this->removeValue($i, $col, $value)) { 38 return false; 39 } 40 } 41 } 42 //square 43 $rs=intval($row / 3) * 3; 44 $cs=intval($col / 3) * 3; 45 46 for($i = $rs; $i < $rs + 3; $i++){ 47 for($j = $cs; $j < $cs + 3; $j++){ 48 if($i != $row && $j != $col){ 49 if(! $this->removeValue($i, $j, $value)) 50 return false; 51 } 52 } 53 } 54 return true; 55 } 56 57 function removeValue($row, $col, $value) { 58 $count = count($this->matrix[$row][$col]); 59 if($count == 1){ 60 $ret = !isset($this->matrix[$row][$col][$value]); 61 return $ret; 62 } 63 if (isset($this->matrix[$row][$col][$value])) { 64 unset($this->matrix[$row][$col][$value]); 65 if($count - 1 == 1) { 66 return $this->setCell($row, $col, current($this->matrix[$row][$col])); 67 } 68 } 69 return true; 70 } 71 72 function set($arr) { 73 for ($i = 0; $i < 9; $i++) { 74 for ($j = 0; $j < 9; $j++) { 75 if ($arr[$i][$j] > 0) { 76 $this->setCell($i, $j, $arr[$i][$j]); 77 } 78 } 79 } 80 } 81 82 function dump() { 83 for($i = 0; $i < 9; $i++){ 84 for($j = 0; $j < 9; $j++){ 85 $c = count($this->matrix[$i][$j]); 86 if($c == 1){ 87 echo " ".current($this->matrix[$i][$j])." "; 88 } else { 89 echo "(".$c.")"; 90 } 91 } 92 echo "\n"; 93 } 94 echo "\n"; 95 } 96 97 function dumpAll() { 98 for($i = 0; $i < 9; $i++){ 99 for($j = 0; $j < 9; $j++){ 100 echo implode(\'\', $this->matrix[$i][$j]), "\t"; 101 } 102 echo "\n"; 103 } 104 echo "\n"; 105 } 106 107 function calc($data) { 108 $this->clear(); 109 $this->set($data); 110 $this->_calc(); 111 $this->dump(); 112 } 113 114 function _calc() { 115 for($i = 0; $i < 9; $i++){ 116 for($j = 0; $j < 9; $j++){ 117 if(count($this->matrix[$i][$j]) == 1) { 118 continue; 119 } 120 foreach($this->matrix[$i][$j] as $v){ 121 $flag = false; 122 $t = new Sudoku($this->matrix); 123 if(!$t->setCell($i, $j, $v)){ 124 continue; 125 } 126 if(!$t->_calc()){ 127 continue; 128 } 129 $this->matrix = $t->matrix; 130 return true; 131 } 132 return false; 133 } 134 } 135 return true; 136 } 137 } 138 139 $sd=new Sudoku; 140 $sd->calc(array( 141 array(0,5,0,0,0,6,0,9,0), 142 array(0,4,7,0,8,2,6,0,0), 143 array(0,8,0,0,0,7,0,5,2), 144 array(7,0,1,0,3,4,0,0,6), 145 array(0,3,0,0,2,0,0,8,0), 146 array(2,0,0,0,0,1,9,0,4), 147 array(4,7,0,1,0,0,0,6,0), 148 array(0,0,9,4,6,0,3,7,0), 149 array(0,1,0,2,0,0,0,4,0), 150 )); 151 152 $sd->calc(array( 153 array(1,0,0,0,0,6,9,0,0), 154 array(0,0,0,9,0,0,0,0,5), 155 array(2,0,0,1,0,0,0,0,3), 156 array(0,0,5,3,0,7,0,2,0), 157 array(3,0,0,6,0,0,0,0,1), 158 array(0,1,0,4,0,0,8,0,0), 159 array(9,0,0,0,0,2,0,0,7), 160 array(5,0,0,0,0,9,0,0,0), 161 array(0,0,3,7,0,0,0,0,4), 162 )); 163 164 $sd->calc(array( 165 array(7,0,0,1,0,0,0,0,5), 166 array(0,0,6,0,4,0,0,8,0), 167 array(0,0,1,0,0,0,0,0,0), 168 array(0,6,0,0,8,0,0,0,3), 169 array(0,8,0,0,0,9,0,7,0), 170 array(1,0,0,0,0,0,0,5,0), 171 array(0,0,0,0,0,0,9,0,0), 172 array(0,4,0,0,3,0,1,0,0), 173 array(9,0,0,0,0,7,0,0,2), 174 )); 175 176 $sd->calc(array( 177 array(0,5,0,0,0,0,0,2,0), 178 array(0,0,3,1,0,0,5,0,0), 179 array(0,0,6,0,0,8,0,0,0), 180 array(6,0,0,0,0,0,0,1,0), 181 array(8,0,0,6,0,0,0,0,4), 182 array(0,3,0,0,0,9,0,0,7), 183 array(0,0,0,5,0,0,3,0,0), 184 array(0,0,8,0,0,6,9,0,0), 185 array(0,9,0,0,0,0,0,7,0), 186 ));

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
PHP上传文件和下载 - 头大的冯冯发布时间:2022-07-10
下一篇:
php继承---trait代码复用发布时间:2022-07-10
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap