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

2744557306

这是一个MATLAB实现的N皇后问题，这是一个经典的组合问题。其目标是在一个N×N的棋盘上放置N个皇后，使得它们之间互不攻击。提供的代码使用了递归回溯的方法来找到N皇后问题的所有解决方案。
$ O5 T( _4 O0 Y2 t: a  D& Y让我们逐步解释这段代码：
% d8 s; b, l; d0 h6 Rfunction [chess, main, deputy, number] = justtry(i, n, chess, main, deputy, number)
# _9 `* v' T+ b% C) u' m2 ~8 H3 ^
1 {& d( u% K  ?5 D/ |这定义了一个名为justtry的函数，它接受六个参数：当前行数i，棋盘大小n，当前皇后的排列chess，主对角线和副对角线的状态（main和deputy），以及解的数量number。
if i == 9
    number = number + 1;
5 h* y" o+ P  o; g: M2 S. r    chess
else
    for k = i:8
        if main(i - chess(k) + n) == 0 && deputy(i + chess(k) - 1) == 0
' K; R5 t, S7 w$ f- S" t
2 z. x) l. Y  E这检查是否已经到达第9行。如果是这样，它会递增解的数量(number)并显示当前皇后在棋盘上的排列。否则，它进入一个从当前行(i)到8的循环。
嵌套的if语句检查当前棋盘位置是否有效（即没有皇后互相威胁）。如果条件满足，它将继续放置皇后。
            t = chess(k); % 交换位置
4 o- Z" U, j. B6 }/ k' ^            chess(k) = chess(i);
+ V" n8 E8 N; D; Z- i4 c            chess(i) = t;
6 G( w% i, a8 y
3 J7 p* f) i5 A            main(i - chess(k) + n) = 1;
            deputy(i + chess(k) - 1) = 1;

. R+ \! |- _+ X& M            [chess, main, deputy, number] = justtry(i + 1, n, chess, main, deputy, number); % 递归调用
' @! y. p$ _) K( V: w7 d
            t = chess(k); % 回溯
            chess(k) = chess(i);
            chess(i) = t;

            main(i - chess(k) + n) = 0;
            deputy(i + chess(k) - 1) = 0;

这部分是回溯算法的核心。它交换皇后的位置，更新对角线的状态，对下一行进行递归调用，然后通过恢复原始状态进行回溯。
) g3 Z  }/ q  k7 [; A        end
    end
end

7 y1 g0 D0 Z* U9 Z这结束了循环和函数。如果i不是9，循环将继续到下一行。
% s1 [+ A' }4 r' Yclear all
! {# ?* d9 O2 S2 J% U9 cclc

这些命令清除工作区和命令窗口。
n = 8;
chess = zeros(1, n);
( k' N0 F; A) L) ?* ufor i = 1:n
- S2 s  V5 p! V) q5 g8 f2 P* F    chess(i) = i;
& s1 W5 N4 _4 P! `/ a; ]end

这初始化了一个带有皇后的第一行的棋盘。
6 T' d7 y0 c8 P: mmain = zeros(1, 2 * n - 1); % 记录主对角线的使用情况
deputy = zeros(1, 2 * n - 1); % 记录副对角线的使用情况
number = 0;
[chess, main, deputy, number] = justtry(1, n, chess, main, deputy, number);

& C. v" T& ~  W! S# a( B这初始化了数组以跟踪主对角线和副对角线的情况，并通过调用justtry开始了递归回溯。整个过程将探索在8x8棋盘上所有可能的皇后排列，并打印每个有效排列以及解的总数。
3 V, r2 c& G1 t% w% j! C4 Q
5 \# @" R/ Q# S% j: g. Z3 ~
& ~- h% `- k' l" }5 a