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皇后問題,并輸出所有的可行解。
上一篇nuxt連接php
下一篇ajax 排序功能的實現