欧美一区二区三区,国内熟女精品熟女A片视频小说,日本av网,小鲜肉男男GAY做受XXX网站

n皇后 php

傅智翔1年前7瀏覽0評論
n皇后問題是一道經典的算法問題,目的是找到n個皇后在n×n的棋盤上互不攻擊的所有放置方式。其中n=8是最為常見的情況,在以下所有示例中n皆為8。 在PHP語言中,我們可以通過回溯算法來解決n皇后問題。回溯算法是一種常見的深度優先搜索算法,在搜索過程中記錄當前狀態,并通過遞歸回溯撤銷之前的狀態,來尋找所有可行的解。 下面是一段使用PHP語言實現n皇后問題的代碼,其中用一個一維數組$queens來記錄每一行中皇后所在的列數。
function nQueens($n) {
$queens = array_fill(0, $n, -1);
$result = array();
solveNQueensHelper($queens, 0, $result);
return $result;
}
function solveNQueensHelper(&$queens, $row, &$result) {
$len = count($queens);
if ($row >= $len) {
array_push($result, $queens);
return;
}
for ($col = 0; $col< $len; $col++) {
if (isValid($queens, $row, $col)) {
$queens[$row] = $col;
solveNQueensHelper($queens, $row + 1, $result);
$queens[$row] = -1; // backtracking
}
}
}
function isValid($queens, $row, $col) {
for ($i = 0; $i< $row; $i++) {
if ($queens[$i] == $col || abs($queens[$i] - $col) == abs($i - $row)) {
return false;
}
}
return true;
}
在以上代碼中,isValid()函數用來判斷皇后的位置是否合理,每次在回溯時將皇后所在的位置重置為-1,solveNQueensHelper()函數用來遞歸進行n皇后問題的搜索,當搜索到一種可行的情況時,將結果存儲到$result數組中。最后將結果數組返回即可。 我們可以通過以下代碼來輸出n皇后問題的所有可行解。
$n = 8;
$solutions = nQueens($n);
foreach ($solutions as $solution) {
for ($row = 0; $row< $n; $row++) {
for ($col = 0; $col< $n; $col++) {
if ($solution[$row] == $col) {
echo "Q";
} else {
echo ".";
}
}
echo "\n";
}
echo "\n";
}
以上代碼中,我們遍歷了$solutions數組中所有的解,輸出了每一種解在棋盤上的擺法。其中Q表示皇后的位置,.表示空位置。 n皇后問題是一個經典的算法問題,使用PHP語言實現可以通過回溯算法進行求解。以上代碼就可以很好地解決n皇后問題,并輸出所有的可行解。