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

2744557306

这是一个MATLAB实现的N皇后问题，这是一个经典的组合问题。其目标是在一个N×N的棋盘上放置N个皇后，使得它们之间互不攻击。提供的代码使用了递归回溯的方法来找到N皇后问题的所有解决方案。
0 c& S- b/ @' H2 W4 A让我们逐步解释这段代码：
) z( `/ T0 {* A' b4 X/ k8 l) {function [chess, main, deputy, number] = justtry(i, n, chess, main, deputy, number)
7 g& \$ i  a: N$ R, ~
这定义了一个名为justtry的函数，它接受六个参数：当前行数i，棋盘大小n，当前皇后的排列chess，主对角线和副对角线的状态（main和deputy），以及解的数量number。
if i == 9
    number = number + 1;
    chess
else
    for k = i:8
3 t2 D, E1 C" V2 p        if main(i - chess(k) + n) == 0 && deputy(i + chess(k) - 1) == 0

这检查是否已经到达第9行。如果是这样，它会递增解的数量(number)并显示当前皇后在棋盘上的排列。否则，它进入一个从当前行(i)到8的循环。
7 o3 ], H  U0 K1 Z8 `- B. P嵌套的if语句检查当前棋盘位置是否有效（即没有皇后互相威胁）。如果条件满足，它将继续放置皇后。
            t = chess(k); % 交换位置
& I4 v7 ~! b; X: q            chess(k) = chess(i);
            chess(i) = t;

, N+ g( m1 w4 `0 w- s            main(i - chess(k) + n) = 1;
$ l9 Q! f. u7 U# x            deputy(i + chess(k) - 1) = 1;
) Z6 x- S1 R3 N8 O4 L3 E/ F+ {
; ?  D% [/ ?& Z( Y  z$ T1 L            [chess, main, deputy, number] = justtry(i + 1, n, chess, main, deputy, number); % 递归调用
/ |& M# _0 v# Y5 }
  N7 s. U7 h6 Z% K  u            t = chess(k); % 回溯
6 O0 n1 W6 ]8 q% k8 a; P9 n; m            chess(k) = chess(i);
            chess(i) = t;

4 y( W1 \$ F! \+ n, V0 }            main(i - chess(k) + n) = 0;
+ h8 C* b$ L9 p+ e/ d) @5 }            deputy(i + chess(k) - 1) = 0;

这部分是回溯算法的核心。它交换皇后的位置，更新对角线的状态，对下一行进行递归调用，然后通过恢复原始状态进行回溯。
        end
    end
  G6 O  z. x% P- E3 T4 W' Tend

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

这些命令清除工作区和命令窗口。
+ _' ~' L( i7 o# ]8 bn = 8;
+ O& d5 k5 e: _chess = zeros(1, n);
for i = 1:n
    chess(i) = i;
end

这初始化了一个带有皇后的第一行的棋盘。
main = zeros(1, 2 * n - 1); % 记录主对角线的使用情况
deputy = zeros(1, 2 * n - 1); % 记录副对角线的使用情况
number = 0;
[chess, main, deputy, number] = justtry(1, n, chess, main, deputy, number);
4 q' I7 t7 a) n7 r5 C/ g% ~
8 D2 `) d# J% X0 q" p1 K) |这初始化了数组以跟踪主对角线和副对角线的情况，并通过调用justtry开始了递归回溯。整个过程将探索在8x8棋盘上所有可能的皇后排列，并打印每个有效排列以及解的总数。
/ t. q2 X4 q, ^- O0 g
3 c; P% V/ R+ |2 m/ Y( P4 K