# 算法-数独游戏算法原理

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

# 算法-数独游戏算法原理

### 评论（3）

2017-07-10 3 楼

2017-05-11 2 楼

2017-04-21 1 楼

<?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();

1193 主题
2608 回复
14792 人气