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

2744557306

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

, H( _, z" D. z* `2 J这定义了一个名为justtry的函数，它接受六个参数：当前行数i，棋盘大小n，当前皇后的排列chess，主对角线和副对角线的状态（main和deputy），以及解的数量number。
if i == 9
    number = number + 1;
    chess
else
4 Q3 d/ f7 m& I/ }3 v2 L3 a    for k = i:8
        if main(i - chess(k) + n) == 0 && deputy(i + chess(k) - 1) == 0
4 e7 {/ r, R) H0 z/ F
这检查是否已经到达第9行。如果是这样，它会递增解的数量(number)并显示当前皇后在棋盘上的排列。否则，它进入一个从当前行(i)到8的循环。
  z/ m  D. v3 b  p3 A# b9 D嵌套的if语句检查当前棋盘位置是否有效（即没有皇后互相威胁）。如果条件满足，它将继续放置皇后。
. c) F' d3 M1 K; V2 I' L            t = chess(k); % 交换位置
            chess(k) = chess(i);
' [$ d: M1 O9 y8 o# G            chess(i) = t;

            main(i - chess(k) + n) = 1;
! c8 N* X9 `6 Z, L4 e* g            deputy(i + chess(k) - 1) = 1;
0 r3 D& D# {3 [$ i& h. q! U
            [chess, main, deputy, number] = justtry(i + 1, n, chess, main, deputy, number); % 递归调用
2 j/ w+ F* Z6 }5 }9 ?
            t = chess(k); % 回溯
            chess(k) = chess(i);
            chess(i) = t;

            main(i - chess(k) + n) = 0;
$ s5 q2 _, X$ `% d( [4 X            deputy(i + chess(k) - 1) = 0;

  S2 Q: p0 e; W: y7 w% S这部分是回溯算法的核心。它交换皇后的位置，更新对角线的状态，对下一行进行递归调用，然后通过恢复原始状态进行回溯。
  z) K" D. O! H3 G4 Y. r        end
) U3 L, I+ ~) S- T0 W# `0 {; m2 u    end
( F- |5 ~+ I% g# nend

. W; v7 x2 ^. I! q* ^这结束了循环和函数。如果i不是9，循环将继续到下一行。
clear all
& l0 d8 j3 a* cclc
1 X  Y$ J5 A) U8 w  v+ S
% F5 q& E2 U) Q: T: U- E3 P$ d这些命令清除工作区和命令窗口。
% ~9 B+ H4 n# r' U4 i6 Qn = 8;
chess = zeros(1, n);
, H7 `" u3 |+ u) p0 c& Ifor i = 1:n
    chess(i) = i;
end
+ q  a6 ?2 n8 O  Z" a- w7 i- r) p
$ s" }& X1 y4 D6 m4 ^! d  `这初始化了一个带有皇后的第一行的棋盘。
main = zeros(1, 2 * n - 1); % 记录主对角线的使用情况
) n& {1 n6 O4 T: jdeputy = zeros(1, 2 * n - 1); % 记录副对角线的使用情况
1 G/ q4 t# H: o! m5 tnumber = 0;
4 W9 W  b2 I- C" ~' @[chess, main, deputy, number] = justtry(1, n, chess, main, deputy, number);

这初始化了数组以跟踪主对角线和副对角线的情况，并通过调用justtry开始了递归回溯。整个过程将探索在8x8棋盘上所有可能的皇后排列，并打印每个有效排列以及解的总数。
) l) a# V3 F2 ~: w% w% B
8 Q; C0 ]' ~  C3 a