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

2744557306

这是一个MATLAB实现的N皇后问题，这是一个经典的组合问题。其目标是在一个N×N的棋盘上放置N个皇后，使得它们之间互不攻击。提供的代码使用了递归回溯的方法来找到N皇后问题的所有解决方案。
; o7 c# q$ `3 w0 M让我们逐步解释这段代码：
function [chess, main, deputy, number] = justtry(i, n, chess, main, deputy, number)

这定义了一个名为justtry的函数，它接受六个参数：当前行数i，棋盘大小n，当前皇后的排列chess，主对角线和副对角线的状态（main和deputy），以及解的数量number。
if i == 9
: m) }$ U6 K( n/ I+ Z    number = number + 1;
6 v9 ~- ^; N$ h0 x0 ~    chess
else
4 h. B5 D2 U2 D) I    for k = i:8
        if main(i - chess(k) + n) == 0 && deputy(i + chess(k) - 1) == 0
- p4 U' a* f8 X  U% X' ~5 B. v
这检查是否已经到达第9行。如果是这样，它会递增解的数量(number)并显示当前皇后在棋盘上的排列。否则，它进入一个从当前行(i)到8的循环。
嵌套的if语句检查当前棋盘位置是否有效（即没有皇后互相威胁）。如果条件满足，它将继续放置皇后。
5 Y9 V- {2 k, b6 u3 M+ L* U            t = chess(k); % 交换位置
+ ]% a- g, _* v6 m2 k) {1 w            chess(k) = chess(i);
            chess(i) = t;

            main(i - chess(k) + n) = 1;
2 G! L  W1 c1 m- d* d            deputy(i + chess(k) - 1) = 1;
* z0 \/ r4 b" k& \  M( n- E) u& A
2 f8 ?. L' u  Z            [chess, main, deputy, number] = justtry(i + 1, n, chess, main, deputy, number); % 递归调用

0 X1 K, G: |0 B9 q! L: T% ]            t = chess(k); % 回溯
, F7 f8 h7 f1 d- M& B; ?8 w- ~            chess(k) = chess(i);
            chess(i) = t;

7 d' P3 R* K( z$ O0 p: Z            main(i - chess(k) + n) = 0;
1 q* ]$ A1 O! r' t6 D8 \% O9 ~$ I            deputy(i + chess(k) - 1) = 0;

  M9 d2 [8 b1 N4 p这部分是回溯算法的核心。它交换皇后的位置，更新对角线的状态，对下一行进行递归调用，然后通过恢复原始状态进行回溯。
$ x! T, Z2 G) ?' r, Y        end
    end
end
, ]) \+ ~5 U" s5 }. R
这结束了循环和函数。如果i不是9，循环将继续到下一行。
) p% Q2 R9 {3 j) _2 E) sclear all
( h4 s4 X# Z( A+ @6 y4 h1 aclc
$ Z- G7 N3 f! i3 w( o% P# M5 m
3 ^& @, }' Q" t" \* N9 [& I这些命令清除工作区和命令窗口。
n = 8;
2 G8 x" {  f7 G- {# D& J* C6 n6 Jchess = zeros(1, n);
1 ?8 l, k1 V! j; [' U8 L  Jfor i = 1:n
( d+ m/ @9 A4 K9 C* b    chess(i) = i;
+ B  z/ n$ b/ aend
- p4 p9 a+ Y$ R3 B( M6 w+ A
这初始化了一个带有皇后的第一行的棋盘。
main = zeros(1, 2 * n - 1); % 记录主对角线的使用情况
! V/ m5 D4 E* \9 D) _9 [  \( hdeputy = zeros(1, 2 * n - 1); % 记录副对角线的使用情况
) G2 {# r* S0 a: Mnumber = 0;
2 j4 N4 |7 _' B' D) m. K& W3 c[chess, main, deputy, number] = justtry(1, n, chess, main, deputy, number);
6 u( k. g2 Y+ D. v5 M# G" t
这初始化了数组以跟踪主对角线和副对角线的情况，并通过调用justtry开始了递归回溯。整个过程将探索在8x8棋盘上所有可能的皇后排列，并打印每个有效排列以及解的总数。
- T1 |6 l* B3 ~$ c
7 n& J% P8 f, y/ `6 p. A2 f& ~* C
6 P7 I0 }% z( w5 h0 F9 Z