欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

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

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

本文实例讲述了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实现数独求解问题的方法的详细内容,更多请关注其它相关文章!

相关标签: php 方法 题的