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

2744557306

这是一个MATLAB实现的N皇后问题，这是一个经典的组合问题。其目标是在一个N×N的棋盘上放置N个皇后，使得它们之间互不攻击。提供的代码使用了递归回溯的方法来找到N皇后问题的所有解决方案。
让我们逐步解释这段代码：
' ?# y1 M8 \" N4 m$ Z3 x2 J, gfunction [chess, main, deputy, number] = justtry(i, n, chess, main, deputy, number)

这定义了一个名为justtry的函数，它接受六个参数：当前行数i，棋盘大小n，当前皇后的排列chess，主对角线和副对角线的状态（main和deputy），以及解的数量number。
if i == 9
' ^  r, T8 ^! _( r; q- H. @    number = number + 1;
    chess
else
    for k = i:8
  M& x# Q2 {/ y: l        if main(i - chess(k) + n) == 0 && deputy(i + chess(k) - 1) == 0
- W% G1 }/ L6 ?* g: \
% A9 Z5 ?  X. ^/ u2 D8 _) |这检查是否已经到达第9行。如果是这样，它会递增解的数量(number)并显示当前皇后在棋盘上的排列。否则，它进入一个从当前行(i)到8的循环。
+ P* |1 s3 u2 @; j7 m% x$ z嵌套的if语句检查当前棋盘位置是否有效（即没有皇后互相威胁）。如果条件满足，它将继续放置皇后。
            t = chess(k); % 交换位置
            chess(k) = chess(i);
, X. i$ g% D/ ?+ P            chess(i) = t;
% q; i9 C# G& C( u
            main(i - chess(k) + n) = 1;
            deputy(i + chess(k) - 1) = 1;

! N( u' k) l8 X: D7 x; v* f7 ?* s            [chess, main, deputy, number] = justtry(i + 1, n, chess, main, deputy, number); % 递归调用
& l( m8 Z* [. ?$ _- O+ J
0 Z3 n4 @# M; C3 _            t = chess(k); % 回溯
$ `" y' V, a6 V) u            chess(k) = chess(i);
            chess(i) = t;
& Z% ~; B" O  j* C3 ]1 q
, a4 |) [/ U/ t/ }            main(i - chess(k) + n) = 0;
            deputy(i + chess(k) - 1) = 0;

这部分是回溯算法的核心。它交换皇后的位置，更新对角线的状态，对下一行进行递归调用，然后通过恢复原始状态进行回溯。
) f0 m9 x$ M" t$ x; q        end
    end
& q4 |2 u6 i' |1 S4 {end

这结束了循环和函数。如果i不是9，循环将继续到下一行。
9 ]6 O7 ~1 w! U" E% s- L; G& Y8 @' Qclear all
clc

8 d! W3 n, s; m4 W. ]0 x这些命令清除工作区和命令窗口。
n = 8;
: B2 b" k4 G6 ~+ D7 Gchess = zeros(1, n);
- Y7 |0 m" U2 j: ]# ~( H. o- Ffor i = 1:n
/ {4 j: y, o' Z0 o    chess(i) = i;
end
+ [, G" b' x7 B: L0 b( C
/ f) ?% w( ?; Q' S$ Y6 g7 L. P1 W这初始化了一个带有皇后的第一行的棋盘。
1 O& W7 l: _5 o2 \1 W; D5 m' omain = zeros(1, 2 * n - 1); % 记录主对角线的使用情况
9 H( B+ A6 ?  X( Udeputy = zeros(1, 2 * n - 1); % 记录副对角线的使用情况
- {1 o# T5 c0 W7 d) ?- k% snumber = 0;
[chess, main, deputy, number] = justtry(1, n, chess, main, deputy, number);
! C' z6 f5 W: D
  K1 L. Z5 @/ }5 g这初始化了数组以跟踪主对角线和副对角线的情况，并通过调用justtry开始了递归回溯。整个过程将探索在8x8棋盘上所有可能的皇后排列，并打印每个有效排列以及解的总数。

1 S9 h# u  j! H$ d