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

2744557306

这是一个MATLAB实现的N皇后问题，这是一个经典的组合问题。其目标是在一个N×N的棋盘上放置N个皇后，使得它们之间互不攻击。提供的代码使用了递归回溯的方法来找到N皇后问题的所有解决方案。
让我们逐步解释这段代码：
function [chess, main, deputy, number] = justtry(i, n, chess, main, deputy, number)
1 x9 J) W6 Z5 n/ p1 M) c
; n4 p% }7 x. k' a这定义了一个名为justtry的函数，它接受六个参数：当前行数i，棋盘大小n，当前皇后的排列chess，主对角线和副对角线的状态（main和deputy），以及解的数量number。
if i == 9
. B2 ?3 x" h4 o7 f    number = number + 1;
- e# q0 r4 D) e    chess
else
    for k = i:8
% j9 i- t2 [: B! G4 }0 N        if main(i - chess(k) + n) == 0 && deputy(i + chess(k) - 1) == 0
  Q8 Q. @# v/ j! Z# U3 V5 g! d
这检查是否已经到达第9行。如果是这样，它会递增解的数量(number)并显示当前皇后在棋盘上的排列。否则，它进入一个从当前行(i)到8的循环。
; |- \4 d- W# l0 k* g' C1 t嵌套的if语句检查当前棋盘位置是否有效（即没有皇后互相威胁）。如果条件满足，它将继续放置皇后。
            t = chess(k); % 交换位置
            chess(k) = chess(i);
            chess(i) = t;

            main(i - chess(k) + n) = 1;
            deputy(i + chess(k) - 1) = 1;
# W; f1 d3 I$ C: s6 i8 _8 q
( ~& T2 R, Z0 Y3 t6 ?  R            [chess, main, deputy, number] = justtry(i + 1, n, chess, main, deputy, number); % 递归调用
6 G( P! L% z8 r6 q9 M" r0 b
            t = chess(k); % 回溯
            chess(k) = chess(i);
            chess(i) = t;
8 L3 e+ M2 t" x4 e2 t4 m' r
            main(i - chess(k) + n) = 0;
) c5 D' w" B0 P! b' [) Z- E            deputy(i + chess(k) - 1) = 0;
( Y6 C4 g6 \1 Z% t: h/ K9 P( E; D
这部分是回溯算法的核心。它交换皇后的位置，更新对角线的状态，对下一行进行递归调用，然后通过恢复原始状态进行回溯。
        end
+ v. E. F+ D  b/ O    end
end

, Y# G7 k, R) @! B这结束了循环和函数。如果i不是9，循环将继续到下一行。
clear all
clc

这些命令清除工作区和命令窗口。
5 ?- G: T- r4 l& Ln = 8;
chess = zeros(1, n);
6 v: p* ^  f1 j$ M, c2 o* k  y# U2 gfor i = 1:n
- A1 M' j) e! m( K4 R: r    chess(i) = i;
end

这初始化了一个带有皇后的第一行的棋盘。
- T" N. \  C- y5 A3 h& v4 v% Nmain = zeros(1, 2 * n - 1); % 记录主对角线的使用情况
3 N6 T  }# O( kdeputy = zeros(1, 2 * n - 1); % 记录副对角线的使用情况
number = 0;
[chess, main, deputy, number] = justtry(1, n, chess, main, deputy, number);

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

6 q. C5 z6 `# I2 _* Y4 B
6 r% f% Z  V* V9 a" |5 V4 Q