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相关内容感兴趣的读者可查看本站专题:《PHP数据结构与算法教程》、《PHP数组(Array)操作技巧大全》、《php字符串(string)用法总结》、《php程序设计算法总结》、《php排序算法总结》、《PHP常用遍历算法与技巧总结》、《PHP数学运算技巧总结》及《php常见数据库操作技巧汇总》

希望本文所述对大家PHP程序设计有所帮助。

(0)

相关推荐

  • php数字转汉字代码(算法)

    复制代码 代码如下: //将数字转换为汉字,比如1210转换为一千二百一十 $num = "842105580";//九位数 function del0($num) //去掉数字段前面的0 { return "".intval($num); } function n2c($x) //单个数字变汉字 { $arr_n = array("零","一","二","三","四"

  • JavaScript遍历求解数独问题的主要思路小结

    数独规则 数独游戏,经典的为9×9=81个单元格组成的九宫格,同时也形成了3×3=9个小九宫格,要求在81个小单元格中填入数字1~9,并且数字在每行每列及每个小九宫格中都不能重复. 数独技巧 直观法 候选数法 相关二十格:一个数字只与其所在行列及小九宫格的二十格相关 我的思路 精心设计了有效性判定函数,最多一次遍历81个小单元格就能做出方案的有效性判定. 同理设计了相关20格判定,一次0~9的循环就完成有效性判定. 用数组模拟堆栈,为搜索提供回溯信息. 利用对象具有map性质,来辅助判断方案的有

  • php中最简单的字符串匹配算法

    本文实例讲述了php中最简单的字符串匹配算法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: <?php /* 最简单字符串匹配算法php实现方式   T: ababcabc P: abc   0.          1.          2. ababcabc    ababcabc    ababcabc |||          |||          ||| abc          abc          abc (X)          (X)         

  • PHP实现的方程求解示例分析

    本文实例讲述了PHP实现的方程求解.分享给大家供大家参考,具体如下: 一.需求 1. 给出一个平均值X,反过来求出来,得到这个平均值X的三个数X1 ,X2, X3,最大值与最小值的差值要小于0.4(X1-X3都是保留1位小数的数) 2. 这三个数X1, X2, X3代表了三组数.满足下面的公式: X1 = [(m1 - m2)/(m1 - m0) ] * 100 (@1); m0, m1, m2三个数的边界条件如下: 1)48<m0<51 2)0.45<m1 - m1<0.55 3

  • python实现数独算法实例

    本文实例讲述了python实现数独算法的方法.分享给大家供大家参考.具体如下: # -*- coding: utf-8 -*- ''' Created on 2012-10-5 @author: Administrator ''' from collections import defaultdict import itertools a = [ [ 0, 7, 0, 0, 0, 0, 0, 0, 0], #0 [ 5, 0, 3, 0, 0, 6, 0, 0, 0], #1 [ 0, 6, 2

  • php 大数据量及海量数据处理算法总结

    下面的方法是我对海量数据的处理方法进行了一个一般性的总结,当然这些方法可能并不能完全覆盖所有的问题,但是这样的一些方法也基本可以处理绝大多数遇到的问题.下面的一些问题基本直接来源于公司的面试笔试题目,方法不一定最优,如果你有更好的处理方法,欢迎与我讨论. 1.Bloom filter 适用范围:可以用来实现数据字典,进行数据的判重,或者集合求交集 基本原理及要点: 对于原理来说很简单,位数组+k个独立hash函数.将hash函数对应的值的位数组置1,查找时如果发现所有hash函数对应位都是1说明

  • 适用于抽奖程序、随机广告的PHP概率算法实例

    那么我们在程序里必然会设计到算法,即按照一定的概率让用户获得奖品.先来看两个概率算法函数. 算法一 复制代码 代码如下: /** * 全概率计算 * * @param array $p array('a'=>0.5,'b'=>0.2,'c'=>0.4) * @return string 返回上面数组的key */function random($ps){    static $arr = array();    $key = md5(serialize($ps)); if (!isset

  • Java实现解数独的小程序

    前言 数独相信很多人都玩过,趣味性很强,十分的耐玩.可有没有程序员想过玩实现一个数独布局的算法呢?算法是个很有意思,很神奇的东西. 算法如下,需要预先给出几个固定的值,目前解决的一个最难的数独是大概26个已知值的情况,理论上应该能解决任意已知值的数独,不过不知道会不会迭代栈溢出--因为在26个已知值的情况下就迭代了3000多次了,囧~~~ 结果显示如下: 这是已知值: 1 1 2 1 4 8 1 5 5 1 6 1 1 7 7 1 8 3 2 1 1 2 2 6 2 4 4 3 5 9 3 7

  • php编写的抽奖程序中奖概率算法

    们先完成后台PHP的流程,PHP的主要工作是负责配置奖项及对应的中奖概率,当前端页面点击翻动某个方块时会想后台PHP发送ajax请求,那么后台PHP根据配置的概率,通过概率算法给出中奖结果,同时将未中奖的奖项信息一并以JSON数据格式发送给前端页面. 先来看概率计算函数 function get_rand($proArr) { $result = ''; //概率数组的总概率精度 $proSum = array_sum($proArr); //概率数组循环 foreach ($proArr as

  • JQuery开发的数独游戏代码

    用了很多Jquery的插件,支持鼠标滚轮选数字.没有什么高深的技术点.工作原因很长时间没有更新了,具体代码都有些记不清了,欢迎大家来拍砖.截图:演示地址:http://demo.jb51.net/js/jsukudo/index.html下载地址:jsukudo20081110v0.3.0.5.zip 下载列表:http://code.google.com/p/jsukudo/downloads/list 用到的JS文件 文件名 出处 说明 blockUI.js http://malsup.co

  • PHP经典算法集锦【经典收藏】

    本文实例总结了PHP经典算法.分享给大家供大家参考,具体如下: 1.首先来画个菱形玩玩,很多人学C时在书上都画过,咱们用PHP画下,画了一半. 思路:多少行for一次,然后在里面空格和星号for一次. <?php for($i=0;$i<=3;$i++){ echo str_repeat(" ",3-$i); echo str_repeat("*",$i*2+1); echo '<br/>'; } 2.冒泡排序,C里基础算法,从小到大对一组数

  • c++递归解数独方法示例

    复制代码 代码如下: #include<iostream> using namespace std; void init();void function(int m); int canplace(int row,int col,int c); void outputresult(); int a[9][9], maxm = 0; int main() {   init(); function(0);  return 0; } void init(){ int i, j; for(i = 0;

  • Go语言实现的最简单数独解法

    soduku.go 复制代码 代码如下: package main import (     "fmt" ) type node []int var sudokuMay [9][9]node var Sudoku = [9][9]int{     {0, 0, 0, 0, 0, 0, 8, 0, 0},     {0, 8, 2, 4, 0, 0, 0, 0, 0},     {1, 9, 0, 0, 6, 3, 0, 0, 0},     {0, 5, 0, 0, 8, 0, 7,

随机推荐