数独破解PHP

莫愁
其他
2019-11-03

PHP

简介数独是一种比较费时费脑的游戏，一般难度的数独玩下来也得1个小时左右，本人是伪数独爱好者，碰到难点的数独需要花上若干个小时，于是偷懒写了一套破解程序，特拿出来分享，希望有人喜欢。
字数 5555

数独破解PHP

数独是一种比较费时费脑的游戏，一般难度的数独玩下来也得1个小时左右，本人是伪数独爱好者，碰到难点的数独需要花上若干个小时，于是偷懒写了一套破解程序，特拿出来分享，希望有人喜欢。

代码如下：

<?php

/* 数独求解程序
 * Created on 2019-11-03
 *
 */

class Sudoku
{
    public $matrix;

public function __construct($arr = null)
    {
        if ($arr == null) {
            $this->Clear();
        } else {
            $this->matrix = $arr;
        }
    }

//初始化所有序列 每一个方格放一个1到9的数组
 public function Clear()
 {
 for ($i = 0; $i < 9; $i++) {
 for ($j = 0; $j < 9; $j++) {
 $this->matrix[$i][$j][0] = array();
 for ($k = 1; $k <= 9; $k++) {
 $this->matrix[$i][$j][0][$k] = $k;
 }
 }
 }
 }

public function setCell($row, $col, $value)
 {
 $this->matrix[$row][$col][0] = 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;
 }

public function removeValue($row, $col, $value)
    {
        $count = count($this->matrix[$row][$col][0]);
        if ($count == 1) {
            $ret = !isSet($this->matrix[$row][$col][0][$value]);
            return $ret;
        }
        if (isSet($this->matrix[$row][$col][0][$value])) {
            unSet($this->matrix[$row][$col][0][$value]);
            if ($count - 1 == 1) {
                return $this->setCell($row, $col, current($this->matrix[$row][$col][0]));
            }
        }
        return true;
    }

public 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]);
 $this->matrix[$i][$j][1] = 1;
 } else {
 $this->matrix[$i][$j][1] = 0;
 }
 }
 }
 }

public function Dump()
 {
 for ($i = 0; $i < 9; $i++) {
 for ($j = 0; $j < 9; $j++) {
 if ($this->matrix[$i][$j][1]) {
 echo " " . $this->matrix[$i][$j][0] . " ";
 } else {
 echo " " . $this->matrix[$i][$j][0] . " ";
 }
 }
 echo "";
 }
 echo "";
 }

public function dumpRand($data)
 {
 for ($i = 0; $i < 9; $i++) {
 for ($j = 0; $j < 9; $j++) {
 if ($data[$i][$j] > 0) {
 echo " " . $data[$i][$j] . " ";
 } else {
 echo " " . $data[$i][$j] . " ";
 }
 }
 echo "";
 }
 echo "";
 }

public function Calc($data = Null)
    {
        $this->Clear();

$this->Set($data);

$this->_Calc();//进行运算

//将计算的数组转换为数字
        if (!$this->changeValue()) {
            echo "is false sudu";
            return false;
        }

$this->Dump();
        return $this->matrix;
    }

public function _Calc()
 {
 for ($i = 0; $i < 9; $i++) {
 for ($j = 0; $j < 9; $j++) {
 if (count($this->matrix[$i][$j][0]) == 1) {
 continue;
 }
 foreach ($this->matrix[$i][$j][0] 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;
    }

public function changeValue()
 {
 for ($i = 0; $i < 9; $i++) {
 for ($j = 0; $j < 9; $j++) {
 if (count($this->matrix[$i][$j][0]) != 1) {
 return false;
 }
 foreach ($this->matrix[$i][$j][0] as $value) {
 $this->matrix[$i][$j][0] = $value;
 }
 }
 }

return true;
    }

/*
     * 产生一个唯一解数独
     * */
    public function randSuDoKu()
    {
        $data = array(
            array(0, 0, 0, 0, 0, 0, 0, 0, 0),
            array(0, 0, 0, 0, 0, 0, 0, 0, 0),
            array(0, 0, 0, 0, 0, 0, 0, 0, 0),
            array(0, 0, 0, 0, 0, 0, 0, 0, 0),
            array(0, 0, 0, 0, 0, 0, 0, 0, 0),
            array(0, 0, 0, 0, 0, 0, 0, 0, 0),
            array(0, 0, 0, 0, 0, 0, 0, 0, 0),
            array(0, 0, 0, 0, 0, 0, 0, 0, 0),
            array(0, 0, 0, 0, 0, 0, 0, 0, 0),
        );
        while (1) {
            /*
             * 随机生成一个数独
             * */
            $this->Clear();

$arr = range(1, 9);
            shuffle($arr);
            foreach ($arr as $key => $value) {
                $a = intval($key / 3); //九宫格的行
                $b = $key % 3; //九宫格的列
                $data[$a][$b] = $value;
            }

$this->Set($data);

$this->_Calc();//进行运算
            $this->changeValue();//转换

$beginSuDu = $this->matrix; //保存已经计算了的数独

/*
             * 挖空该随机数独并重新计算
             * */
            $baoLiuArr = array(); //保留位置数组
            $baoLiuNum = rand(22, 24);// 保留数量
            $Num = 1;
            while (1) {
                $randAdd = rand(1, 80); //产生一个随机自增
                $Num = ($Num + $randAdd) % 81;
                array_push($baoLiuArr, $Num);
                $uniqueArr = array_unique($baoLiuArr);
                if (count($uniqueArr) > $baoLiuNum) {
                    $baoLiuArr = $uniqueArr;
                    break;
                }
            }

$waKongData = array(
 array(0, 0, 0, 0, 0, 0, 0, 0, 0),
 array(0, 0, 0, 0, 0, 0, 0, 0, 0),
 array(0, 0, 0, 0, 0, 0, 0, 0, 0),
 array(0, 0, 0, 0, 0, 0, 0, 0, 0),
 array(0, 0, 0, 0, 0, 0, 0, 0, 0),
 array(0, 0, 0, 0, 0, 0, 0, 0, 0),
 array(0, 0, 0, 0, 0, 0, 0, 0, 0),
 array(0, 0, 0, 0, 0, 0, 0, 0, 0),
 array(0, 0, 0, 0, 0, 0, 0, 0, 0),
 );
 //将已经计算的数独挖空
 for ($i = 0; $i < 9; $i++) {
 for ($j = 0; $j < 9; $j++) {
 $Num = $i * 9 + $j;//坐标
 if (in_array($Num, $baoLiuArr)) {
 $waKongData[$i][$j] = $beginSuDu[$i][$j][0];
 } else {
 $waKongData[$i][$j] = 0;
 }
 }
 }

$this->Clear();
            $this->Set($waKongData);
            //计算挖空 返回false重新找
            if (!$this->_Calc()) {
                continue;
            }

/*
            $this->changeValue();//转换
            $endSuDu = $this->matrix;

/* /*
 * 判断前后2个数独是否相同
 *
 for ($i = 0; $i < 9; $i++) {
 for ($j = 0; $j < 9; $j++) {
 if ($beginSuDu[$i][$j][0] != $endSuDu[$i][$j][0]) {
 continue 3;
 }
 }
 }
 */

$this->dumpRand($waKongData);

return $waKongData;
        }
    }

public function isShuDoKu($arr)
 {
 for ($i = 0; $i < 9; $i++) {
 for ($j = 0; $j < 9; $j++) {
 if ($this->squareISTure($i, $j, $arr)) {
 continue;
 } else {
 return false;
 }

}
        }

return true;
    }

public function squareISTure($a, $b, $arr)
 {
 //行项判断
 $row = array();
 for ($i = 0; $i < 9; $i++) {
 array_push($row, $arr[$a][$i][0]);
 }
 if (!(count(array_unique($row)) == 9)) {
 return false;
 }

//列项判断
 $col = array();
 for ($j = 0; $j < 9; $j++) {
 array_push($col, $arr[$j][$b][0]);
 }
 if (!(count(array_unique($col)) == 9)) {
 return false;
 }

//3*3判断
 $i = intval($a / 3) * 3;
 $j = intval($b / 3) * 3;
 $bigSquare = array();
 for ($a = 0; $a < 3; $a++) {
 for ($b = 0; $b < 3; $b++) {
 array_push($bigSquare, $arr[$i + $a][$j + $b][0]);
 }
 }
 if (!(count(array_unique($bigSquare)) == 9)) {
 return false;
 }

return true;
    }

}

$sd = new Sudoku;
$start_time = microtime(true);
$data = $sd->randSuDoKu();
$end_time = microtime(true);

echo 'computation time is:' , $end_time - $start_time . 's';

var_dump($sd->isShuDoKu($sd->Calc($data)));
/*$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(2, 3, 8, 0, 0, 0, 0, 0, 0),
    array(6, 1, 7, 0, 0, 0, 0, 0, 0),
    array(5, 4, 9, 0, 0, 0, 0, 0, 0),
    array(0, 0, 0, 0, 0, 0, 0, 0, 0),
    array(0, 0, 0, 0, 0, 0, 0, 0, 0),
    array(0, 0, 0, 0, 0, 0, 0, 0, 0),
    array(0, 0, 0, 0, 0, 0, 0, 0, 0),
    array(0, 0, 0, 0, 0, 0, 0, 0, 0),
    array(0, 0, 0, 0, 0, 0, 0, 0, 0)
));

$sd->Calc(array(
    array(0, 0, 0, 9, 1, 0, 4, 0, 6),
    array(5, 0, 0, 0, 0, 6, 0, 0, 0),
    array(1, 0, 4, 0, 8, 0, 0, 0, 0),
    array(7, 0, 0, 0, 0, 0, 0, 5, 0),
    array(0, 1, 0, 0, 0, 0, 0, 8, 0),
    array(0, 2, 0, 0, 0, 0, 0, 0, 3),
    array(0, 0, 0, 0, 6, 0, 1, 0, 9),
    array(0, 0, 0, 5, 0, 0, 0, 0, 2),
    array(4, 0, 1, 0, 7, 3, 0, 0, 0)
));*/

转载： 感谢您对莫愁个人博客网站平台的认可,非常欢迎各位朋友分享到个人站长或者朋友圈，但转载请说明文章出处“来源莫愁个人博客 https://www.mochoublog.com/study/364.html”。