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

2744557306

这是一个MATLAB实现的N皇后问题，这是一个经典的组合问题。其目标是在一个N×N的棋盘上放置N个皇后，使得它们之间互不攻击。提供的代码使用了递归回溯的方法来找到N皇后问题的所有解决方案。
9 S$ }6 B* N- a7 R1 [) F/ S9 m让我们逐步解释这段代码：
: l) k6 x5 e& x  Nfunction [chess, main, deputy, number] = justtry(i, n, chess, main, deputy, number)

2 V( b- ]) m6 N* |* C# Q这定义了一个名为justtry的函数，它接受六个参数：当前行数i，棋盘大小n，当前皇后的排列chess，主对角线和副对角线的状态（main和deputy），以及解的数量number。
if i == 9
, A0 z* y. s  g- t* |, I' o8 E    number = number + 1;
3 y8 l1 `/ h# w# R& j    chess
: M0 e9 x" }9 a6 }; V- A+ L) Jelse
    for k = i:8
' }6 @- Z. R0 h  o        if main(i - chess(k) + n) == 0 && deputy(i + chess(k) - 1) == 0

这检查是否已经到达第9行。如果是这样，它会递增解的数量(number)并显示当前皇后在棋盘上的排列。否则，它进入一个从当前行(i)到8的循环。
嵌套的if语句检查当前棋盘位置是否有效（即没有皇后互相威胁）。如果条件满足，它将继续放置皇后。
: j+ C( b% }2 U* M7 d$ F            t = chess(k); % 交换位置
            chess(k) = chess(i);
: b  v2 }5 P/ R0 b3 l: T4 n            chess(i) = t;

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

$ ~- Z1 A" `5 P            [chess, main, deputy, number] = justtry(i + 1, n, chess, main, deputy, number); % 递归调用

            t = chess(k); % 回溯
            chess(k) = chess(i);
            chess(i) = t;

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

4 |: K( b0 c( i, w这部分是回溯算法的核心。它交换皇后的位置，更新对角线的状态，对下一行进行递归调用，然后通过恢复原始状态进行回溯。
3 W  b& |2 V8 q- q        end
    end
end
/ Q8 x0 w* [2 A
这结束了循环和函数。如果i不是9，循环将继续到下一行。
( P, {$ ^) M" A( v3 N2 |( Eclear all
! _1 L" O7 r: P0 W. K- Hclc
, Y6 E& t* _5 Z0 `, t
这些命令清除工作区和命令窗口。
5 w5 X& c7 f4 l( d4 z. in = 8;
, U) @1 n: R3 Dchess = zeros(1, n);
for i = 1:n
8 y5 e; T" t0 ~, b    chess(i) = i;
end
2 O9 @& P5 [' M: e  l! ~9 c. e
0 E* N. U8 u# \. ^' s这初始化了一个带有皇后的第一行的棋盘。
main = zeros(1, 2 * n - 1); % 记录主对角线的使用情况
) ^8 u) W, x( X5 P2 X2 r% Cdeputy = zeros(1, 2 * n - 1); % 记录副对角线的使用情况
# ?6 h  @& |" J& @, D9 vnumber = 0;
# l1 @- I" G1 D9 I% M/ O2 `( {[chess, main, deputy, number] = justtry(1, n, chess, main, deputy, number);

$ g3 h+ w, F( S5 z' Y6 d这初始化了数组以跟踪主对角线和副对角线的情况，并通过调用justtry开始了递归回溯。整个过程将探索在8x8棋盘上所有可能的皇后排列，并打印每个有效排列以及解的总数。


4 d/ e0 k) G% ?' D' z5 g! I