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

2744557306

这是一个MATLAB实现的N皇后问题，这是一个经典的组合问题。其目标是在一个N×N的棋盘上放置N个皇后，使得它们之间互不攻击。提供的代码使用了递归回溯的方法来找到N皇后问题的所有解决方案。
' {3 @+ I" r8 f8 T2 P9 A1 U4 {让我们逐步解释这段代码：
* ^5 D2 n2 ^" J  C: f5 `function [chess, main, deputy, number] = justtry(i, n, chess, main, deputy, number)

这定义了一个名为justtry的函数，它接受六个参数：当前行数i，棋盘大小n，当前皇后的排列chess，主对角线和副对角线的状态（main和deputy），以及解的数量number。
% W/ A1 A. W" c1 ~$ rif i == 9
    number = number + 1;
+ Y9 v: W+ w' Q! \    chess
else
    for k = i:8
        if main(i - chess(k) + n) == 0 && deputy(i + chess(k) - 1) == 0

这检查是否已经到达第9行。如果是这样，它会递增解的数量(number)并显示当前皇后在棋盘上的排列。否则，它进入一个从当前行(i)到8的循环。
嵌套的if语句检查当前棋盘位置是否有效（即没有皇后互相威胁）。如果条件满足，它将继续放置皇后。
            t = chess(k); % 交换位置
' O. S. N2 t) j' T& H) S/ W            chess(k) = chess(i);
            chess(i) = t;
9 q4 s/ q, D  L' w
! c7 d( r5 a4 X8 l! v2 f" f$ ?            main(i - chess(k) + n) = 1;
            deputy(i + chess(k) - 1) = 1;
2 ]* l5 Q0 D6 C) M
            [chess, main, deputy, number] = justtry(i + 1, n, chess, main, deputy, number); % 递归调用

  D: t: K3 {8 ]9 d            t = chess(k); % 回溯
            chess(k) = chess(i);
            chess(i) = t;

$ D- @( A4 r- i5 ^1 Q0 I' a            main(i - chess(k) + n) = 0;
! v/ p* k1 R' g0 y% ]: y            deputy(i + chess(k) - 1) = 0;
. e7 B' T, {+ x* r6 e* h3 F
这部分是回溯算法的核心。它交换皇后的位置，更新对角线的状态，对下一行进行递归调用，然后通过恢复原始状态进行回溯。
! x* e/ p; i0 B0 w* [7 a; _: |: m        end
6 ]: G( k1 A: z8 E    end
end

这结束了循环和函数。如果i不是9，循环将继续到下一行。
clear all
clc

这些命令清除工作区和命令窗口。
$ E( G: ]7 E4 p" W0 yn = 8;
chess = zeros(1, n);
for i = 1:n
3 S. s7 M# x. j    chess(i) = i;
end
. S9 o; A3 t: W
这初始化了一个带有皇后的第一行的棋盘。
  }- d9 G! |" z! ?2 ], u5 H* cmain = zeros(1, 2 * n - 1); % 记录主对角线的使用情况
. Z0 a4 ~4 y: tdeputy = zeros(1, 2 * n - 1); % 记录副对角线的使用情况
number = 0;
[chess, main, deputy, number] = justtry(1, n, chess, main, deputy, number);

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

+ x2 g8 u5 S2 |4 ?) F* a
7 b5 A4 X9 S' E* ]) o% f