数学建模社区-数学中国

标题: 排列树的回溯搜索解决n皇后问题 [打印本页]
作者: 2744557306    时间: 2023-12-22 16:52
标题: 排列树的回溯搜索解决n皇后问题
这是一个MATLAB实现的N皇后问题，这是一个经典的组合问题。其目标是在一个N×N的棋盘上放置N个皇后，使得它们之间互不攻击。提供的代码使用了递归回溯的方法来找到N皇后问题的所有解决方案。
$ ^; f0 l6 D  u0 S9 Q让我们逐步解释这段代码：
4 j9 K$ V3 w* v1 r3 z, }6 pfunction [chess, main, deputy, number] = justtry(i, n, chess, main, deputy, number)
' V" p9 O+ t7 ^! ~8 _! T$ H
2 |1 v; g( w) O; f- Q+ Y5 D) Q这定义了一个名为justtry的函数，它接受六个参数：当前行数i，棋盘大小n，当前皇后的排列chess，主对角线和副对角线的状态（main和deputy），以及解的数量number。
2 e( j+ I. W4 [1 r. x: ?" n4 Tif i == 9& N/ A  g1 s7 i0 v
    number = number + 1;0 q; w) F1 [( Z1 b  m& M3 `
    chess. K. ?8 U& ]6 v; D
else
. T$ i0 I1 P8 l! J. k    for k = i:8
  c% {: L" a4 z7 T6 L- \        if main(i - chess(k) + n) == 0 && deputy(i + chess(k) - 1) == 0
0 Z3 {% o1 O" {6 I! ~' @5 k
! H; k4 G/ H& ^9 R* }8 N这检查是否已经到达第9行。如果是这样，它会递增解的数量(number)并显示当前皇后在棋盘上的排列。否则，它进入一个从当前行(i)到8的循环。
' M9 M0 B  {! R; n. w, J8 z嵌套的if语句检查当前棋盘位置是否有效（即没有皇后互相威胁）。如果条件满足，它将继续放置皇后。
2 p* V( P7 }, j: E            t = chess(k); % 交换位置! L1 k5 ^" ?# z4 }
            chess(k) = chess(i);/ J8 T: ~5 g- p8 g
            chess(i) = t;; b8 b8 `: O. F8 S
* |. m5 }" I. D# }! e
            main(i - chess(k) + n) = 1;
; X6 S) W, q  R* ~            deputy(i + chess(k) - 1) = 1;
8 g0 E4 E1 q7 e& V0 j3 t2 M
& ]$ ?) `0 v, o' I. ^6 C; q            [chess, main, deputy, number] = justtry(i + 1, n, chess, main, deputy, number); % 递归调用8 H9 o7 L' L! F8 j* G& y* e
7 Y' @7 c" x2 E/ G2 A0 T6 T8 Z% B$ n
            t = chess(k); % 回溯" v" v& u+ Z' v, o7 M7 S" h" z& Y
            chess(k) = chess(i);; D* T- A7 G: X+ j% s. d
            chess(i) = t;* y, V( i4 l* j0 }

8 T2 V7 y$ [* V4 Y7 t* ~            main(i - chess(k) + n) = 0;
6 s, ?; F8 M9 V" f$ {            deputy(i + chess(k) - 1) = 0;
6 v0 a+ q  }+ N; v3 J7 A- A' l- q" A: O( ?: `
这部分是回溯算法的核心。它交换皇后的位置，更新对角线的状态，对下一行进行递归调用，然后通过恢复原始状态进行回溯。$ t3 M" J$ T+ P5 K' y0 C
        end
7 _. c9 H4 L4 B, U    end
$ V' s+ G4 z( T0 c2 uend. f- u7 W- a& I( l
& J& r7 ^  K0 C$ m* y$ @4 P. g
这结束了循环和函数。如果i不是9，循环将继续到下一行。% |5 j1 b3 S7 n2 L
clear all( i6 |' p2 _* M: O
clc
' F* ]& A  e+ @' }1 Z
( Y* c& ]2 ]: _" t) k+ Z这些命令清除工作区和命令窗口。
" S1 P7 v% ]+ ~n = 8;: {8 U' S  N$ Z; p$ m+ r
chess = zeros(1, n);
0 c( W3 U/ ?+ g4 ?for i = 1:n
( {; K% V; ^# Q3 f+ w/ ~2 G    chess(i) = i;& R9 K" s* \: U4 A
end
) N! f; {3 R! E& c. ~: J' E2 ^2 y7 y$ }- b0 D8 }
这初始化了一个带有皇后的第一行的棋盘。
9 D; m  L# Q; m! I4 q2 Fmain = zeros(1, 2 * n - 1); % 记录主对角线的使用情况
3 ~& l0 w: n4 fdeputy = zeros(1, 2 * n - 1); % 记录副对角线的使用情况
$ U0 h# g" U! s, p& D7 I/ p$ u  ~number = 0;
& p& n5 n' j, O, Z[chess, main, deputy, number] = justtry(1, n, chess, main, deputy, number);
2 |# g0 h- o: [4 z" c! _8 ?8 N" `
/ M' p' Y1 {1 J" g  ~7 D这初始化了数组以跟踪主对角线和副对角线的情况，并通过调用justtry开始了递归回溯。整个过程将探索在8x8棋盘上所有可能的皇后排列，并打印每个有效排列以及解的总数。
; M! L4 F: q' \+ {' |1 ?* V
% j3 n! P) ^& R/ c0 |
- l" c. h  s, Z& }# g
3 L, K' y$ w! P* C

排列树的回溯搜索.rar

694 Bytes, 下载次数: 0, 下载积分: 体力 -2 点

售价: 2 点体力  [记录]  [购买]





欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5