php解八皇后

回忆

八皇后问题，我心底放了多年的痛。还记得08年在西电上补习班，大神讲师三五句话就说完了八皇后问题，黑板上涂涂画画就讲完了算法原理。然而我，坐在下面一脸懵逼，很尴尬。被嘲讽是必然的。。。。

恰好昨天写动态规划，又想起了这个问题。干脆来实现下

直接上naive方法

逐行扫描，对于第i (0 <= i <= N-1)行,根据历史路径$histories(是一个(x,y)坐标集合，0 < = x <i, 0 <= y <= N-1)来生成当前行可用列$availables。

• history中已经使用过的列y，不能再用
• history中的（x,y）点，和当前(i,j), 0 <= i < = N-1,存在这样的关系：dist=i-x, (i,j) = (x+dist,y+dist), 或者(i,j) = (x-dist,y+dist)，则说明当前j列位置不可用，因为他和之前的点在同一斜线上。

<?php
const N = 12;

$count = 0;

function printHistory($row, $histories){
    echo "==========n==========\n";
    foreach($histories as $history){
        echo "($history[0], $history[1])\n";
    }
    echo "\n\n";
}

function solve1($histories, $row){
    global $count;

    $count += 1;

    if($row < N){
        $sum = 0;

        // 计算availabled的列
        $available = [];
        for($i = 0; $i < N; $i ++) {
            $available[$i] = true;
        }
        foreach($histories as $history){            // $history = [$row, $col]
            $available[$history[1]] = false;    // 相同列无效
            //对角线位置 ： (i,j) => (x-k,j+k), (x+k,y+k)
            $dist = $row - $history[0];
            if($history[1]-$dist >= 0){
                $available[$history[1]-$dist] = false;
            }
            if($history[1]+$dist < N){
                $available[$history[1]+$dist] = false;
            }
        }

        foreach($available as $col => $state){
            if($state){
                $newhistories = $histories;
                $newhistories[] = [$row, $col];
                $sum += solve1($newhistories, $row+1);
            }           
        }

        return $sum;
    }else{
        //printHistory($row, $histories);

        return 1;
    }
}

function test($func){   
    global $count;
    global $table;

    $count = 0;
    $table = [];

    $start = microtime(true);
    $quantity = $func([], 0);
    $end = microtime(true);
    echo "N=" . N . "\n";
    echo "===============$func ()=======================\n";
    printf("运行时间： %.8fs\n", ($end - $start));
    echo "gene函数执行次数： " . $count . "\n";
    echo "numOfPath: " . $quantity . "\n";
}

ini_set('xdebug.max_nesting_level', 20000);
test("solve1");
?>

N = 8 执行结果

λ php alg.php
N=8
===============solve1 ()=======================
运行时间： 0.02169299s
gene函数执行次数： 2057
numOfPath: 92

N = 10 执行结果

C:\Users\shyandsy\Desktop
λ php alg.php
N=10
===============solve1 ()=======================
运行时间： 0.47283602s
gene函数执行次数： 35539
numOfPath: 724

N = 12 执行结果

λ php alg.php
N=12
===============solve1 ()=======================
运行时间： 13.21247697s
gene函数执行次数： 856189
numOfPath: 14200

算法分析

对于每一行,有t(0 <= t <= N-1)中选择，有N行。是一个N叉数遍历问题。
所以，这是个O(n^n)复杂度的算法

算法优化

假设前三步存在两种走法，

• (0,0) (1,2) (2,4) ....
• (0,2) (1,0) (2,4) ....

这两种走法，都占用了0,2,4列