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

2744557306

这是一个MATLAB实现的N皇后问题，这是一个经典的组合问题。其目标是在一个N×N的棋盘上放置N个皇后，使得它们之间互不攻击。提供的代码使用了递归回溯的方法来找到N皇后问题的所有解决方案。
让我们逐步解释这段代码：
function [chess, main, deputy, number] = justtry(i, n, chess, main, deputy, number)
# Y) ~" U5 H; [
6 T, A9 u9 ]2 Q% I4 O这定义了一个名为justtry的函数，它接受六个参数：当前行数i，棋盘大小n，当前皇后的排列chess，主对角线和副对角线的状态（main和deputy），以及解的数量number。
& f. V& I+ I/ S3 rif i == 9
' W+ ^" y/ M: S9 G" z    number = number + 1;
; w  z0 Z6 Q, X( z* j) y4 r+ D    chess
1 _% G7 z( ]% Ielse
. D; g6 A/ B2 |% q$ w* u+ k    for k = i:8
8 R9 z* ^# L5 t  V  u) }# B        if main(i - chess(k) + n) == 0 && deputy(i + chess(k) - 1) == 0
  z$ ?& x- L, h
, Y, z) `; k2 }7 F# x这检查是否已经到达第9行。如果是这样，它会递增解的数量(number)并显示当前皇后在棋盘上的排列。否则，它进入一个从当前行(i)到8的循环。
嵌套的if语句检查当前棋盘位置是否有效（即没有皇后互相威胁）。如果条件满足，它将继续放置皇后。
9 a4 U$ J# ~* g' W. [            t = chess(k); % 交换位置
' Z2 Z  }+ s, f" p            chess(k) = chess(i);
            chess(i) = t;

7 b" c5 ~* u7 G8 i4 z7 f0 o            main(i - chess(k) + n) = 1;
; E/ u9 u, r. }- Q1 ^0 q9 W& E            deputy(i + chess(k) - 1) = 1;

            [chess, main, deputy, number] = justtry(i + 1, n, chess, main, deputy, number); % 递归调用

            t = chess(k); % 回溯
            chess(k) = chess(i);
            chess(i) = t;
$ `. \. m/ l: E3 e& _- l2 l% n
            main(i - chess(k) + n) = 0;
            deputy(i + chess(k) - 1) = 0;

: _, E8 t4 f6 U9 S这部分是回溯算法的核心。它交换皇后的位置，更新对角线的状态，对下一行进行递归调用，然后通过恢复原始状态进行回溯。
$ Q+ X+ z" q" H$ p. H        end
  z1 C  T+ A6 @( U5 u! B! V    end
) g$ x3 p/ Q- lend

3 k* B  V5 H: O( D8 ?: g这结束了循环和函数。如果i不是9，循环将继续到下一行。
4 y; G. Q0 X5 U$ A1 ~clear all
( {/ J: f* U" h" e) ]7 O- `clc

5 i! ]3 a" A/ H: g9 r: u这些命令清除工作区和命令窗口。
$ f7 B% H. [" Z9 ?+ [2 ]n = 8;
, U  i, e& U1 z; Schess = zeros(1, n);
for i = 1:n
+ T( Z. D. Q8 l. ^8 Y# r    chess(i) = i;
5 i9 u  q  u  ]( S: Qend
) ~9 |8 D  C2 x5 b. g
7 @5 |! L2 U* _/ p% \' B* i. q这初始化了一个带有皇后的第一行的棋盘。
main = zeros(1, 2 * n - 1); % 记录主对角线的使用情况
deputy = zeros(1, 2 * n - 1); % 记录副对角线的使用情况
* c* C; M' R6 K; H: Z6 f' ~2 M  Wnumber = 0;
1 [5 y$ [# ^3 O8 |[chess, main, deputy, number] = justtry(1, n, chess, main, deputy, number);
) C" b3 ]7 s* T
这初始化了数组以跟踪主对角线和副对角线的情况，并通过调用justtry开始了递归回溯。整个过程将探索在8x8棋盘上所有可能的皇后排列，并打印每个有效排列以及解的总数。