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

2744557306

这是一个MATLAB实现的N皇后问题，这是一个经典的组合问题。其目标是在一个N×N的棋盘上放置N个皇后，使得它们之间互不攻击。提供的代码使用了递归回溯的方法来找到N皇后问题的所有解决方案。
6 I! B$ n/ i% o1 t+ Z- K让我们逐步解释这段代码：
% A$ D/ Z0 \5 r1 F# W. K6 efunction [chess, main, deputy, number] = justtry(i, n, chess, main, deputy, number)
# S, g/ e. y* ~
这定义了一个名为justtry的函数，它接受六个参数：当前行数i，棋盘大小n，当前皇后的排列chess，主对角线和副对角线的状态（main和deputy），以及解的数量number。
# b, E. A6 C0 x3 }' g! rif i == 9
, C8 F# S/ C: N9 E+ k; ?& ]. k) W    number = number + 1;
, r8 E! O: a9 B1 W  v    chess
else
    for k = i:8
, C7 B( T+ W% r2 t; w$ R# T2 \        if main(i - chess(k) + n) == 0 && deputy(i + chess(k) - 1) == 0
: h) u2 r/ q. D+ g
这检查是否已经到达第9行。如果是这样，它会递增解的数量(number)并显示当前皇后在棋盘上的排列。否则，它进入一个从当前行(i)到8的循环。
. b. L3 Z7 I2 D) ~嵌套的if语句检查当前棋盘位置是否有效（即没有皇后互相威胁）。如果条件满足，它将继续放置皇后。
            t = chess(k); % 交换位置
            chess(k) = chess(i);
            chess(i) = t;

7 P2 b) T; ~5 U3 p4 d' w9 K            main(i - chess(k) + n) = 1;
            deputy(i + chess(k) - 1) = 1;

. g: u* ]( g* J            [chess, main, deputy, number] = justtry(i + 1, n, chess, main, deputy, number); % 递归调用
* ^5 V/ m7 }8 W* {5 P( V+ ?
            t = chess(k); % 回溯
            chess(k) = chess(i);
9 m2 x8 {7 R' `* ]0 I, h            chess(i) = t;
% |+ F+ {' v  h5 }
1 d4 F" K0 V( u0 B# w  L            main(i - chess(k) + n) = 0;
$ w3 ]; L/ ^: i. E: C& w            deputy(i + chess(k) - 1) = 0;

5 V* z+ Z1 s6 A+ L+ i这部分是回溯算法的核心。它交换皇后的位置，更新对角线的状态，对下一行进行递归调用，然后通过恢复原始状态进行回溯。
        end
    end
0 N, F( `" y; d! s! Z4 F( jend

这结束了循环和函数。如果i不是9，循环将继续到下一行。
clear all
6 \' ~5 n6 A! ]1 _# V; J7 l5 l+ Mclc
3 P+ H! T5 a  I3 L. t* s  |
这些命令清除工作区和命令窗口。
! q( s" \& \$ G/ V/ an = 8;
6 F! R/ G# O7 l! [+ |chess = zeros(1, n);
for i = 1:n
    chess(i) = i;
end
9 N- P7 h# k; Y; V; o
6 t* X9 E8 X5 u1 K& d8 r+ {- b这初始化了一个带有皇后的第一行的棋盘。
- i; U% `% y) z5 m9 L3 l( {6 fmain = zeros(1, 2 * n - 1); % 记录主对角线的使用情况
" a8 V; i" ^" B# N- c* _deputy = zeros(1, 2 * n - 1); % 记录副对角线的使用情况
number = 0;
[chess, main, deputy, number] = justtry(1, n, chess, main, deputy, number);

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

: G% J$ b& a6 f( C* C( c