php计算八皇后问题

今天去表弟家玩，他提到了八皇后摆放问题，我说直接用8个for循环镶套就可以解决，经过一番构思和测试，终于实现了输出八皇后位置。

因为每一行只能摆放一个皇后，所以我只求每个皇后的纵坐标。

经过多番修改成功生成92种结果，最终代码分享如下，留下纪念下。

<?php
for($a=1;$a<9;$a++){
    $tmp[1]=$a;
for($b=1;$b<9;$b++){
        $tmp[2]=$b;
        if($b==$a){continue;}
    if(
        abs($b-$a)==1
    ){continue;}
for($c=1;$c<9;$c++){
    $tmp[3]=$c;
    if (in_array($c, array($a, $b))){
        continue;
    }
    if(
        abs($c-$b)==1||abs($c-$a)==2
    ){
        continue;
    }
for($d=1;$d<9;$d++){
        $tmp[4]=$d;
    if (in_array($d, array($a,$b,$c))){
        continue;
    }
    if (
    abs($d-$b)==2
    ||abs($d-$a)==3   
        ||abs($d-$c)==1
    ){
        continue;
    } 
for($e=1;$e<9;$e++){
        $tmp[5]=$e;
    if (in_array($e, array($a,$b,$c,$d))){
        continue;
    }
    if (
    abs($e-$b)==3
    ||abs($e-$a)==4
        ||abs($e-$c)==2
        ||abs($e-$d)==1
    ){
        continue;
    }
for($f=1;$f<9;$f++){
        $tmp[6]=$f;
    if (in_array($f, array($a,$b,$c,$d,$e))){
        continue;
    }
    if (
      abs($f-$b)==4
    ||abs($f-$a)==5
        ||abs($f-$c)==3
        ||abs($f-$d)==2
        ||abs($f-$e)==1
    
    ){
        continue;
    }
for($g=1;$g<9;$g++){
        $tmp[7]=$g;
    if (in_array($g, array($a,$b,$c,$d,$e,$f))){
        continue;
    }
    if (
abs($g-$b)==5
    ||abs($g-$a)==6
        ||abs($g-$c)==4
        ||abs($g-$d)==3
        ||abs($g-$e)==2
        ||abs($g-$f)==1
    ){
        continue;
    }      
for($h=1;$h<9;$h++){
        $tmp[8]=$h;
    if (in_array($h, array($a, $b,$c,$d,$e,$f,$g))){
        continue;
    }
    if (
      abs($h-$b)==6
    ||abs($h-$a)==7
        ||abs($h-$c)==5
        ||abs($h-$d)==4
        ||abs($h-$e)==3
        ||abs($h-$f)==2
        ||abs($h-$g)==1
    ){
        continue;
    }
        $xx[]=$tmp;
    }
    }
    }
}
}
}
}
}
print_r($xx);

上面的是简单版本，按照需求直接写的代码。

不过上面的代码，里面有很多类似的重复逻辑。最重优化后的版本如下，使用了递归的方式，不在一个一个的写for循环。

<?php
$arr = [];
bhh(1, [], [], $arr);
print_r($arr);
function bhh($length, $load, $jieguo, &$arr) {
    if ($length > 8) {
        $arr[] = $jieguo;
        return;
    }
    for ($num = 1; $num <= 8; $num++) {
        if (!in_array($num, $load) && isValid($num, $length, $jieguo)) {
            $load[] = $num;
            $jieguo[$length] = $num;
            bhh($length + 1, $load, $jieguo, $arr);
            array_pop($load);
        }
    }
}
function isValid($num, $length, $jieguo) {
    foreach ($jieguo as $index => $value) {
        $indexDiff = $length - $index;
        $valueDiff = abs($num - $value);
        if ($valueDiff === $indexDiff) {
            return false;
        }
    }
    return true;
}

这种方式的好处，比如如果求9皇后的问题呢，只要修改一下$length>9就可以了。代码更短更容易维护。