新浪博客

数独高级技巧-单链,Y-wing(续)

2007-08-18 23:02阅读：1,379

http://blog.sina.cn/dpool/blog/u/1153126670

数独高级技巧-单链,Y-wing(续)X
Y-wing就比较简单一点,如果存在三个格辅数分别为:D1(AB),D2(AC),D3(BC),且D1与D2在同一规则上,D1与D3在同一规则上,D2与D3不在同一规则上,则与D2和D3在同一规则上的D4中的辅数C可删减掉

图中绿色组成Y-wing,Y-wing删减后可删减掉紫色单元中的5,以后就能用单链来解了
对数字5,(4,3)(4,7)(9,7)(9,2)组成单链(链长为单数3)
程序如下:
<?
/* AB --- BC
* AC C
*
*/
/* 找所有对 */
function getdouble($arrdu)
{
$ret = array();
foreach($arrdu as $i => $v)
{
if(strlen($v)==3)
{
$ret[$v{1}][] = $i;
$ret[$v{2}][] = $i;
}
}
//print_r($ret);
return $ret;
}
function y_wing(&$arrdu)
{
//outit2($
arrdu);
GLOBAL $rule,$initstr,$r_row,$r_col,$r_box;
$max = true;
$ret = 0;

while($max)
{
$max = false;
$narr = str_split(substr($initstr,1)); //1,2,3,4,...
$alldouble = getdouble($arrdu);

foreach($narr as $num)
{
//echo 'NUM $num';
for($i=0; $i<count($alldouble[$num]);$i++)
for($j=$i+1;$j<count($alldouble[$num]);$j++)
foreach($alldouble[$num] as $i)
foreach($alldouble[$num] as $j)
if( $j > $i
&& $r_row[$i] != $r_row[$j] //找两个不同的单元格,都包含C(num)
&& $r_col[$i] != $r_col[$j] //且要求这两个格不在同一行/列/盒
&& $r_box[$i] != $r_box[$j] //为AC,BC样式
&& $arrdu[$i] != $arrdu[$j]
)
{
//再找是否存在一个关键点 AB
$first = true;
$a = str_replace('$num','',substr($arrdu[$i],1));
$b = str_replace('$num','',substr($arrdu[$j],1));
//echo '$i $j $a $b';
$q = array_intersect( $alldouble[$a],$alldouble[$b] );
if(count($q)>0)
foreach($q as $r)
if(( $r_row[$i] == $r_row[$r] || $r_col[$i] == $r_col[$r] || $r_box[$i] == $r_box[$r])
&& ( $r_row[$j] == $r_row[$r] || $r_col[$j] == $r_col[$r] || $r_box[$j] == $r_box[$r])
)
{
//找到了
//echo 'Fund';
//outit2($arrdu);
foreach($arrdu as $m => $n)
if( $n{0} === '0'
&& strpos($n,'$num') !== false
&& $m != $i && $m != $j && $m != $r
&& ( $r_row[$i] == $r_row[$m] || $r_col[$i] == $r_col[$m] || $r_box[$i] == $r_box[$m])
&& ( $r_row[$j] == $r_row[$m] || $r_col[$j] == $r_col[$m] || $r_box[$j] == $r_box[$m])
)
{
$new = str_replace('$num','',$n);
$arrdu[$m] = $new;
if($GLOBALS['debug'])
{
if($first)
{
echo 'Y-wing(A$a,B$b,C$num):AB:'.bit2place($r).' AC:'.bit2place($j)
.' BC:'.bit2place($i).'';
$first = false;
}
echo ' ...'.bit2place($m).' $n -> $new ';
}
$max = true;
$ret = 1;
if(onlyone($arrdu)==-1)return -1;
}
}
}
}
}
return $ret;
}
?>

运行结果:
D:\mywebhtdocs\do\game\dushu\ok>php do.php 3008027150079018030815379060000030090
03196408900700001000378602806000107702619084
Intersection 4 in Row7 remove from Box7
...(8,2)03459 -> 0359
Intersection 2 in Col7 remove from Box6
...(4,8)02567 -> 0567
...(5,8)0257 -> 057
...(6,8)02356 -> 0356
Intersection 4 in Box2 remove from Col5
...(4,5)02458 -> 0258
...(6,5)02458 -> 0258
...(8,5)0245 -> 025
Intersection 5 in Box8 remove from Row8
...(8,2)0359 -> 039
...(8,8)0359 -> 039
Intersection 2 in Row5 remove from Box4
...(4,1)012456 -> 01456
...(4,2)0124567 -> 014567
...(6,2)02456 -> 0456
Quads ... 3(2,3,4,6)2 4 5 8 (4,3) (4,4) (4,5) (4,7)
... (4,1)01456->016
... (4,2)014567->0167
... (4,8)0567->067
Y-wing(A2,B4,C5):AB:(4,4) AC:(6,6) BC:(4,7)
...(4,5) 0258 -> 028
Y-wing(A2,B4,C5):AB:(4,4) AC:(6,6) BC:(4,7)
...(6,7) 0235 -> 023
Y-wing(A2,B4,C5):AB:(4,4) AC:(6,6) BC:(4,7)
...(6,8) 0356 -> 036
Intersection 5 in Box5 remove from Row6
...(6,2)0456 -> 046
...(6,3)0458 -> 048
5 Chains:(4,3)---(4,7) (4,7)---(9,7) (9,7)---(9,2)
...(5,2) 0257 -> 027
5 Chains:(4,3)---(4,7) (4,7)---(9,7) (9,7)---(7,8)
...(7,3) 0459 -> 049
In rule11 only(4,3)have a 5
In (4,7) only 2 Candidates
In (5,1) only 2 Candidates
In (5,2) only 7 Candidates
In (5,8) only 5 Candidates
In (6,7) only 3 Candidates
In (6,8) only 6 Candidates
In (7,8) only 9 Candidates
In (8,8) only 3 Candidates
In (9,7) only 5 Candidates
In rule2 only(3,8)have a 2
In (2,8) only 4 Candidates
In (3,1) only 4 Candidates
In (4,4) only 4 Candidates
In (4,5) only 8 Candidates
In (4,8) only 7 Candidates
In (6,2) only 4 Candidates
In (6,3) only 8 Candidates
In (6,6) only 5 Candidates
In (7,3) only 4 Candidates
In (8,2) only 9 Candidates
In (8,4) only 2 Candidates
In (8,5) only 5 Candidates
In (8,6) only 4 Candidates
In (9,2) only 3 Candidates
In rule0 only(1,3)have a 9
In rule0 only(1,5)have a 4
In (1,2) only 6 Candidates
In (2,1) only 5 Candidates
In (2,2) only 2 Candidates
In (2,5) only 6 Candidates
In (4,2) only 1 Candidates
In (6,5) only 2 Candidates
In (7,1) only 1 Candidates
In (7,2) only 5 Candidates
In rule3 only(4,1)have a 6
===========
3 6 9 8 4 2 7 1 5
5 2 7 9 6 1 8 4 3
4 8 1 5 3 7 9 2 6
6 1 5 4 8 3 2 7 9
2 7 3 1 9 6 4 5 8
9 4 8 7 2 5 3 6 1
1 5 4 3 7 8 6 9 2
8 9 6 2 5 4 1 3 7
7 3 2 6 1 9 5 8 4
===========

留言板

下载客户端体验更佳，还能发布图片和表情~

亿万博主正在被热评！
999+

给此博文留言吧！ 有机会上热评榜！ 攒金币兑换礼品！

好的评论会让人崇拜发布评论

关注

我的更多文章

下载客户端阅读体验更佳

APP专享