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

2744557306

这是一个MATLAB实现的N皇后问题，这是一个经典的组合问题。其目标是在一个N×N的棋盘上放置N个皇后，使得它们之间互不攻击。提供的代码使用了递归回溯的方法来找到N皇后问题的所有解决方案。
让我们逐步解释这段代码：
function [chess, main, deputy, number] = justtry(i, n, chess, main, deputy, number)
. v% F, ^- F* W; l1 C! a
这定义了一个名为justtry的函数，它接受六个参数：当前行数i，棋盘大小n，当前皇后的排列chess，主对角线和副对角线的状态（main和deputy），以及解的数量number。
if i == 9
    number = number + 1;
    chess
+ p! T" _9 E+ K' g; Belse
/ X; j7 h1 Z" X5 s3 F. p% F    for k = i:8
( B/ o' |5 _# |) t$ K        if main(i - chess(k) + n) == 0 && deputy(i + chess(k) - 1) == 0
( r; K3 d# g" L' A) g# q& `1 j( q
这检查是否已经到达第9行。如果是这样，它会递增解的数量(number)并显示当前皇后在棋盘上的排列。否则，它进入一个从当前行(i)到8的循环。
- u  g0 y$ E+ R) i+ H# F+ v嵌套的if语句检查当前棋盘位置是否有效（即没有皇后互相威胁）。如果条件满足，它将继续放置皇后。
' L$ V9 G8 s3 L/ A( _% Y            t = chess(k); % 交换位置
/ W! Q4 [" k4 P: u6 k            chess(k) = chess(i);
            chess(i) = t;

* P$ q- A, K- O+ n0 H            main(i - chess(k) + n) = 1;
            deputy(i + chess(k) - 1) = 1;

& P6 P2 ]( e2 o: _) {3 r' K            [chess, main, deputy, number] = justtry(i + 1, n, chess, main, deputy, number); % 递归调用
' T% g  K7 _6 q% F9 r; M
            t = chess(k); % 回溯
            chess(k) = chess(i);
' l) @6 e+ c. M) ~( o9 Q            chess(i) = t;
/ h9 ?' e+ s) V. H, Z0 u
& {2 `9 B7 R1 \/ j. J            main(i - chess(k) + n) = 0;
  Y& ?2 B. O/ j, i' H6 j, U            deputy(i + chess(k) - 1) = 0;
& ]' ]6 x$ W4 F& U
4 |4 f( e! u* J; `& a. v9 V这部分是回溯算法的核心。它交换皇后的位置，更新对角线的状态，对下一行进行递归调用，然后通过恢复原始状态进行回溯。
# c9 I3 a' X* G# L& D* P: s        end
    end
end
, p* M$ j& D5 C+ S' L( v0 m3 W  \
+ P3 Z) {7 P8 g4 V; A6 k这结束了循环和函数。如果i不是9，循环将继续到下一行。
5 C- k/ r$ }9 C+ q* ]clear all
clc

$ I  ?! E9 g  M; A+ G这些命令清除工作区和命令窗口。
+ _8 t0 s1 m3 E5 ?" vn = 8;
( y7 b* x  ?, A/ ~chess = zeros(1, n);
for i = 1:n
) N3 _. E, N* `, g$ ?4 p    chess(i) = i;
end
5 a7 R. \5 U+ q% }$ t* P- j' q% n8 c
这初始化了一个带有皇后的第一行的棋盘。
: r, \3 h4 y! ]$ O/ Zmain = zeros(1, 2 * n - 1); % 记录主对角线的使用情况
! L: W" |" R6 _6 V. Z9 v9 gdeputy = zeros(1, 2 * n - 1); % 记录副对角线的使用情况
; s7 P2 j: Y& [' Q0 [2 enumber = 0;
5 L2 R6 t! Y7 b  H0 T3 E0 g[chess, main, deputy, number] = justtry(1, n, chess, main, deputy, number);

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


8 s9 [4 t4 ]9 [6 Y! Y2 P4 Z2 Y0 l