当前位置:Gxlcms > PHP教程 > PHP实现数独求解问题的方法

PHP实现数独求解问题的方法

时间:2021-07-01 10:21:17 帮助过:33人阅读

这篇文章主要介绍了PHP实现的数独求解问题,涉及php数组与字符串的遍历、比较、判断、运算等相关操作技巧,需要的朋友可以参考下

本文实例讲述了PHP实现的数独求解问题。分享给大家供大家参考,具体如下:

一、数独问题描述:

对于给出的数字二维数组,要求每行每列的数字不能重复。

二、实现代码:

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

运行结果如下:

  1. 1 5 2 3 4 6 7 9 8
  2. 9 4 7 5 8 2 6 1 3
  3. 3 8 6 9 1 7 4 5 2
  4. 7 9 1 8 3 4 5 2 6
  5. 5 3 4 6 2 9 1 8 7
  6. 2 6 8 7 5 1 9 3 4
  7. 4 7 3 1 9 8 2 6 5
  8. 8 2 9 4 6 5 3 7 1
  9. 6 1 5 2 7 3 8 4 9
  10. 1 3 7 2 5 6 9 4 8
  11. 4 6 8 9 7 3 2 1 5
  12. 2 5 9 1 8 4 6 7 3
  13. 6 8 5 3 1 7 4 2 9
  14. 3 9 4 6 2 8 7 5 1
  15. 7 1 2 4 9 5 8 3 6
  16. 9 4 6 5 3 2 1 8 7
  17. 5 7 1 8 4 9 3 6 2
  18. 8 2 3 7 6 1 5 9 4
  19. 7 3 8 1 9 6 4 2 5
  20. 2 9 6 3 4 5 7 8 1
  21. 4 5 1 2 7 8 3 9 6
  22. 5 6 9 7 8 4 2 1 3
  23. 3 8 2 5 1 9 6 7 4
  24. 1 7 4 6 2 3 8 5 9
  25. 6 2 7 4 5 1 9 3 8
  26. 8 4 5 9 3 2 1 6 7
  27. 9 1 3 8 6 7 5 4 2
  28. 9 5 1 3 6 7 4 2 8
  29. 7 8 3 1 4 2 5 6 9
  30. 2 4 6 9 5 8 7 3 1
  31. 6 2 9 4 7 5 8 1 3
  32. 8 7 5 6 1 3 2 9 4
  33. 1 3 4 2 8 9 6 5 7
  34. 4 6 7 5 9 1 3 8 2
  35. 3 1 8 7 2 6 9 4 5
  36. 5 9 2 8 3 4 1 7 6

以上就是本文的全部内容,希望对大家的学习有所帮助。


相关推荐:

PHP的Yii框架中行为的定义与绑定方法讲解_php技巧

PHP的Yii框架中移除组件所绑定的行为的方法_php技巧

详解PHP的Yii框架中组件行为的属性注入和方法注入_php技巧

以上就是PHP实现数独求解问题的方法的详细内容,更多请关注Gxl网其它相关文章!

人气教程排行