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

2744557306

这是一个MATLAB实现的N皇后问题，这是一个经典的组合问题。其目标是在一个N×N的棋盘上放置N个皇后，使得它们之间互不攻击。提供的代码使用了递归回溯的方法来找到N皇后问题的所有解决方案。
: w4 Q- l4 o8 Q/ N' J让我们逐步解释这段代码：
3 {- t1 }% h' Q$ sfunction [chess, main, deputy, number] = justtry(i, n, chess, main, deputy, number)

7 S# b; @( s' J这定义了一个名为justtry的函数，它接受六个参数：当前行数i，棋盘大小n，当前皇后的排列chess，主对角线和副对角线的状态（main和deputy），以及解的数量number。
if i == 9
    number = number + 1;
    chess
  w) L8 b& ^- V  l  }$ X6 `else
    for k = i:8
        if main(i - chess(k) + n) == 0 && deputy(i + chess(k) - 1) == 0

这检查是否已经到达第9行。如果是这样，它会递增解的数量(number)并显示当前皇后在棋盘上的排列。否则，它进入一个从当前行(i)到8的循环。
嵌套的if语句检查当前棋盘位置是否有效（即没有皇后互相威胁）。如果条件满足，它将继续放置皇后。
2 g$ M+ |. d* C, q: m            t = chess(k); % 交换位置
! W) b6 q0 v, `" n  U            chess(k) = chess(i);
; [  V. R; R1 j            chess(i) = t;
2 ^! L8 B- `: K9 _! U! N
( A' k9 K* H: {: G9 k            main(i - chess(k) + n) = 1;
            deputy(i + chess(k) - 1) = 1;
% ?1 y) D) K. D" Q, n
            [chess, main, deputy, number] = justtry(i + 1, n, chess, main, deputy, number); % 递归调用

" f+ }6 l9 h% K            t = chess(k); % 回溯
            chess(k) = chess(i);
' G- N3 e! y( t4 a% f            chess(i) = t;
( k+ J! G3 x4 F  d( V, ?- e
            main(i - chess(k) + n) = 0;
            deputy(i + chess(k) - 1) = 0;
, M7 Z5 n, S* r1 \; E
+ ]5 s7 \8 @! N9 _  C这部分是回溯算法的核心。它交换皇后的位置，更新对角线的状态，对下一行进行递归调用，然后通过恢复原始状态进行回溯。
; \5 E1 @3 H9 _7 f! _& T        end
    end
, ?3 {6 ]8 A$ X6 A1 Z7 @end
, W: F) m) r( z2 `7 K
这结束了循环和函数。如果i不是9，循环将继续到下一行。
clear all
clc
+ O3 [* Y, y, z  M
这些命令清除工作区和命令窗口。
n = 8;
' `5 `  P2 [5 M# W/ pchess = zeros(1, n);
for i = 1:n
    chess(i) = i;
end

这初始化了一个带有皇后的第一行的棋盘。
7 _. J4 h: i: \) T8 I/ @main = zeros(1, 2 * n - 1); % 记录主对角线的使用情况
deputy = zeros(1, 2 * n - 1); % 记录副对角线的使用情况
number = 0;
) P: ?1 h% k0 B$ k! ^[chess, main, deputy, number] = justtry(1, n, chess, main, deputy, number);

" {+ L2 R0 {  f# e2 q# K这初始化了数组以跟踪主对角线和副对角线的情况，并通过调用justtry开始了递归回溯。整个过程将探索在8x8棋盘上所有可能的皇后排列，并打印每个有效排列以及解的总数。
2 ^: D6 ^, T$ f
. p& s3 D( W0 q
# s. ^! m3 z+ m' b; D/ b