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

2744557306

这是一个MATLAB实现的N皇后问题，这是一个经典的组合问题。其目标是在一个N×N的棋盘上放置N个皇后，使得它们之间互不攻击。提供的代码使用了递归回溯的方法来找到N皇后问题的所有解决方案。
让我们逐步解释这段代码：
  }- F$ w4 H- w: `, t+ r4 lfunction [chess, main, deputy, number] = justtry(i, n, chess, main, deputy, number)
( a( h2 A' ^0 V; x: }
# J4 [* X) N0 A* O  b' M这定义了一个名为justtry的函数，它接受六个参数：当前行数i，棋盘大小n，当前皇后的排列chess，主对角线和副对角线的状态（main和deputy），以及解的数量number。
- o8 [+ o8 @9 S; y( jif i == 9
1 s" c% L8 R& `2 H! U9 E7 n" U    number = number + 1;
$ y. f. a/ @- i' N4 R    chess
else
6 z9 U) A1 X+ j- c0 |% S* _+ H    for k = i:8
7 b6 x  p: J3 Z% X2 [9 [' S: O* a        if main(i - chess(k) + n) == 0 && deputy(i + chess(k) - 1) == 0
* u% k5 q7 d/ n$ n, x  ]
这检查是否已经到达第9行。如果是这样，它会递增解的数量(number)并显示当前皇后在棋盘上的排列。否则，它进入一个从当前行(i)到8的循环。
" L2 n: ~6 w) U1 h  {9 m  {嵌套的if语句检查当前棋盘位置是否有效（即没有皇后互相威胁）。如果条件满足，它将继续放置皇后。
            t = chess(k); % 交换位置
  i) e$ B, U9 R4 W3 m            chess(k) = chess(i);
7 R; s' C& s: R6 D! o/ s* {            chess(i) = t;
) M' |- ^4 y! f+ m
2 N; v7 ]- K5 u1 t( g$ m4 m            main(i - chess(k) + n) = 1;
1 i! g( g) n5 @  {' S            deputy(i + chess(k) - 1) = 1;
+ v5 s4 _8 ]- J  k1 \
2 O) I7 S& R; U0 }  F. `            [chess, main, deputy, number] = justtry(i + 1, n, chess, main, deputy, number); % 递归调用

            t = chess(k); % 回溯
            chess(k) = chess(i);
            chess(i) = t;

            main(i - chess(k) + n) = 0;
            deputy(i + chess(k) - 1) = 0;

这部分是回溯算法的核心。它交换皇后的位置，更新对角线的状态，对下一行进行递归调用，然后通过恢复原始状态进行回溯。
: n6 \, d7 X2 m        end
) |$ p* v. ~' [$ l    end
4 e) v3 B3 n7 o; b, I% T6 xend
: T; \4 t" C5 K$ ^3 D9 u# d
这结束了循环和函数。如果i不是9，循环将继续到下一行。
clear all
; A/ G! K2 s8 h. {" |clc

: M! ~3 H* w* U9 ]; l这些命令清除工作区和命令窗口。
) y4 e& k; L( l7 N5 ?n = 8;
- s& N4 N' k6 X9 z5 N7 z, [5 ichess = zeros(1, n);
for i = 1:n
6 y" F& M# L- f5 c7 ^3 y    chess(i) = i;
end

这初始化了一个带有皇后的第一行的棋盘。
; V; K* j/ |1 S4 V0 _- E( Mmain = zeros(1, 2 * n - 1); % 记录主对角线的使用情况
deputy = zeros(1, 2 * n - 1); % 记录副对角线的使用情况
number = 0;
" o. t" f2 t0 a[chess, main, deputy, number] = justtry(1, n, chess, main, deputy, number);
: `# ^( W4 M6 S# G! h
) g$ F6 Q0 L9 ^# b& Q这初始化了数组以跟踪主对角线和副对角线的情况，并通过调用justtry开始了递归回溯。整个过程将探索在8x8棋盘上所有可能的皇后排列，并打印每个有效排列以及解的总数。


$ A& M: F) i( W1 x1 @9 l* M4 ?