用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; 
    }
}

测试:

";
                else echo " ";
            }
            echo "";
        }    
        echo "

$queen = new Queen(8);
$re = $queen->getResult();
//输出
$k=0;
foreach($re as $v) {
    echo "输出第".++$k."个结果:
";
    echo "";
        foreach($v as $row){
            echo "";
            for($i=1;$i<=count($v);$i++) {
                if($row == $i) echo "Q

";
}

当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

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