八皇后 Eight Queens PHP

eightqueen.php

<?php
/*
 * 八皇后问题是一个非常有趣的问题，是由德国大数学家高斯首先提出来的。
 * 要求在国际象棋的棋盘上放置八个皇后，使她们不能互相攻击。
 * 即任何两个皇后不能处在同一行、同一列、同一条斜线上。
 *
 * 问有多少种不同的摆法？并找出所有的摆法。
 *
 * 问题分析：
 * (1) 满足上述条件的八个皇后，必然是每行一个，每列一个。
 * (2) 棋盘上任意一行、任意一列、任意一条斜线上都不能有两个皇后。
 *
 */

class Queen {
    var $chess; // 保存各列皇后放置的行数，下标表示列号(0-7)，chess[i]保存放置行号(1-8)
    var $queens; // 皇后数量
    var $result = array(); // 正解

    function __construct($queens) {
        $this->queens = $queens; // 棋盘大小 $queens x $queens
        $this->place(); // 开始放置第0个皇后
    }

    // i表示行号,第n列皇后将放置的行号
    function place($n = 0) {
        if ($n == $this->queens) { // n==queens时，表示前面的8列(列号为0-7)都已经放好，把一组解输出
            for ($i = 0; $i < $this->queens; $i++) {
                $re[] = $this->chess[$i]; // 保存皇后位置
            }
            $this->result[] = $re;
        }

        // 先在第一列放置皇后，记录放置的行号（行号从小到大挨个试，下同），再放
        // 置第二列（前提不与前面的皇后冲突），同样也记录行号，然后放置第三、第
        // 四列（前提也是不与前面的皇后冲突），这里注意一下，正在尝试第N列皇后的
        // 放置时说明前（N-1）列皇后放置是不冲突的。当发现某列无法放置皇后时，就
        // 返回前一列，行号加一（就跟上面二叉树例子一样，返回一步后，向右一个试
        // 探，这里按行号从小到大试探），继续试探。如果放置好了第八列的皇后就得
        // 到了一种放置的方法。接着行号加一或者返回前一列，继续试探，直到把所有
        // 的情况都试完。
        for ($i = 1; $i <= $this->queens; $i++) {
            $this->chess[$n] = $i; // 这条语句保证了每一列皇后的放置都会从第1行试探到第N行

            // 如果放置第n列成功，则继续尝试第n+1列
            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 False;
                // chess[i]==chess[n]表示放置的行号相同，冲突
                // 因为是逐列操作，不存在放置的列号相同
                // chess[i]-chess[n]==n-i,斜率为1，表示在斜率为1的对角线上
                // chess[i]-chess[n]==i-n,斜率为-1，表示在斜率为-1的对角线上
            }
        }
        return True;
    }

    function getResult() {
        return $this->result;
    }
}

$queen = new Queen(8);
$re = $queen->getResult();
// output
$k = 0;
foreach ($re as $v) {
    echo '输出第' . ++$k . '个结果:<br />';
    echo '<table border="0" cellpadding="0" cellspacing="1" bgcolor="#000000" style="padding:5px;">';
    foreach ($v as $row) {
        echo '<tr align="center">';
        for ($i = 1; $i <= count($v); $i++) {
            if ($row == $i) {
                echo '<td bgcolor="#ffffff" width="20" style="color:#ff0000;font-weight:bold;">Q</td>';
            }
            else {
                echo '<td bgcolor="#ffffff" width="20">&nbsp;</td>';
            }
        }
        echo "</tr>";
    }
    echo "</table><br />";
}
?>