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

2744557306

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

这定义了一个名为justtry的函数，它接受六个参数：当前行数i，棋盘大小n，当前皇后的排列chess，主对角线和副对角线的状态（main和deputy），以及解的数量number。
if i == 9
$ n! A) D! s" X6 m    number = number + 1;
2 N* ?/ t# ^! u+ I+ {7 O    chess
else
8 E7 j" Q1 ]! z    for k = i:8
        if main(i - chess(k) + n) == 0 && deputy(i + chess(k) - 1) == 0

这检查是否已经到达第9行。如果是这样，它会递增解的数量(number)并显示当前皇后在棋盘上的排列。否则，它进入一个从当前行(i)到8的循环。
+ \) V) S2 u: [# N5 H/ }- o9 ~* z嵌套的if语句检查当前棋盘位置是否有效（即没有皇后互相威胁）。如果条件满足，它将继续放置皇后。
            t = chess(k); % 交换位置
; E/ I6 m! K* t9 a) p            chess(k) = chess(i);
            chess(i) = t;

            main(i - chess(k) + n) = 1;
            deputy(i + chess(k) - 1) = 1;
  {9 w( n% w: {! ^, T
8 r# |; P* ~$ X6 y            [chess, main, deputy, number] = justtry(i + 1, n, chess, main, deputy, number); % 递归调用
6 y6 z2 P0 y1 P5 E
4 S( L* O0 `$ j  c            t = chess(k); % 回溯
: \3 B; J$ l9 G  b7 ]/ h            chess(k) = chess(i);
            chess(i) = t;

5 c- O" }3 A- U$ r            main(i - chess(k) + n) = 0;
9 E1 ]$ }# I6 Z6 ?$ u( I. {            deputy(i + chess(k) - 1) = 0;
2 F  B* B" f" |- P( A7 s  m
/ w, H3 `/ W, j0 J这部分是回溯算法的核心。它交换皇后的位置，更新对角线的状态，对下一行进行递归调用，然后通过恢复原始状态进行回溯。
        end
" M* {. H7 d/ R    end
5 b" M$ ]7 Q7 P) l0 vend

/ Y; e6 y. K5 v这结束了循环和函数。如果i不是9，循环将继续到下一行。
clear all
5 L. K! R  [9 U* }5 O# E$ Q* Pclc
! d9 s8 j" n3 C  i& P: E
这些命令清除工作区和命令窗口。
; l% D; X+ R" Qn = 8;
$ w1 j6 @, F6 ochess = zeros(1, n);
for i = 1:n
0 P% {) p' t; ~, X    chess(i) = i;
  a" P2 j$ M- @1 `* f4 e; eend

+ B% z+ M& z/ V& g$ v这初始化了一个带有皇后的第一行的棋盘。
4 a) U, w4 E8 ~; d9 q+ W6 Fmain = zeros(1, 2 * n - 1); % 记录主对角线的使用情况
) v9 v* Y8 _5 n/ ]# p& Qdeputy = zeros(1, 2 * n - 1); % 记录副对角线的使用情况
' h" a0 ^" A# v' F2 [' T" X/ }number = 0;
[chess, main, deputy, number] = justtry(1, n, chess, main, deputy, number);

这初始化了数组以跟踪主对角线和副对角线的情况，并通过调用justtry开始了递归回溯。整个过程将探索在8x8棋盘上所有可能的皇后排列，并打印每个有效排列以及解的总数。