排列树的回溯搜索解决n皇后问题

2744557306

这是一个MATLAB实现的N皇后问题，这是一个经典的组合问题。其目标是在一个N×N的棋盘上放置N个皇后，使得它们之间互不攻击。提供的代码使用了递归回溯的方法来找到N皇后问题的所有解决方案。
让我们逐步解释这段代码：
function [chess, main, deputy, number] = justtry(i, n, chess, main, deputy, number)
# X+ {# k3 c  n/ F2 H
* A8 W- u, w! t3 U' `& N+ ]这定义了一个名为justtry的函数，它接受六个参数：当前行数i，棋盘大小n，当前皇后的排列chess，主对角线和副对角线的状态（main和deputy），以及解的数量number。
# v+ R  f) w5 Y( ?: Y0 Gif i == 9
    number = number + 1;
' B4 {, @$ g7 P4 e    chess
else
    for k = i:8
        if main(i - chess(k) + n) == 0 && deputy(i + chess(k) - 1) == 0

这检查是否已经到达第9行。如果是这样，它会递增解的数量(number)并显示当前皇后在棋盘上的排列。否则，它进入一个从当前行(i)到8的循环。
6 x7 p  D) l8 H, ^* l( C& I! A嵌套的if语句检查当前棋盘位置是否有效（即没有皇后互相威胁）。如果条件满足，它将继续放置皇后。
            t = chess(k); % 交换位置
            chess(k) = chess(i);
            chess(i) = t;

9 z7 t' D9 S% S( B- _* Q* S            main(i - chess(k) + n) = 1;
8 y* _9 ~7 i' p1 V            deputy(i + chess(k) - 1) = 1;

            [chess, main, deputy, number] = justtry(i + 1, n, chess, main, deputy, number); % 递归调用

! Z& [' b0 ^5 q, U            t = chess(k); % 回溯
) _: {" b5 A7 x* b  ~            chess(k) = chess(i);
            chess(i) = t;

$ x  q% U: Q3 K6 ?: i            main(i - chess(k) + n) = 0;
            deputy(i + chess(k) - 1) = 0;

这部分是回溯算法的核心。它交换皇后的位置，更新对角线的状态，对下一行进行递归调用，然后通过恢复原始状态进行回溯。
6 E$ \% Y2 K" j; [4 Z        end
    end
end

$ p5 k& l% p" e( _* f' T$ E) K0 j这结束了循环和函数。如果i不是9，循环将继续到下一行。
0 I+ V* x( r& a. u7 Pclear all
clc
) [5 i5 }0 h5 e( l! m" ?( l$ X
这些命令清除工作区和命令窗口。
n = 8;
chess = zeros(1, n);
* C0 S1 f/ Q( y8 n! ]0 Pfor i = 1:n
    chess(i) = i;
' C) y* l/ X: H/ l2 d2 S+ uend

这初始化了一个带有皇后的第一行的棋盘。
main = zeros(1, 2 * n - 1); % 记录主对角线的使用情况
deputy = zeros(1, 2 * n - 1); % 记录副对角线的使用情况
! H% I$ e  {+ K2 W+ q. j4 i5 znumber = 0;
4 _) C' c. X. J( X( I4 l[chess, main, deputy, number] = justtry(1, n, chess, main, deputy, number);

; @4 ^: D. N% G8 y6 }% i( X8 ^9 q这初始化了数组以跟踪主对角线和副对角线的情况，并通过调用justtry开始了递归回溯。整个过程将探索在8x8棋盘上所有可能的皇后排列，并打印每个有效排列以及解的总数。
: ]. K+ F$ n3 L+ r- L

6 H) n, N1 m8 z# ]