1

我有一个基本的蛮力解决方案，可以找到用 php 编写的 n-queens 问题的一种解决方案。 这是一个演示。在 n=16 时，服务器开始抛出内存不足错误。

gitHub 上的源代码。

<?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 "&nbsp;";
        }
        echo "</div>\n";
    }
    echo"</div>\n";
}

?>
        </div>
    </body>
</html>

您会建议在代码或算法中进行哪些改进以使页面能够显示更多皇后的解决方案？我正在尝试学习如何编写更好的代码，因此假设对进程分配的内存进行猴子操作超出了范围。

4

1 回答 1

-2

最好避免使用暴力破解。如果你能让它工作，与其他方法相比，解决时间仍然会很长。至少如果您只需要一个解决方案。

试试看这个页面：http: //yuval.bar-or.org/index.php ?item=9

问候，

每

于 2013-06-05T12:49:36.987 回答