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

2744557306

这是一个MATLAB实现的N皇后问题，这是一个经典的组合问题。其目标是在一个N×N的棋盘上放置N个皇后，使得它们之间互不攻击。提供的代码使用了递归回溯的方法来找到N皇后问题的所有解决方案。
8 C* ?& ?  I+ Q( A让我们逐步解释这段代码：
9 C6 G/ k# ^! Wfunction [chess, main, deputy, number] = justtry(i, n, chess, main, deputy, number)

这定义了一个名为justtry的函数，它接受六个参数：当前行数i，棋盘大小n，当前皇后的排列chess，主对角线和副对角线的状态（main和deputy），以及解的数量number。
7 p7 q; N$ X" Z, b  Pif i == 9
* T3 j! a9 W+ K& N, M! ^: A0 V    number = number + 1;
    chess
else
    for k = i:8
# e% E2 ?5 `' ]3 g! m+ q( E( @        if main(i - chess(k) + n) == 0 && deputy(i + chess(k) - 1) == 0

这检查是否已经到达第9行。如果是这样，它会递增解的数量(number)并显示当前皇后在棋盘上的排列。否则，它进入一个从当前行(i)到8的循环。
9 q8 o: O8 L% Y# d- o嵌套的if语句检查当前棋盘位置是否有效（即没有皇后互相威胁）。如果条件满足，它将继续放置皇后。
: ?! A0 B6 J1 ?/ \9 R            t = chess(k); % 交换位置
/ O' p2 G. m& |7 D# u9 r+ L$ u            chess(k) = chess(i);
* @; p' \9 ?  {3 _9 w            chess(i) = t;

* P; e2 r9 o4 B+ E3 {, W5 N* D+ i* V& n            main(i - chess(k) + n) = 1;
            deputy(i + chess(k) - 1) = 1;

            [chess, main, deputy, number] = justtry(i + 1, n, chess, main, deputy, number); % 递归调用

            t = chess(k); % 回溯
            chess(k) = chess(i);
0 o3 G0 k# D% B, z2 t            chess(i) = t;

            main(i - chess(k) + n) = 0;
* H1 P4 X& z+ N            deputy(i + chess(k) - 1) = 0;
8 M( b5 k' [# H' |* p( s
0 V+ g0 O# Q; H( Q+ w2 f2 I这部分是回溯算法的核心。它交换皇后的位置，更新对角线的状态，对下一行进行递归调用，然后通过恢复原始状态进行回溯。
        end
0 R+ M1 M" W- X! }    end
end
0 U+ W" `- f/ B% L) `
' S, F% {+ ~' t9 e4 q% y, ]这结束了循环和函数。如果i不是9，循环将继续到下一行。
clear all
6 _3 @5 _. c: Fclc
6 e) ?$ m' J, Y3 V
; W, t9 F, E3 i/ F这些命令清除工作区和命令窗口。
: s6 I- [) X7 F- D+ y+ ^3 En = 8;
chess = zeros(1, n);
for i = 1:n
    chess(i) = i;
. \7 X$ y" ~- O0 T$ w2 y8 Fend
* m( d$ C% S5 o# q9 O( B
3 `. \3 H$ |' z( Z* Z这初始化了一个带有皇后的第一行的棋盘。
4 F8 j! i% @2 k: L2 v0 X  Y4 R0 F' Vmain = zeros(1, 2 * n - 1); % 记录主对角线的使用情况
deputy = zeros(1, 2 * n - 1); % 记录副对角线的使用情况
# `5 @4 }" M) }# ?! V6 e$ n, c( f/ anumber = 0;
[chess, main, deputy, number] = justtry(1, n, chess, main, deputy, number);

- u" D' m. j  e" N这初始化了数组以跟踪主对角线和副对角线的情况，并通过调用justtry开始了递归回溯。整个过程将探索在8x8棋盘上所有可能的皇后排列，并打印每个有效排列以及解的总数。
) u& B) y: L, Z/ A+ O0 c& f
2 l# N  u$ b; O9 ~: H