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

2744557306

这是一个MATLAB实现的N皇后问题，这是一个经典的组合问题。其目标是在一个N×N的棋盘上放置N个皇后，使得它们之间互不攻击。提供的代码使用了递归回溯的方法来找到N皇后问题的所有解决方案。
让我们逐步解释这段代码：
4 F, u) b/ W8 |: }& }8 e: _3 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;
6 d" Z4 y' b  e! f. R( c    chess
+ k. H# _: S  i/ zelse
5 j5 _! U2 P; E) |9 B* I, V    for k = i:8
  G. f3 F8 K. }* f' G! W/ K( T4 Z        if main(i - chess(k) + n) == 0 && deputy(i + chess(k) - 1) == 0

. H) f! I- d2 b1 y3 ^这检查是否已经到达第9行。如果是这样，它会递增解的数量(number)并显示当前皇后在棋盘上的排列。否则，它进入一个从当前行(i)到8的循环。
/ [6 F' I# e( H; h7 h嵌套的if语句检查当前棋盘位置是否有效（即没有皇后互相威胁）。如果条件满足，它将继续放置皇后。
            t = chess(k); % 交换位置
6 j" s7 o3 X4 F1 j            chess(k) = chess(i);
            chess(i) = t;
- a% E8 M; k1 m( c+ E
            main(i - chess(k) + n) = 1;
            deputy(i + chess(k) - 1) = 1;
0 d/ Y* {, x3 e, a
            [chess, main, deputy, number] = justtry(i + 1, n, chess, main, deputy, number); % 递归调用
* m) k9 t: ^5 g# u  M" E/ W
            t = chess(k); % 回溯
. v5 ^5 B& C7 ~2 k1 u; N3 s$ k+ Q            chess(k) = chess(i);
. r" X/ |3 G/ k& z8 h% N, C            chess(i) = t;

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

/ ?9 H) V- d6 W: M5 Z6 b+ k- g这部分是回溯算法的核心。它交换皇后的位置，更新对角线的状态，对下一行进行递归调用，然后通过恢复原始状态进行回溯。
        end
    end
end
& M3 c8 A, ^  C+ }0 d6 S5 u6 R
  l) a! n. P6 I7 \" d9 ~6 y; J这结束了循环和函数。如果i不是9，循环将继续到下一行。
clear all
; D& Q: r: r$ o; P8 ?; G4 Hclc

这些命令清除工作区和命令窗口。
5 n! _+ B4 L' r8 V# W. I+ u2 Wn = 8;
chess = zeros(1, n);
for i = 1:n
2 B, K0 _3 Q* Z: Q9 e# j5 M$ U2 u    chess(i) = i;
, X6 P  F- N3 l+ C8 mend

这初始化了一个带有皇后的第一行的棋盘。
main = zeros(1, 2 * n - 1); % 记录主对角线的使用情况
deputy = zeros(1, 2 * n - 1); % 记录副对角线的使用情况
number = 0;
[chess, main, deputy, number] = justtry(1, n, chess, main, deputy, number);
2 O8 }+ N: Q; M  f+ t
这初始化了数组以跟踪主对角线和副对角线的情况，并通过调用justtry开始了递归回溯。整个过程将探索在8x8棋盘上所有可能的皇后排列，并打印每个有效排列以及解的总数。
; ]: ^. n" m# q

2 k! y' k% O1 T0 f