澳门新葡萄京官网首页:PHP实现的数独求解问题示例,PHP实现的方程求解示例分析

正文实例陈诉了PHP达成的数独求解难点。分享给大家供我们参照他事他说加以考察,具体如下:

求解数独的C++实现##

本文实例陈诉了PHP完成的方程求解。分享给大家供我们参谋,具体如下:

#include <iostream>

int get_flag(int x, int flag)
{
    return flag & (1 << (x - 1));
}

int set_flag(int x, int flag)
{
    return flag | (1 << (x - 1));
}

int reset_flag(int x, int flag)
{
    return flag & (~(1 << (x - 1)));
}

bool solve_sudoku(int x, int y, int flag[3][9], int map[9][9])
{
    if (x == 9)
        return true;

    if (map[x][y] != 0)
        return solve_sudoku(x+(y+1)/9, (y+1)%9, flag, map);

    for (int i = 1; i <= 9; i++) {
        int b = get_flag(i, flag[0][x]);
        b |= get_flag(i, flag[1][y]);
        b |= get_flag(i, flag[2][x/3*3+y/3]);
        if (!b) {
            flag[0][x] = set_flag(i, flag[0][x]);
            flag[1][y] = set_flag(i, flag[1][y]);
            flag[2][x/3*3+y/3] = set_flag(i, flag[2][x/3*3+y/3]);
            if (solve_sudoku(x+(y+1)/9, (y+1)%9, flag, map)) {
                map[x][y] = i;
                return true;
            }
            flag[0][x] = reset_flag(i, flag[0][x]);
            flag[1][y] = reset_flag(i, flag[1][y]);
            flag[2][x/3*3+y/3] = reset_flag(i, flag[2][x/3*3+y/3]);
        }
    }

    return false;
}

void sudoku(int map[9][9])
{
    int flag[3][9];
    for (int i = 0; i < 9; i++)
        flag[0][i] = flag[1][i] = flag[2][i] = 0;
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++)
            if (map[i][j]) {
                flag[0][i] = set_flag(map[i][j], flag[0][i]);
                flag[1][j] = set_flag(map[i][j], flag[1][j]);
                flag[2][i/3*3+j/3] = set_flag(map[i][j], flag[2][i/3*3+j/3]);
             }
    solve_sudoku(0, 0, flag, map);
}

void print(int map[9][9])
{
    std::cout << "┏";
    for (int i = 0; i < 8; i++)
        if (i == 2 || i == 5)
            std::cout << "━━━┳";
        else
            std::cout << "━━━━";
    std::cout << "━━━┓" << std::endl;
    for (int i = 0; i < 9; i++) {
        std::cout << "┃";
        for (int j = 0; j < 9; j++) {
            std::cout << " " << map[i][j] << " ";
            if (j % 3 == 2)
                std::cout << "┃";
            else
                std::cout << " ";
        }
        std::cout << std::endl;
        if (i == 2 || i == 5) {
            std::cout << "┣";
            for (int j = 0; j < 8; j++)
                if (j == 2 || j == 5)
                    std::cout << "━━━╋";
                else
                    std::cout << "━━━━";
            std::cout << "━━━┫" << std::endl;
        } else if (i < 8) {
            std::cout << "┃";
            for (int j = 0; j < 8; j++)
                if (j == 2 || j == 5)
                    std::cout << "   ┃";
                else
                    std::cout << "    ";
             std::cout << "   ┃" << std::endl;
        }
    }
    std::cout << "┗";
    for (int i = 0; i < 8; i++)
        if (i == 2 || i == 5)
            std::cout << "━━━┻";
        else
            std::cout << "━━━━";
    std::cout << "━━━┛" << std::endl;
}

int main()
{
    int map[9][9] = {
        0, 0, 1, 0, 0, 0, 6, 0, 0,
        0, 5, 9, 0, 0, 2, 0, 0, 0,
        4, 0, 0, 0, 0, 6, 0, 0, 2,
        0, 0, 0, 8, 7, 0, 0, 1, 0,
        2, 0, 0, 0, 9, 0, 0, 0, 7,
        0, 4, 0, 0, 5, 3, 0, 0, 0,
        8, 0, 0, 5, 0, 0, 0, 0, 6,
        0, 0, 0, 1, 0, 0, 7, 9, 0,
        0, 0, 4, 0, 0, 0, 5, 0, 0,
    };
    print(map);
    sudoku(map);
    print(map);
    return 0;
}
//该片段来自于http://outofmemory.cn

一、数独难题汇报:

动机##\

在做数独的时候,抱着好奇心想做三个数独求解的次第。
澳门新葡萄京官网首页:PHP实现的数独求解问题示例,PHP实现的方程求解示例分析。及时本身并不曾接触多少算法,也是抱着试试看看的心情编写了这几个数独求解器。

一、需求

对于给出的数字二维数组,供给每行每列的数字不可能重新。

情势独的不二法门##\

要写二个求解数独的次第,要求求线弄驾驭要用什么点子去求解数独。一般是行使简易的摒除法,然则事实上摒除法并无法做相比高等的数独。深究下去开掘较高端的数独可用的不二等秘书诀多达十种,何况面对分裂的数独要使用分歧的方法,相应的算法打码量十二分不小,何况并从未八个确定的套路。Computer长于重复单调职业,为了程序能越来越好的设计,笔者设想动用候选数法,在候选数法不能够收获解的时候利用寻觅的主意,那样能保险一定的性质下自然能求出一个数独的解。

  1. 交付二个平均值X,反过来求出来,获得那几个平均值X的多个数X1 ,X2,
    X3,最大值与最小值的差值要低于0.4(X1-X3都以保存1位小数的数)
  2. 那多少个数X1, X2, X3意味着了三组数。满意上面包车型地铁公式: X1 = [(m1 – m2)/(m1

二、完成代码:

统一策画思路##\

  • m0) ] * 100 (@1);
<?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

求解数独框架

(自豪地运用processon)

m0, m1, m2两个数的境界条件如下:

相关文章