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

2744557306

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

这定义了一个名为justtry的函数，它接受六个参数：当前行数i，棋盘大小n，当前皇后的排列chess，主对角线和副对角线的状态（main和deputy），以及解的数量number。
if i == 9
    number = number + 1;
) t1 f# g- G& x- I7 b    chess
else
    for k = i:8
        if main(i - chess(k) + n) == 0 && deputy(i + chess(k) - 1) == 0

这检查是否已经到达第9行。如果是这样，它会递增解的数量(number)并显示当前皇后在棋盘上的排列。否则，它进入一个从当前行(i)到8的循环。
. t6 @6 H! w* `% a8 s嵌套的if语句检查当前棋盘位置是否有效（即没有皇后互相威胁）。如果条件满足，它将继续放置皇后。
# [6 B7 u1 ~4 w% G# d            t = chess(k); % 交换位置
' p  _" q6 ^: Y$ L            chess(k) = chess(i);
            chess(i) = t;

/ P% h5 S3 M) a            main(i - chess(k) + n) = 1;
            deputy(i + chess(k) - 1) = 1;

' `8 z: e) p( F) X4 x" q            [chess, main, deputy, number] = justtry(i + 1, n, chess, main, deputy, number); % 递归调用

            t = chess(k); % 回溯
. c& D# [# S1 u            chess(k) = chess(i);
- f2 d- j  S$ b% H' N" _            chess(i) = t;
; H  `3 V& W  f$ W! m
7 R1 D7 K2 V# o+ r( _& W            main(i - chess(k) + n) = 0;
            deputy(i + chess(k) - 1) = 0;
$ ~) w% l4 r% i3 N- f7 {+ s
这部分是回溯算法的核心。它交换皇后的位置，更新对角线的状态，对下一行进行递归调用，然后通过恢复原始状态进行回溯。
        end
    end
end
" a) \6 b  r- O/ O
这结束了循环和函数。如果i不是9，循环将继续到下一行。
clear all
clc

这些命令清除工作区和命令窗口。
n = 8;
. o2 w7 O0 a3 f! E4 u& @; n* Zchess = zeros(1, n);
for i = 1:n
    chess(i) = i;
) Z1 \+ ?0 y' s8 O4 w+ Y' L* {; Gend
9 i+ P' g& P! M0 m0 ~! P
这初始化了一个带有皇后的第一行的棋盘。
! P% }  N0 ]0 l$ S  F- \main = zeros(1, 2 * n - 1); % 记录主对角线的使用情况
( X+ z- E' s; s" S, ^1 kdeputy = zeros(1, 2 * n - 1); % 记录副对角线的使用情况
& D* K1 v9 K! t! R$ Snumber = 0;
+ B) N9 _( d, a" w  k+ V/ t0 q[chess, main, deputy, number] = justtry(1, n, chess, main, deputy, number);
$ _9 s' A7 f1 C3 f3 ~! t5 T
这初始化了数组以跟踪主对角线和副对角线的情况，并通过调用justtry开始了递归回溯。整个过程将探索在8x8棋盘上所有可能的皇后排列，并打印每个有效排列以及解的总数。
3 D4 E) g6 q0 t  D6 b! B$ S
5 r2 n6 t" p$ f# i  x) D
. F1 ]' k5 ?5 y