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

2744557306

这是一个MATLAB实现的N皇后问题，这是一个经典的组合问题。其目标是在一个N×N的棋盘上放置N个皇后，使得它们之间互不攻击。提供的代码使用了递归回溯的方法来找到N皇后问题的所有解决方案。
让我们逐步解释这段代码：
function [chess, main, deputy, number] = justtry(i, n, chess, main, deputy, number)
% G) c" t# J* v- j: h+ `
( b  D7 s; ?- @, m7 _, N: f这定义了一个名为justtry的函数，它接受六个参数：当前行数i，棋盘大小n，当前皇后的排列chess，主对角线和副对角线的状态（main和deputy），以及解的数量number。
if i == 9
    number = number + 1;
9 S9 L6 @' J. h    chess
else
! E5 P9 L, f8 B1 F4 Y2 q" e. ~3 K    for k = i:8
4 P- {" M% K& @; g$ x        if main(i - chess(k) + n) == 0 && deputy(i + chess(k) - 1) == 0
. n+ k% q0 W' R9 O
8 l' a2 C3 c5 v- u9 I这检查是否已经到达第9行。如果是这样，它会递增解的数量(number)并显示当前皇后在棋盘上的排列。否则，它进入一个从当前行(i)到8的循环。
嵌套的if语句检查当前棋盘位置是否有效（即没有皇后互相威胁）。如果条件满足，它将继续放置皇后。
            t = chess(k); % 交换位置
& ]; ], N* x# J( y- Q4 l            chess(k) = chess(i);
            chess(i) = t;
: c$ X, C, z9 M1 b3 {) L- r
; N0 h  I( H6 r( f! A8 R6 T* ]            main(i - chess(k) + n) = 1;
            deputy(i + chess(k) - 1) = 1;
9 _+ ^1 Q* U# Q; ^3 b% M
            [chess, main, deputy, number] = justtry(i + 1, n, chess, main, deputy, number); % 递归调用

* M6 A$ K. N3 t0 G# e# y; h            t = chess(k); % 回溯
            chess(k) = chess(i);
            chess(i) = t;
- t& _- l0 |9 f  C# p/ j
            main(i - chess(k) + n) = 0;
            deputy(i + chess(k) - 1) = 0;
6 J5 v( n% J" d: k7 Q+ u" _
, X5 R+ g) `. Z$ W这部分是回溯算法的核心。它交换皇后的位置，更新对角线的状态，对下一行进行递归调用，然后通过恢复原始状态进行回溯。
        end
) ^  A2 u3 X+ }0 ^" t: |    end
7 U3 Z+ ^: z7 X* }end
1 [5 f0 N7 ^  i' d9 @' Z
这结束了循环和函数。如果i不是9，循环将继续到下一行。
clear all
4 R  p- M0 Y% |* Y4 Jclc
3 F, t( I$ t% g1 A6 i& i0 J
这些命令清除工作区和命令窗口。
5 a9 ^6 O3 {, e4 I( X& I+ wn = 8;
chess = zeros(1, n);
for i = 1:n
    chess(i) = i;
end
; n& [% r& b7 E) h8 W" R
5 _$ W7 s9 I/ P) n& [% S这初始化了一个带有皇后的第一行的棋盘。
8 d8 \9 [' O+ V7 Ymain = zeros(1, 2 * n - 1); % 记录主对角线的使用情况
deputy = zeros(1, 2 * n - 1); % 记录副对角线的使用情况
2 |; X+ N3 }. L" O; e, tnumber = 0;
2 G9 G8 u# Z6 _4 O# d3 q[chess, main, deputy, number] = justtry(1, n, chess, main, deputy, number);
% a& [; Z! O+ E6 f6 I, m
2 S# p" n* }" E这初始化了数组以跟踪主对角线和副对角线的情况，并通过调用justtry开始了递归回溯。整个过程将探索在8x8棋盘上所有可能的皇后排列，并打印每个有效排列以及解的总数。


; o/ ?' _. ?; g4 z