算法-数独游戏算法原理

WP主题讨论 WP主题讨论 主题:1013 回复:2239

算法-数独游戏算法原理

瑾兮 发布于 2017-04-18 字数 258 浏览 1094 回复 3

最近有些许迷恋数独游戏,故想要自己实现一个数独算法。网上找了一些都是先把整个9宫格填充后再去掉并记录部分数字,从而在用户输入的时候判断是否错误。现在想自己直接在宫格里填些数字,然后让系统去自动填充剩余的部分。想知道下数独算法的原理,知道的请简单描述下。

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

支持 Markdown 语法,需要帮助?

评论(3

甜柠檬 2017-07-10 3 楼

数独的穷举搜索模式(回溯法):
从一个结点出发,试探假设,再站在假设的基础上继续试探,如果遇到矛盾,否定前一级试探,如果找到解,输出解,停止搜索.
算法原理:构建一棵搜索树(深度为9*9),然后对每一个格子用不同的数字进行尝试,如果不与数独构造法则冲突则继续搜索,否则返回到上一个节点换个数继续搜索。在搜索过程中,对于每一个数都要考察其是否满足数独规则,即是否与所在小矩阵中的数字重复和是否存在行列重复。此外如果运气不好的话搜索过程可能会很漫长。好处是生成的数独足够“随机”,除了数独规则外没有什么规律可循。

数独的逻辑搜索模式(矩阵变换法):
逻辑搜索是站在确定性基础上的,即‘永远只做一次假设’,不在假设的基础上再假设,就是说不用寻遍整个搜索树。
算法原理: 以中间的矩阵为中心,利用列变换生成2号和8号矩阵(我们将所有子矩阵按照行优先的顺序从1-9进行编号),再使用行变换生成4号和6号矩阵,最后分别用4号和6号矩阵利用列变换生成1号、7号矩阵和3号9号矩阵。这样就最重形成了一个合法的数独。

归属感 2017-05-11 2 楼

先把只有一种可能的数值的位置找出来并填充,然后用回溯法找出其余的。

清晨说ぺ晚安 2017-04-21 1 楼

写了一个能解决sudoku.name上hard以及以下难度数独,部分hard++也能解,但不是完全能解。里面采用了三个算法:

就是区内没有的数字,但其它区外有,那可以通过其它区的同一数字来排除,如果只能一个格剩下,那么该格就是该数字。
一个区的一个格要确定一个数字,那么必须是这格的纵横以及区内所有数字合并起来,如果刚好是1-9内少一个,那么就是少的那个数字。
实在1、2都没法确定,那说明是高阶数独了,只能猜了。但猜也是有技巧的,在1、2的基础上,如果不是刚好一个的话,那么可填数字是2个或者2个以上。那么,先猜2个之1,再猜3个之一。把这些都弄到一个存储区,一个个来猜,直到最后全对,否则重猜,重猜的时候要把猜之前备份的数据恢复。

<?php
/* *****

  • File Name: sudoku.php
  • Author: wushuiyong
  • mail: wushuiyong@huamanshu.com
  • ****/

class Sudoku {

const LINES = 9;
const H = 'h';
const V = 'v';

static $X = 'x';

private $_count = 0;

private $_guess = false;
private $_buffer =[];
private $_forecast = [];
private $_rollback = 0;

private $_base = [1, 2, 3, 4, 5, 6, 7, 8, 9];
private $_map = array(
    array(
        self::H =&gt; array(1, 2),
        self::V =&gt; array(3, 6),
    ),
    array(
        self::H =&gt; array(0, 2),
        self::V =&gt; array(4, 7),
    ),
    array(
        self::H =&gt; array(0, 1),
        self::V =&gt; array(5, 8),
    ),

    array(
        self::H =&gt; array(4, 5),
        self::V =&gt; array(0, 6),
    ),
    array(
        self::H =&gt; array(3, 5),
        self::V =&gt; array(1, 7),
    ),
    array(
        self::H =&gt; array(3, 4),
        self::V =&gt; array(2, 8),
    ),

    array(
        self::H =&gt; array(7, 8),
        self::V =&gt; array(0, 3),
    ),
    array(
        self::H =&gt; array(6, 8),
        self::V =&gt; array(1, 4),
    ),
    array(
        self::H =&gt; array(6, 7),
        self::V =&gt; array(2, 5),
    ),
);
private $_table = [];

private $_left = [];

private $_trytable = [];

/**
 * @comment 初始化数独表
 * @param string $table
 */
function __construct($table) {
    $this-&gt;_table = $table;
}

/**
 * @comment 横向检查某数字是否存在, 0 =&gt; start
 */
function setHorizontal($field, $h) {
    foreach ($this-&gt;_trytable[$field] as $k =&gt; &amp;$v) {
        $line = intval($h / 3);
        $k &gt;= $line * 3 &amp;&amp; $k &lt; ($line + 1) * 3 &amp;&amp; $v = self::$X;
    }
}

/**
 * @comment 纵向检查某数字是否存在
 */
function setVerital($field, $c) {
    foreach ($this-&gt;_trytable[$field] as $k =&gt; &amp;$v) {
        $line = $c % 3;
        ($k % 3) == $line &amp;&amp; $v = self::$X;
    }
}

/**
 * @comment 获取横向数字
 */
function getHorizontal($field, $pos) {
    $horizontal = [];
    $horNum = intval($pos / 3) * 3;
    $allField = array_merge($this-&gt;_map[$field][self::H], array($field));
    sort($allField);
    foreach ($allField as $field) {
        for ($i = $horNum; $i &lt; $horNum + 3; $i++) {
            $horizontal[] = $this-&gt;_table[$field][$i];
        }
    }
    return $horizontal;
}

/**
 * @comment 获取纵向数字
 */
function getVerital($field, $pos) {
    $coll  = $pos % 3; //$this-&gt;getVNum($pos, $v);
    $verital = [];
    $allField = array_merge($this-&gt;_map[$field][self::V], array($field));
    sort($allField);
    foreach ($allField as $field) {
        for ($i = $coll; $i &lt; self::LINES - 2; $i += 3) {
            $verital[] = $this-&gt;_table[$field][$i];
        }
    }
    return $verital;
}

function setLeft($field) {
    $this-&gt;_left = $this-&gt;_base;
    for ($i = 0; $i &lt; self::LINES; $i++) {
        unset($this-&gt;_left[$this-&gt;_table[$field][$i]-1]);
    }
}

/**
 * @comment 开始求解
 *
 */
function explain() {
    while (!$this-&gt;isComplete()) {
        $mark = $this-&gt;_count;
        // 直接用数字来筛掉
        $this-&gt;solutionSingleNum();
        // 不行再看行、列、区1-9哪个可填
        //sleep(1); 看演示
        $mark == $this-&gt;_count &amp;&amp; $this-&gt;solutionClean();
        //sleep(1); 看演示
        // 如果这样都不行,那只能猜了
        $mark == $this-&gt;_count &amp;&amp; $this-&gt;solutionGuess();
        //echo "#", PHP_EOL;
    }
}

/**
 * @comment 求解方法1 单个数字扫描
 *
 */
function solutionSingleNum() {
    for ($curr = 0; $curr &lt; self::LINES; $curr++) {
        $this-&gt;_trytable = $this-&gt;_table;
        $this-&gt;setLeft($curr);
        foreach ($this-&gt;_left as $v) {
            $this-&gt;_trytable = $this-&gt;_table;
            foreach ($this-&gt;_map[$curr][self::H] as $field) {
                foreach ($this-&gt;_table[$field] as $k =&gt; $item) {
                    $item == $v &amp;&amp; $this-&gt;setHorizontal($curr, $k);
                }
            }
            foreach ($this-&gt;_map[$curr][self::V] as $field) {
                foreach ($this-&gt;_table[$field] as $k =&gt; $item) {
                    $item == $v &amp;&amp; $this-&gt;setVerital($curr, $k);
                }
            }
            $fill = $this-&gt;isFill($curr);
            if (!$fill) continue;
            foreach ($this-&gt;_trytable[$curr] as $k =&gt; $item) {
                if ($item === 0) {
                    $this-&gt;_table[$curr][$k] = $v;
                    $this-&gt;_count++;
                    break;
                }
            }
        }
    }
}

/**
 * @comment 求解方法2 看行、列、区1-9哪个可填
 *
 */

function solutionClean() {
for ($curr = 0; $curr < self::LINES; $curr++) {
foreach ($this->_table[$curr] as $k => $v) {
if (0 === $v) {
// 单个9宫格内可填数字
$this->_left = array_diff($this->_base, $this->_table[$curr]);
//$h = $this->getHNum($curr, $k);
//echo "h> $h $k", PHP_EOL;
$horizontalArr = $this->getHorizontal($curr, $k);
//print_r($horizontalArr);

                //$c = $this-&gt;getVNum($curr, $k);
                //echo "=== line $v", PHP_EOL;
                $veritalArr = $this-&gt;getVerital($curr, $k);
                $collection = array_merge($horizontalArr, $veritalArr);
                $collection = array_unique($collection);
                $this-&gt;_left = array_diff($this-&gt;_base, $collection);
                if (1 === count($this-&gt;_left)) {
                    //echo "==$curr, $k", PHP_EOL;
                    //print_r($veritalArr); print_r($horizontalArr);
                    $this-&gt;_table[$curr][$k] = array_pop($this-&gt;_left);
                    $this-&gt;_count++;
                    //echo "--clean--", PHP_EOL;
                    //$this-&gt;show();
                    break;
                }
            }
        }
    }
}

/**
 * @comment 求解方法3 不行就只能猜了
 *
 */

function solutionGuess() {
if (!$this->_guess) {
$this->guess();
}
$this->_table = $this->_buffer;
$forecast = current($this->_forecast);
next($this->_forecast);

echo "--guess--n";

    $this-&gt;_table[$forecast[0]][$forecast[1]] = $forecast[2];
}

function guess() {
    $this-&gt;_guess  = true;
    $this-&gt;_buffer = $this-&gt;_table;
    for ($curr = 0; $curr &lt; self::LINES; $curr++) {
        foreach ($this-&gt;_table[$curr] as $k =&gt; $v) {
            if (0 === $v) {
                // 单个9宫格内可填数字
                $this-&gt;_left = array_diff($this-&gt;_base, $this-&gt;_table[$curr]);
                $horizontalArr = $this-&gt;getHorizontal($curr, $k);
                $veritalArr = $this-&gt;getVerital($curr, $k);
                $collection = array_merge($horizontalArr, $veritalArr);
                $collection = array_unique($collection);
                $this-&gt;_left = array_diff($this-&gt;_base, $collection);
                $guessBits = count($this-&gt;_left);
                foreach ($this-&gt;_left as $l) {
                    $this-&gt;_forecast[$guessBits][] = [$curr, $k, $l];
                }
                sort($this-&gt;_forecast);
            }
        }
    }
    $t = []; 
    foreach ($this-&gt;_forecast as $v) {                                                                                                       
        foreach ($v as $i) {
            $t[] = $i; 
        }   
    }   
    $this-&gt;_forecast = $t;
}

function isFill($field) {
    $ret = array_count_values($this-&gt;_trytable[$field]);
    return $ret[0] === 1;
}

function isComplete() {
    for ($i = 0; $i &lt; self::LINES; $i++) {
        if (array_count_values($this-&gt;_table[$i])[0]) {
            return false;
        }
    }
    return true;
}

function show() {
    for ($i = 0; $i &lt; 7; $i+=3) {
        for ($j = $i; $j &lt; $i + 3; $j++) {
            for ($k = 0; $k &lt; 3; $k++) {
                printf("%s ", $this-&gt;_table[$j][$k] ? $this-&gt;_table[$j][$k] : ' ');
            }
        }
        echo PHP_EOL;
        for ($j = $i; $j &lt; $i + 3; $j++) {
            for ($k = 3; $k &lt; 6; $k++) {
                printf("%s ", $this-&gt;_table[$j][$k] ? $this-&gt;_table[$j][$k] : ' ');
            }
        }
        echo PHP_EOL;
        for ($j = $i; $j &lt; $i + 3; $j++) {
            for ($k = 6; $k &lt; 9; $k++) {
                printf("%s ", $this-&gt;_table[$j][$k] ? $this-&gt;_table[$j][$k] : ' ');
            }
        }
        echo PHP_EOL;
    }
    echo PHP_EOL;
}

}

// hard ++
$tableHardHard = array(
array(
0, 9, 0,
8, 0, 0,
1, 0, 0,
),
array(
0, 0, 0,
7, 0, 0,
0, 2, 0,
),
array(
4, 0, 0,
1, 0, 0,
0, 0, 0,
),

array(
    0, 0, 1,
    0, 3, 0,
    0, 0, 6,
),
array(
    0, 0, 0,
    0, 0, 7,
    0, 0, 9,
),
array(
    2, 0, 0,
    0, 9, 0,
    8, 0, 0,
),

array(
    0, 0, 0,
    0, 0, 2,
    0, 0, 4,
),
array(
    0, 6, 0,
    0, 0, 4,
    0, 0, 0,
),
array(
    0, 0, 8,
    0, 0, 5,
    0, 7, 0,
)

);

$sudo = new Sudoku($tableHardHard);
$sudo->show();
$sudo->explain();
$sudo->show();