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

2744557306

这是一个MATLAB实现的N皇后问题，这是一个经典的组合问题。其目标是在一个N×N的棋盘上放置N个皇后，使得它们之间互不攻击。提供的代码使用了递归回溯的方法来找到N皇后问题的所有解决方案。
) O( \' f8 R2 H. s8 _让我们逐步解释这段代码：
! _. T1 _% B' s% E9 Tfunction [chess, main, deputy, number] = justtry(i, n, chess, main, deputy, number)

这定义了一个名为justtry的函数，它接受六个参数：当前行数i，棋盘大小n，当前皇后的排列chess，主对角线和副对角线的状态（main和deputy），以及解的数量number。
1 E! f) K2 F9 ~, [2 Kif i == 9
6 ?/ e& C$ @1 j- b    number = number + 1;
3 k/ i9 A) L& Z8 Z    chess
3 T1 {# L: U1 P$ m1 W% gelse
    for k = i:8
7 S( z0 h; ]% `1 n1 ?! e        if main(i - chess(k) + n) == 0 && deputy(i + chess(k) - 1) == 0

* P  J5 b: U$ {+ l$ X2 M这检查是否已经到达第9行。如果是这样，它会递增解的数量(number)并显示当前皇后在棋盘上的排列。否则，它进入一个从当前行(i)到8的循环。
嵌套的if语句检查当前棋盘位置是否有效（即没有皇后互相威胁）。如果条件满足，它将继续放置皇后。
            t = chess(k); % 交换位置
! B+ ]3 A% \; I, ?  T            chess(k) = chess(i);
            chess(i) = t;

7 t0 V0 z1 L! ]+ D& i1 Y1 l            main(i - chess(k) + n) = 1;
) `2 Q6 ~% l% D' @            deputy(i + chess(k) - 1) = 1;

            [chess, main, deputy, number] = justtry(i + 1, n, chess, main, deputy, number); % 递归调用
5 s2 ?1 f4 z2 z, ]2 E% ^
            t = chess(k); % 回溯
$ p/ @! g6 e- _9 t- h            chess(k) = chess(i);
            chess(i) = t;
- m/ T6 k3 j  H
            main(i - chess(k) + n) = 0;
- U9 e: _$ i4 f; |6 J5 y) h) L            deputy(i + chess(k) - 1) = 0;

4 ]* {  D) H+ G+ _7 Z! i( f这部分是回溯算法的核心。它交换皇后的位置，更新对角线的状态，对下一行进行递归调用，然后通过恢复原始状态进行回溯。
        end
    end
end

" q+ t3 m# `# K这结束了循环和函数。如果i不是9，循环将继续到下一行。
clear all
8 |6 O. m, N7 t/ wclc
3 g, g+ `3 B+ Q" ?& o- I* p
; K4 @& {3 M& p+ g1 p" s9 o这些命令清除工作区和命令窗口。
n = 8;
chess = zeros(1, n);
for i = 1:n
  L( o  p6 I4 A  ~    chess(i) = i;
- i1 e5 i  B1 f) y, ?0 Jend
+ S& V, E" p# ^5 p+ d4 m" f
& o: d8 G$ k/ ]这初始化了一个带有皇后的第一行的棋盘。
main = zeros(1, 2 * n - 1); % 记录主对角线的使用情况
" v  T$ j! I+ U4 y& Pdeputy = zeros(1, 2 * n - 1); % 记录副对角线的使用情况
number = 0;
) S* A" b3 \7 O[chess, main, deputy, number] = justtry(1, n, chess, main, deputy, number);
( K; `$ e# t# z- z+ g: u; J/ P
3 L2 D" Q# Z( i! @9 o这初始化了数组以跟踪主对角线和副对角线的情况，并通过调用justtry开始了递归回溯。整个过程将探索在8x8棋盘上所有可能的皇后排列，并打印每个有效排列以及解的总数。
6 d! m0 Y0 B: Y$ @2 k- N- E( T
) [- T' F4 ?. T. A# |4 ]7 ~