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

2744557306

这是一个MATLAB实现的N皇后问题，这是一个经典的组合问题。其目标是在一个N×N的棋盘上放置N个皇后，使得它们之间互不攻击。提供的代码使用了递归回溯的方法来找到N皇后问题的所有解决方案。
: N9 a: N9 s/ U$ ^. n* D  u: Y让我们逐步解释这段代码：
function [chess, main, deputy, number] = justtry(i, n, chess, main, deputy, number)
' X% |) K! x# o" L: B6 l
& j8 |# {; c; f, v. d* N这定义了一个名为justtry的函数，它接受六个参数：当前行数i，棋盘大小n，当前皇后的排列chess，主对角线和副对角线的状态（main和deputy），以及解的数量number。
0 {4 j7 A  l/ P: f5 mif i == 9
2 i" y/ i) J; Q    number = number + 1;
    chess
else
    for k = i:8
        if main(i - chess(k) + n) == 0 && deputy(i + chess(k) - 1) == 0

这检查是否已经到达第9行。如果是这样，它会递增解的数量(number)并显示当前皇后在棋盘上的排列。否则，它进入一个从当前行(i)到8的循环。
嵌套的if语句检查当前棋盘位置是否有效（即没有皇后互相威胁）。如果条件满足，它将继续放置皇后。
; J9 m- T$ B$ V6 D" H6 g2 S            t = chess(k); % 交换位置
            chess(k) = chess(i);
            chess(i) = t;
+ s/ z5 o. J8 D4 f# w3 H5 z% P7 Y7 s
            main(i - chess(k) + n) = 1;
, }% r! a' ^1 K, y# U            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);
            chess(i) = t;

: E7 w+ v5 k5 d' z, T$ ~, b            main(i - chess(k) + n) = 0;
            deputy(i + chess(k) - 1) = 0;

这部分是回溯算法的核心。它交换皇后的位置，更新对角线的状态，对下一行进行递归调用，然后通过恢复原始状态进行回溯。
        end
& y0 O# d- O, X& Q# h: b& {    end
end

5 P) V! e# ~) c. V$ U: }  S这结束了循环和函数。如果i不是9，循环将继续到下一行。
clear all
clc

1 p. w5 W  m5 V& g. w这些命令清除工作区和命令窗口。
. |9 S6 s3 w* I! D! m" Dn = 8;
chess = zeros(1, n);
for i = 1:n
' D3 G1 v2 N! [( s    chess(i) = i;
' ]  e7 p& j* y/ w% r+ ?5 xend

1 n1 K0 d" X6 m5 [# \这初始化了一个带有皇后的第一行的棋盘。
: q& ~$ @; i9 B" ~main = zeros(1, 2 * n - 1); % 记录主对角线的使用情况
deputy = zeros(1, 2 * n - 1); % 记录副对角线的使用情况
6 Q+ X( Y8 |* n+ I+ G& Unumber = 0;
[chess, main, deputy, number] = justtry(1, n, chess, main, deputy, number);
2 F  }5 i3 [+ l! `( [+ X) w
4 F* D+ _# u/ t3 l5 E$ d这初始化了数组以跟踪主对角线和副对角线的情况，并通过调用justtry开始了递归回溯。整个过程将探索在8x8棋盘上所有可能的皇后排列，并打印每个有效排列以及解的总数。
2 F. _" S8 K2 r3 c4 j2 b9 @