Skip to content

Instantly share code, notes, and snippets.

@vayn
Created November 3, 2010 07:41
Show Gist options
  • Save vayn/660858 to your computer and use it in GitHub Desktop.
Save vayn/660858 to your computer and use it in GitHub Desktop.
八皇后 Eight Queens 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 />";
}
?>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment