刚入职，有点闲，记得大学有听说过什么八皇后，没有实现过，心血来潮，打算自己写一个,写了整整一天回想起大学，哎，没好好学习，原来大学的课程还是有用的，学了总比没学好，当时觉得没用的知识，不一定以后也不着，并且很有可能用得着在这里奉劝一下在校大学生，把大学的专业课程好好学好，对你绝对有用的，理解下课本上的思想也行（比如说编译原理，图形学，计算机体系结构，操作系统等，这些大部分人真的可能不会参加这方面的工作，但里面的各种思想是解决各种问题的精华中的精华，不限于在程序上），还有英语及交际口才能力，也非常非常非常重要，与你职业上能达到什么高度样紧密相关。
再发下牢骚，本人从小的理想就是当天文方面的物理科学家去探索浩瀚宇宙（留给我儿子去实现吧），无奈智力有限，英语太烂等，只能上个普通本科，做只普通程序猿，毕业后进个深圳一家普通公司，做网站的，学校学的是JAVA，工作就转向了PHP，工作了3年，期间与网站有关的都做(前台样式脚本、后台PHP、服务器LINUX等)，今年运气好跳到了一家很大的公司，希望自己以后会越来越好~
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8"/>
</head>
<body>
<?php
$num = 8; //几皇后？
echo showQueens(queen($num),$num);
/**
回溯主体函数，返回所有可能的方案数组
*/
function queen($num){
$queen=array(); //临时的一种方案
$queens=array();//全部方案
for($i=0;$i<$num;$i++){//从00位置开始放置皇后
for($j=0;$j<$num;$j++){
if(is_conflict($queen,$i,$j,$num)){ //有冲突则取下一个
if($j+1===$num){ //列到了再后一个都有冲突则回退
backRow($queen,$i,$j,$num);
countinue;
}
}else{ //没有冲突则前进
$queen[$i][$j]=1; //记录可行值
if($i===$num-1){ //前面到了最后一行，达成一种方案，记录。。
$queens[]=$queen;
unset($queen[$i]);
backRow($queen,$i,$j,$num);//回退
}else{
break;
}
}
}
}
return $queens;
}
function backRow(&$queen,&$i,&$j,$num){
$i=$i-1;
$j=getNextJ($queen[$i]);//求回退位置的J的下标
unset($queen[$i]);
if($j+1===$num){ //回退的行已经是最后一列了，接着回退
$i=$i-1;
if($i===-1){ //回退到了第一行，遍历结束
$i=$num;return;
}
$j=getNextJ($queen[$i]);
unset($queen[$i]);
}
}
function getNextJ($queen){
foreach($queen as $k=>$v){
return $k;
}
return false;
} /**
显示打印结果
*/
function showQueens($queens,$num){
$html ='<div>'.$num.'皇后共'.count($queens).'种方案</div>';
foreach($queens as $queen){
$html .=showQueen($queen,$num);
}
return $html;
}
//图形显示
function showQueen($queen,$num){
$html ='<table style="text-align:center;">
<tr>';
for($i=-1;$i<$num;$i++){
$html .='<td width="52" height="52">'.$i.'</td>';
}
$html .='</tr>';
foreach($queen as $row=>$q){
$html .='<tr><td height="52">'.($row).'</td>';
for($i=0;$i<$num;$i++){
$html .='<td style="background-color:#00cc99;">'.$q[$i].'</td>';
}
$html .='</tr>';
}
$html .='</table>';
return $html;
} /**
检查要前进i,j的位置上面有没有冲突
*/
function is_conflict($queen,$i,$j,$num){
$flag=check_conflict_col($queen,$i,$j); //竖列有没有冲突
if($flag)return $flag; $flag=check_conflict_corner_left($queen,$i,$j); //左上对角有没有冲突
if($flag)return $flag; $flag=check_conflict_corner_right($queen,$i,$j,$num); //右上对角有没有冲突
return $flag;
}
//竖列有冲突？
function check_conflict_col($queen,$i,$j){
for($row=0;$row<$i;$row++){
if($queen[$row][$j]===1){
return true;
}
}
return false;
}
//左上斜线有冲突？
function check_conflict_corner_left($queen,$i,$j){
$step=1;
while($i-$step>=0 && $j-$step>=0){
if($queen[$i-$step][$j-$step]===1){
return true;
}
$step++;
}
return false;
}
//右上斜线有冲突？
function check_conflict_corner_right($queen,$i,$j,$num){
$step=1;
while(($i-$step)>=0 && ($j+$step<$num)){
if($queen[$i-$step][$j+$step]===1){
return true;
}
$step++;
}
return false;
}
?>
</body>
再发下牢骚，本人从小的理想就是当天文方面的物理科学家去探索浩瀚宇宙（留给我儿子去实现吧），无奈智力有限，英语太烂等，只能上个普通本科，做只普通程序猿，毕业后进个深圳一家普通公司，做网站的，学校学的是JAVA，工作就转向了PHP，工作了3年，期间与网站有关的都做(前台样式脚本、后台PHP、服务器LINUX等)，今年运气好跳到了一家很大的公司，希望自己以后会越来越好~
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8"/>
</head>
<body>
<?php
$num = 8; //几皇后？
echo showQueens(queen($num),$num);
/**
回溯主体函数，返回所有可能的方案数组
*/
function queen($num){
$queen=array(); //临时的一种方案
$queens=array();//全部方案
for($i=0;$i<$num;$i++){//从00位置开始放置皇后
for($j=0;$j<$num;$j++){
if(is_conflict($queen,$i,$j,$num)){ //有冲突则取下一个
if($j+1===$num){ //列到了再后一个都有冲突则回退
backRow($queen,$i,$j,$num);
countinue;
}
}else{ //没有冲突则前进
$queen[$i][$j]=1; //记录可行值
if($i===$num-1){ //前面到了最后一行，达成一种方案，记录。。
$queens[]=$queen;
unset($queen[$i]);
backRow($queen,$i,$j,$num);//回退
}else{
break;
}
}
}
}
return $queens;
}
function backRow(&$queen,&$i,&$j,$num){
$i=$i-1;
$j=getNextJ($queen[$i]);//求回退位置的J的下标
unset($queen[$i]);
if($j+1===$num){ //回退的行已经是最后一列了，接着回退
$i=$i-1;
if($i===-1){ //回退到了第一行，遍历结束
$i=$num;return;
}
$j=getNextJ($queen[$i]);
unset($queen[$i]);
}
}
function getNextJ($queen){
foreach($queen as $k=>$v){
return $k;
}
return false;
} /**
显示打印结果
*/
function showQueens($queens,$num){
$html ='<div>'.$num.'皇后共'.count($queens).'种方案</div>';
foreach($queens as $queen){
$html .=showQueen($queen,$num);
}
return $html;
}
//图形显示
function showQueen($queen,$num){
$html ='<table style="text-align:center;">
<tr>';
for($i=-1;$i<$num;$i++){
$html .='<td width="52" height="52">'.$i.'</td>';
}
$html .='</tr>';
foreach($queen as $row=>$q){
$html .='<tr><td height="52">'.($row).'</td>';
for($i=0;$i<$num;$i++){
$html .='<td style="background-color:#00cc99;">'.$q[$i].'</td>';
}
$html .='</tr>';
}
$html .='</table>';
return $html;
} /**
检查要前进i,j的位置上面有没有冲突
*/
function is_conflict($queen,$i,$j,$num){
$flag=check_conflict_col($queen,$i,$j); //竖列有没有冲突
if($flag)return $flag; $flag=check_conflict_corner_left($queen,$i,$j); //左上对角有没有冲突
if($flag)return $flag; $flag=check_conflict_corner_right($queen,$i,$j,$num); //右上对角有没有冲突
return $flag;
}
//竖列有冲突？
function check_conflict_col($queen,$i,$j){
for($row=0;$row<$i;$row++){
if($queen[$row][$j]===1){
return true;
}
}
return false;
}
//左上斜线有冲突？
function check_conflict_corner_left($queen,$i,$j){
$step=1;
while($i-$step>=0 && $j-$step>=0){
if($queen[$i-$step][$j-$step]===1){
return true;
}
$step++;
}
return false;
}
//右上斜线有冲突？
function check_conflict_corner_right($queen,$i,$j,$num){
$step=1;
while(($i-$step)>=0 && ($j+$step<$num)){
if($queen[$i-$step][$j+$step]===1){
return true;
}
$step++;
}
return false;
}
?>
</body>
部分思路大致这样，代码不写了，我这台机器没有64bit，要放到服务器上测试很麻烦
另外，虽然是二进制位运算，但棋盘是8*8，用八进制去思考会明瞭些