八皇后
29 Oct 2012八皇后问题：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Eight Queens Puzzle(Recursive algorithm) - 八皇后问题（递归算法）</title>
<style type="text/css">
body {
background-color: #c1c1c1;
}
p {
text-align: center;
}
table {
border-width: 5px;
border-color: #bb3355;
border-style: solid;
background-color: #ffffff;
}
td {
text-align: center;
vertical-align: middle;
width: 70px;
height: 70px;
}
td.b {
background-color: #000000;
}
</style>
<script type="text/javascript">
var Q = new Array(8); //八皇后所在的列位置
// 判断第n个皇后与前面的n-1个皇后是否冲突
function Clash(n) {
var flag = false; //冲突标志
var i = 0; //从第0行逐行判断
while ((i < n) && !flag) {
flag = (Q[n] == Q[i]) || (Math.abs(Q[n] - Q[i]) == (n - i)); //在同一列或相同的对角线即为冲突
i++;
}
return flag;
}
//搜索第n个皇后的位置
function QSeek(n) {
//判断是否已经回溯到了第一个皇后之前，即已经找到了所有解
if (n >= 0) {
Q[n]++; //将该位置的皇后右移一个位置
if (Q[n] < 8) //当前行的皇后右移未超出范围
{
if (Clash(n)) //冲突则继续搜索当前行的皇后位置
return QSeek(n)
else //不冲突则当前行搜索完成
return true;
}
else //当前行无法安放，递归回溯
{
Q[n] = -1; //删除当前行的皇后
if (QSeek(n - 1)) //递归回溯
return QSeek(n) //在前一行搜索成功时，再搜索当前行
else
return false; //无解
}
}
else
return false; //无解
}
//刷新皇后图片
function showQueens() {
//清除原有图像，即清除所有TD标记中的内容
var tds = document.getElementsByTagName("TD");
for (var i = 0; i < tds.length; i++)
tds[i].innerHTML = "";
//绘制新图像
for (var i = 0; i < 8; i++) {
eval("r" + i + "c" + Q[i] + ".innerHTML = \"<img src=\\\"queen.jpg\\\" />\";");
}
}
var count = 1; //记录解的个数
function Queens() {
if (count == 1) { //求第一组解时需搜索前7个皇后的位置
for (var i = 0; i < 7; i++)
QSeek(i);
}
if (QSeek(7)) {
showQueens();
seekbtn.value = "已经搜索到第" + count + "组解，准备搜索第" + ++count + "组解...";
seekbtn.focus(); //设置焦点到按钮
}
else
seekbtn.value = "全部解已经搜索完成，共" + (count - 1) + "组！";
}
</script>
</head>
<body>
<p>
Eight Queens Puzzle (Recursive algorithm) - 八皇后问题（递归算法）<br />
</p>
<center>
<table cellpadding="0" cellspacing="0">
<tr>
<td id="r0c0"></td>
<td class="b" id="r0c1"></td>
<td id="r0c2"></td>
<td class="b" id="r0c3"></td>
<td id="r0c4"></td>
<td class="b" id="r0c5"></td>
<td id="r0c6"></td>
<td class="b" id="r0c7"></td>
</tr>
<tr>
<td class="b" id="r1c0"></td>
<td id="r1c1"></td>
<td class="b" id="r1c2"></td>
<td id="r1c3"></td>
<td class="b" id="r1c4"></td>
<td id="r1c5"></td>
<td class="b" id="r1c6"></td>
<td id="r1c7"></td>
</tr>
<tr>
<td id="r2c0"></td>
<td class="b" id="r2c1"></td>
<td id="r2c2"></td>
<td class="b" id="r2c3"></td>
<td id="r2c4"></td>
<td class="b" id="r2c5"></td>
<td id="r2c6"></td>
<td class="b" id="r2c7"></td>
</tr>
<tr>
<td class="b" id="r3c0"></td>
<td id="r3c1"></td>
<td class="b" id="r3c2"></td>
<td id="r3c3"></td>
<td class="b" id="r3c4"></td>
<td id="r3c5"></td>
<td class="b" id="r3c6"></td>
<td id="r3c7"></td>
</tr>
<tr>
<td id="r4c0"></td>
<td class="b" id="r4c1"></td>
<td id="r4c2"></td>
<td class="b" id="r4c3"></td>
<td id="r4c4"></td>
<td class="b" id="r4c5"></td>
<td id="r4c6"></td>
<td class="b" id="r4c7"></td>
</tr>
<tr>
<td class="b" id="r5c0"></td>
<td id="r5c1"></td>
<td class="b" id="r5c2"></td>
<td id="r5c3"></td>
<td class="b" id="r5c4"></td>
<td id="r5c5"></td>
<td class="b" id="r5c6"></td>
<td id="r5c7"></td>
</tr>
<tr>
<td id="r6c0"></td>
<td class="b" id="r6c1"></td>
<td id="r6c2"></td>
<td class="b" id="r6c3"></td>
<td id="r6c4"></td>
<td class="b" id="r6c5"></td>
<td id="r6c6"></td>
<td class="b" id="r6c7"></td>
</tr>
<tr>
<td class="b" id="r7c0"></td>
<td id="r7c1"></td>
<td class="b" id="r7c2"></td>
<td id="r7c3"></td>
<td class="b" id="r7c4"></td>
<td id="r7c5"></td>
<td class="b" id="r7c6"></td>
<td id="r7c7"></td>
</tr>
</table>
<br/>
<input style="width: 300px; height: 25px" type="button" id="seekbtn" value="准备搜索第1组解..." onclick="Queens()" />
</center>
</body>
</html>