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

2744557306

这是一个MATLAB实现的N皇后问题，这是一个经典的组合问题。其目标是在一个N×N的棋盘上放置N个皇后，使得它们之间互不攻击。提供的代码使用了递归回溯的方法来找到N皇后问题的所有解决方案。
  D6 p( d! W; z+ N$ ?1 ~; }让我们逐步解释这段代码：
function [chess, main, deputy, number] = justtry(i, n, chess, main, deputy, number)
9 d: j! w+ u4 s  @' M5 P3 o
这定义了一个名为justtry的函数，它接受六个参数：当前行数i，棋盘大小n，当前皇后的排列chess，主对角线和副对角线的状态（main和deputy），以及解的数量number。
: K1 `; P) ]* {7 pif i == 9
! M0 R7 {* K) b$ Q1 p    number = number + 1;
' G6 J3 K: v% ^- V" C    chess
" E! I) u; E; |. h( aelse
    for k = i:8
- b- i/ F1 d% ]        if main(i - chess(k) + n) == 0 && deputy(i + chess(k) - 1) == 0

这检查是否已经到达第9行。如果是这样，它会递增解的数量(number)并显示当前皇后在棋盘上的排列。否则，它进入一个从当前行(i)到8的循环。
嵌套的if语句检查当前棋盘位置是否有效（即没有皇后互相威胁）。如果条件满足，它将继续放置皇后。
- j0 ^! E8 r* _8 E! y+ b            t = chess(k); % 交换位置
            chess(k) = chess(i);
# O$ O& q* z- Y- e/ g& A( \            chess(i) = t;

" v# [8 ~8 G/ s: l7 d7 l4 o0 ?  H            main(i - chess(k) + n) = 1;
9 }2 H( p/ f. X3 X, Q            deputy(i + chess(k) - 1) = 1;
  ^( I3 e" [3 k' Q) T8 B, x  T
% e! f' n4 N  N" }! K+ l            [chess, main, deputy, number] = justtry(i + 1, n, chess, main, deputy, number); % 递归调用
' i% P: y4 V# X$ H; w2 X- C, |
            t = chess(k); % 回溯
( U" n# D' t( S2 C; P) R! w            chess(k) = chess(i);
- a7 W+ M( q3 j( y8 B            chess(i) = t;
" n; Z9 p' s4 ^6 E$ ^- k  P: R
" E$ k+ o/ F' r& ^$ ~5 E( M5 k            main(i - chess(k) + n) = 0;
            deputy(i + chess(k) - 1) = 0;
$ h' I1 m" W7 C/ I+ n! y+ k
这部分是回溯算法的核心。它交换皇后的位置，更新对角线的状态，对下一行进行递归调用，然后通过恢复原始状态进行回溯。
; O+ I0 M: l; ?: o* o        end
    end
) m6 T, |9 y3 [" J# Uend

, b  J% _" ~- B9 a! A. V这结束了循环和函数。如果i不是9，循环将继续到下一行。
% ^( }1 u; s# ]6 I5 F  oclear all
clc

这些命令清除工作区和命令窗口。
n = 8;
chess = zeros(1, n);
for i = 1:n
    chess(i) = i;
end

这初始化了一个带有皇后的第一行的棋盘。
main = zeros(1, 2 * n - 1); % 记录主对角线的使用情况
deputy = zeros(1, 2 * n - 1); % 记录副对角线的使用情况
3 X7 r. u0 Z6 x. H0 q' \& Bnumber = 0;
[chess, main, deputy, number] = justtry(1, n, chess, main, deputy, number);
% b% i/ j7 G* Z
这初始化了数组以跟踪主对角线和副对角线的情况，并通过调用justtry开始了递归回溯。整个过程将探索在8x8棋盘上所有可能的皇后排列，并打印每个有效排列以及解的总数。
4 ?* j& t' ?: A1 f& |/ u  K* ]+ S
" ?9 H: D- M% o