数学建模社区-数学中国
标题:
排列树的回溯搜索解决n皇后问题
[打印本页]
作者:
2744557306
时间:
2023-12-22 16:52
标题:
排列树的回溯搜索解决n皇后问题
这是一个MATLAB实现的N皇后问题，这是一个经典的组合问题。其目标是在一个N×N的棋盘上放置N个皇后，使得它们之间互不攻击。提供的代码使用了递归回溯的方法来找到N皇后问题的所有解决方案。
- ^2 S- b- M9 [& w" ^
让我们逐步解释这段代码：
3 O; b; |7 C8 U* e% A
function [chess, main, deputy, number] = justtry(i, n, chess, main, deputy, number)
z) {: Q+ g) w( {) g
~; {9 b, G9 e- _& N5 Z
这定义了一个名为justtry的函数，它接受六个参数：当前行数i，棋盘大小n，当前皇后的排列chess，主对角线和副对角线的状态（main和deputy），以及解的数量number。
) K; W# N- A E% f* c$ e
if i == 9
0 i& I* I' r) z4 r6 |
number = number + 1;
5 w6 Q4 S( r4 T% r
chess
& ?6 T( P9 Z7 M+ |( b3 T# [
else
. b" G! K$ z6 k8 o7 W$ W! X
for k = i:8
/ N6 Y+ m) |7 s
if main(i - chess(k) + n) == 0 && deputy(i + chess(k) - 1) == 0
! ]. V3 O3 {2 ]
+ e' R, y, E6 [0 p
这检查是否已经到达第9行。如果是这样，它会递增解的数量(number)并显示当前皇后在棋盘上的排列。否则，它进入一个从当前行(i)到8的循环。
" k; j! G g4 Y8 a
嵌套的if语句检查当前棋盘位置是否有效（即没有皇后互相威胁）。如果条件满足，它将继续放置皇后。
: r! Y% n+ w- q, C3 e
t = chess(k); % 交换位置
- E3 z9 \5 j8 f* \. k
chess(k) = chess(i);
2 N5 Y/ z0 S; [* w s. B
chess(i) = t;
* X4 Q: }5 ]. B9 M: c: [# l4 Q
# ~7 C2 g* p9 j6 p) Y; [& I
main(i - chess(k) + n) = 1;
# ]( E0 k' ?+ W# w' S
deputy(i + chess(k) - 1) = 1;
2 W3 h* p" h5 o: {! \: b
7 A6 @& c- O( i# Y. M
[chess, main, deputy, number] = justtry(i + 1, n, chess, main, deputy, number); % 递归调用
# B" |9 L! p c& G- M: L
/ G1 `+ |; R B, R0 `( Z, t
t = chess(k); % 回溯
, C' D. f) i+ D6 d5 f7 P
chess(k) = chess(i);
# }; l0 f* j6 B; e- Z6 r: ~9 p. T
chess(i) = t;
; @3 e& P1 j3 c2 _/ @
; t/ H. a- h/ ^
main(i - chess(k) + n) = 0;
3 B: w1 b ^% J
deputy(i + chess(k) - 1) = 0;
9 ?9 E) w' E2 B+ k* @# [ a0 U+ n
& c% @0 |8 N: L/ d" }
这部分是回溯算法的核心。它交换皇后的位置，更新对角线的状态，对下一行进行递归调用，然后通过恢复原始状态进行回溯。
. K7 o1 m. C2 [# j, z# Z% S6 i& b
end
8 e3 z, l$ D# ^5 T4 a3 j
end
7 I2 I/ o7 I4 M5 \5 B o# x
end
7 j) _7 ]; a' G* G* J
3 ]9 N$ r6 r; ^ n4 N* j/ Z2 D
这结束了循环和函数。如果i不是9，循环将继续到下一行。
% ` o5 a. i: p3 U
clear all
0 X! n4 r, s! g6 s0 F. Z1 K: P
clc
% f. |% i- {1 m& a: c0 R
8 l- \: a: H( ]# c& |7 |
这些命令清除工作区和命令窗口。
7 }7 |% ?' Z- t }8 S/ c
n = 8;
$ F. [0 x# H1 e' N) M+ d1 R8 f
chess = zeros(1, n);
$ N# F: q! @+ m% i; V. ?0 T
for i = 1:n
6 C) x! |" q- r. L/ O+ ~8 b7 @2 T
chess(i) = i;
: B+ P7 S( n& }; K; W l
end
* V$ R: {1 H1 F; b r9 ]5 U) m% q
/ [$ \1 g$ ]5 D) _1 y( \4 r
这初始化了一个带有皇后的第一行的棋盘。
9 ~3 R$ N- m! B1 u c# q7 L, j& ?
main = zeros(1, 2 * n - 1); % 记录主对角线的使用情况
% {) Y# \& ]( w9 R
deputy = zeros(1, 2 * n - 1); % 记录副对角线的使用情况
! M6 m7 d5 |) a. X
number = 0;
8 C1 t5 D2 O5 C! ~& W8 y" R, [
[chess, main, deputy, number] = justtry(1, n, chess, main, deputy, number);
) I, w4 X% ]5 d% c P' K) C" R
; ~( V8 r3 l% p* i
这初始化了数组以跟踪主对角线和副对角线的情况，并通过调用justtry开始了递归回溯。整个过程将探索在8x8棋盘上所有可能的皇后排列，并打印每个有效排列以及解的总数。
b" ]$ h1 a! W" X+ c9 i5 U( d% ^' p
5 d0 J; N$ K* t/ F" s8 O9 y
m# V4 O7 Z9 U6 H/ E+ V$ k& \
& `( W6 g8 s0 b9 L1 U, o9 e& S
排列树的回溯搜索.rar
2023-12-22 16:52 上传
点击文件名下载附件
下载积分: 体力 -2 点
694 Bytes, 下载次数: 0, 下载积分: 体力 -2 点
售价:
2 点体力
[
记录
] [
购买
]
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
