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

2744557306

这是一个MATLAB实现的N皇后问题，这是一个经典的组合问题。其目标是在一个N×N的棋盘上放置N个皇后，使得它们之间互不攻击。提供的代码使用了递归回溯的方法来找到N皇后问题的所有解决方案。
9 f( {" \7 C  t2 [% ~# \2 D" k让我们逐步解释这段代码：
# Z" P2 g* V8 J- mfunction [chess, main, deputy, number] = justtry(i, n, chess, main, deputy, number)

这定义了一个名为justtry的函数，它接受六个参数：当前行数i，棋盘大小n，当前皇后的排列chess，主对角线和副对角线的状态（main和deputy），以及解的数量number。
if i == 9
    number = number + 1;
( A: q! D- m7 |  _6 O0 q; @% \    chess
. ]0 r! r2 v- O, j5 P5 r; F- L. relse
    for k = i:8
1 F3 I- X( k1 N) V7 n) k, I        if main(i - chess(k) + n) == 0 && deputy(i + chess(k) - 1) == 0

+ S; H& a  [  c# h$ e" V  {这检查是否已经到达第9行。如果是这样，它会递增解的数量(number)并显示当前皇后在棋盘上的排列。否则，它进入一个从当前行(i)到8的循环。
嵌套的if语句检查当前棋盘位置是否有效（即没有皇后互相威胁）。如果条件满足，它将继续放置皇后。
2 h+ C0 l% m7 Y6 }9 K  b. e! |) @            t = chess(k); % 交换位置
9 b, |$ n) \% |. V) Q9 t5 P0 ]            chess(k) = chess(i);
: ]+ X+ B+ q, g            chess(i) = t;
1 S7 f+ E0 Y4 I8 ]
            main(i - chess(k) + n) = 1;
            deputy(i + chess(k) - 1) = 1;
% h# k4 P+ V$ C! k: F: b
            [chess, main, deputy, number] = justtry(i + 1, n, chess, main, deputy, number); % 递归调用
. x% h- [3 s9 x
            t = chess(k); % 回溯
- B1 o! V, M4 d9 G0 r+ C2 ]            chess(k) = chess(i);
$ w; p. d7 p0 A1 F            chess(i) = t;

- t6 `6 b: w6 Y            main(i - chess(k) + n) = 0;
* w% F& }; W1 D! ?& C6 b5 r3 }& n            deputy(i + chess(k) - 1) = 0;
& r; y9 i! `" b
% M1 r- m/ p- u# w- [这部分是回溯算法的核心。它交换皇后的位置，更新对角线的状态，对下一行进行递归调用，然后通过恢复原始状态进行回溯。
' B3 k: A# z5 V8 g        end
    end
) r6 M" v5 K5 B. K1 [2 g4 P) }end

* @9 g! k# \7 R1 [% V  O" v这结束了循环和函数。如果i不是9，循环将继续到下一行。
clear all
0 \2 t# p/ c3 {/ Jclc
0 i( c; Q3 ], d) h6 m$ a% B
! p& a6 ?  A  K0 e1 g这些命令清除工作区和命令窗口。
n = 8;
chess = zeros(1, n);
for i = 1:n
# k& H# h- j1 Z% T0 z, a    chess(i) = i;
end

5 Z8 ^4 |# A6 p. w$ I: |: v! R& T5 S这初始化了一个带有皇后的第一行的棋盘。
: ^# ^( g- `3 x3 `main = zeros(1, 2 * n - 1); % 记录主对角线的使用情况
/ q& X, o6 ~+ G- Zdeputy = zeros(1, 2 * n - 1); % 记录副对角线的使用情况
number = 0;
[chess, main, deputy, number] = justtry(1, n, chess, main, deputy, number);

这初始化了数组以跟踪主对角线和副对角线的情况，并通过调用justtry开始了递归回溯。整个过程将探索在8x8棋盘上所有可能的皇后排列，并打印每个有效排列以及解的总数。
5 n1 s) z1 n* ?" z
2 ]8 n6 `% ~) m* v: ]* z
2 j/ s0 y3 Q0 i" l- ?" g0 _