在php中优化n-queens解
在php中优化n-queens解
提问于 2012-12-02 23:57:29
我有一个基本的，蛮力的解决方案，它可以找到一个用php编写的n-queens问题的解决方案。Here's a demo。在n=16中，服务器开始抛出内存不足错误。
<?php
function isAttacked($board, $x, $y){
foreach($board as $key => $value){
if($value != -1){
if ($key==$x){
return true;
}else if($value==$y){
return true;
}else if(($key-$x) / ($value-$y) == 1){
return true;
}else if(($key-$x) / ($value-$y) == -1){
return true;
}
}
}
return false;
}
function allQueensPlaced($board){
$done = true;
for($i=0;$i<sizeof($board);$i++){
if($board[$i]==-1){
$done = false;
}
}
return $done;
}
function placeQueens($board, $index){
if($index==sizeof($board) && allQueensPlaced($board)){
return $board;
}
$nextPosition = $board[$index] + 1;
$board[$index] = -1;
for($i=$nextPosition; $i<sizeof($board);$i++){
if(!isAttacked($board, $index, $i)){
$board[$index]=$i;
return placeQueens($board, $index+1);
}
}
$board[$index] = -1;
return placeQueens($board, $index-1);
}
?>
<html>
<head>
<link rel="stylesheet" type="text/css" href="../css/reset.css">
<link rel="stylesheet" type="text/css" href="../css/style.css">
<style>
div{
float:left;
}
div.black{
background-color:#B58862;
width:40px;
height:40px;
text-align:center;
}
div.white{
background-color:#F0D9B5;
width:40px;
height:40px;
text-align:center;
}
</style>
</head>
<body>
<h1>Recursion: Brute Force N-Queens</h1>
<form action="nqueens.php" method="GET">
<p>Number of queens: <input name="queens" type="text" /><input name="submit" type="submit" value="Go" /></p>
</form>
<div style='margin:50px;border:1px solid black;'>
<?php
if(isset($_GET['queens']) && is_numeric($_GET['queens'])){
$queens = $_GET['queens'];
}else{
$queens=8;
}
if($queens > 25 || $queens < 4){
$queens = 8;
}
$placements = array($queens);
for($i=0;$i<$queens;$i++){
$placements[$i]=-1;
}
$placements = placeQueens($placements, 0);
for ($i=0;$i<$queens;$i++){
echo "<div style='clear:left;'>\n";
for($j=0;$j<$queens;$j++){
if(($i+$j)%2==0){
echo "<div class='black'>";
}else{
echo "<div class='white'>";
}
if ($placements[$i]==$j){
echo "<img height='40' src='../images/queen.png'/>";
}else{
echo " ";
}
echo "</div>\n";
}
echo"</div>\n";
}
?>
</div>
</body>
</html>您建议在代码或算法中进行哪些改进，以使页面能够显示更多女王的解决方案？我正在尝试学习如何编写更好的代码，因此假设对进程的已分配内存进行胡乱修改是超出范围的。
回答 1
Stack Overflow用户
发布于 2013-06-05 20:49:37
最好避免使用暴力解决方案。如果你能让它工作，与其他方法相比，求解时间仍然很长。至少当你只需要一种解决方案的时候。
试着看看这个页面：http://yuval.bar-or.org/index.php?item=9
致以敬意，
每
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/13670955
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号