数学建模社区-数学中国
标题:
排列树的回溯搜索解决n皇后问题
[打印本页]
作者:
2744557306
时间:
2023-12-22 16:52
标题:
排列树的回溯搜索解决n皇后问题
这是一个MATLAB实现的N皇后问题，这是一个经典的组合问题。其目标是在一个N×N的棋盘上放置N个皇后，使得它们之间互不攻击。提供的代码使用了递归回溯的方法来找到N皇后问题的所有解决方案。
5 L- P- Z" V8 f. ~$ o8 ^5 G2 _
让我们逐步解释这段代码：
* B8 v7 \/ ~& ~6 k+ O$ [
function [chess, main, deputy, number] = justtry(i, n, chess, main, deputy, number)
4 X( _# h1 G5 x7 c/ d5 ^# a
( O- I5 P( A3 C7 S2 X7 ?
这定义了一个名为justtry的函数，它接受六个参数：当前行数i，棋盘大小n，当前皇后的排列chess，主对角线和副对角线的状态（main和deputy），以及解的数量number。
( c) ?$ f9 B' ?1 H
if i == 9
+ }3 [* S( g$ V: X$ }
number = number + 1;
: Z/ V6 p/ E1 M7 g/ C. K
chess
4 Q( ]. g3 Y9 @0 s$ q q
else
+ N! S2 a1 I- W* i' L
for k = i:8
" C" w/ E4 o/ c2 s- |; c1 j
if main(i - chess(k) + n) == 0 && deputy(i + chess(k) - 1) == 0
9 B8 p$ f) q! F
! z/ ^0 t1 k: q8 S
这检查是否已经到达第9行。如果是这样，它会递增解的数量(number)并显示当前皇后在棋盘上的排列。否则，它进入一个从当前行(i)到8的循环。
* s0 Y) V# o8 @6 `- R
嵌套的if语句检查当前棋盘位置是否有效（即没有皇后互相威胁）。如果条件满足，它将继续放置皇后。
" M- P6 O3 j& p/ B# j8 g
t = chess(k); % 交换位置
. s, F( W% ~+ R. ~% d
chess(k) = chess(i);
- Y$ L/ f0 x) L! S8 m" [: M
chess(i) = t;
( B6 Q) \1 ?5 a1 }* F' A; h
, J8 r+ r/ ?* r. Y t
main(i - chess(k) + n) = 1;
5 r: W. L7 x' A7 f) D) n0 y
deputy(i + chess(k) - 1) = 1;
2 g6 |6 z) @3 m K# m2 b+ C
# o! B( g0 r7 D; P
[chess, main, deputy, number] = justtry(i + 1, n, chess, main, deputy, number); % 递归调用
p4 g* L: G0 ^
0 B$ T. A9 L9 o% r* G8 S- [
t = chess(k); % 回溯
7 M4 C$ O- Z1 y/ d/ J1 h
chess(k) = chess(i);
. x v5 F$ a( X% Y9 }
chess(i) = t;
8 z6 J% ]+ Z+ p; X, ^
9 Z0 ~# s8 ]; ^
main(i - chess(k) + n) = 0;
' {7 R# u, k" v! d. x/ C+ `
deputy(i + chess(k) - 1) = 0;
2 R" X# Z' G! I" V: U% Z
) z3 @! d: b* E' f1 L, V
这部分是回溯算法的核心。它交换皇后的位置，更新对角线的状态，对下一行进行递归调用，然后通过恢复原始状态进行回溯。
) T: C! x5 _' ?, t. U Q+ ]
end
3 M2 }) u$ g6 x/ f
end
7 o0 H7 k. ~+ D( ^$ n
end
- ?, K x+ u2 H e
/ Z n) V F+ j X! P r) V
这结束了循环和函数。如果i不是9，循环将继续到下一行。
3 L2 f# ^+ s) b& {" l6 e
clear all
8 o% O0 d9 E8 x* X
clc
K+ u2 Y) F- f9 R
% S! j! R% Z0 f% k/ c1 w
这些命令清除工作区和命令窗口。
8 K1 q; h: ~9 `/ s% J! i8 }
n = 8;
) H S) ?( i% B+ M
chess = zeros(1, n);
; b7 P* I. p' B" y) `8 w) u( e
for i = 1:n
% P+ o& x* G- y& K" B0 v
chess(i) = i;
0 O5 _% |8 T: D: @9 @& |% n
end
7 g5 _( @0 n3 g
2 ?. d, i7 [0 ?- {' M" ?
这初始化了一个带有皇后的第一行的棋盘。
8 I1 R/ L o1 N7 @5 h0 `# Z9 X
main = zeros(1, 2 * n - 1); % 记录主对角线的使用情况
+ N' x( z& _; U5 v$ @
deputy = zeros(1, 2 * n - 1); % 记录副对角线的使用情况
. |7 `6 d0 x+ |, q2 I- C6 n0 F8 t; t
number = 0;
- W8 u2 g0 {* b$ r3 W
[chess, main, deputy, number] = justtry(1, n, chess, main, deputy, number);
3 R4 F. _2 {' D" [3 g J# b! I8 c- m
1 R. G8 w8 Y0 s: \$ X
这初始化了数组以跟踪主对角线和副对角线的情况，并通过调用justtry开始了递归回溯。整个过程将探索在8x8棋盘上所有可能的皇后排列，并打印每个有效排列以及解的总数。
. V! N2 Z R& C7 D+ L
* ~% L& \0 r: r! y
" T. \* j3 w7 D( z4 M; T( C- ?; C
4 d% [+ ~0 }4 w/ F- a. G" v
排列树的回溯搜索.rar
2023-12-22 16:52 上传
点击文件名下载附件
下载积分: 体力 -2 点
694 Bytes, 下载次数: 0, 下载积分: 体力 -2 点
售价:
2 点体力
[
记录
] [
购买
]
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
