用php解八皇后问题

八皇后问题是一个非常有趣的问题，是由德国大数学家高斯首先提出来的。要求在国际象棋的棋盘上放置八个皇后，使她们不能互相攻击，即任何两个皇后不能处在同一行、同一列、同一条斜线上。问有多少种不同的摆法？并找出所有的摆法。
问题分析：
(1)   满足上述条件的八个皇后，必然是每行一个，每列一个。
(2)   棋盘上任意一行、任意一列、任意一条斜线上都不能有两个皇后。
php代码:
class Queen{
    var $chess; //皇后位置
    var $queens; //皇后数
    var $result = array();//正解
    function Queen($queens){
        $this -> queens = $queens; //棋盘大小 $queens x $queens
        $this -> place(); //开始放置第0个皇后
    }
    //在第$n行放置皇后
    function place($n=0){
        if($n == $this -> queens){ //得到一个解
            for($i = 0 ; $i $this -> queens ; $i++) $re[] = $this -> chess[$i]; //保存皇后位置
            $this -> result[] = $re;
            return;
        }
        for($i = 1 ; $i $this -> queens ; $i++){
            $this -> chess[$n] = $i;
            if($this -> isOK($n)) $this -> place($n + 1);
        }
    }
    //判断位置是否有效
    function isOK($n){
        for($i = 0 ; $i $n ; $i++){
            if($this -> chess[$i] == $this -> chess[$n] || abs($this -> chess[$i] - $this -> chess[$n]) == ($n - $i)) return 0;
        }
        return 1;
    }
    function getResult(){
        return $this -> result;
    }
}
测试:
$queen = new Queen(8);
$re = $queen->getResult();
//输出
$k=0;
foreach($re as $v) {
    echo "输出第".++$k."个结果:
";
    echo "";
        foreach($v as $row){
            echo "";
            for($i=1;$icount($v);$i++) {
                if($row == $i) echo "Q";
                else echo " ";
            }
            echo "";
        }   
        echo "
";
}
当n=8时,共有92种解法,其中部分结果如下:
输出第1个结果:
Q











Q










Q





Q




Q











Q


Q









Q




输出第2个结果:
Q












Q









Q


Q











Q




Q





Q










Q



输出第3个结果:
Q













Q




Q









Q









Q

Q










Q





Q





各位朋友有兴趣也可以将皇后改成骑士(马),马的控制范围为直走两格,横走一格,即"日"字形..