数学建模社区-数学中国
标题:
排列树的回溯搜索解决n皇后问题
[打印本页]
作者:
2744557306
时间:
2023-12-22 16:28
标题:
排列树的回溯搜索解决n皇后问题
这是一个MATLAB实现的N皇后问题，这是一个经典的组合问题。其目标是在一个N×N的棋盘上放置N个皇后，使得它们之间互不攻击。提供的代码使用了递归回溯的方法来找到N皇后问题的所有解决方案。
; X+ T8 \ B! w" N# v: J7 ?! l C, }
让我们逐步解释这段代码：
% ~0 B7 ^( ?% U: w) Q0 ^
function [chess, main, deputy, number] = justtry(i, n, chess, main, deputy, number)
9 n* C; `( e; q4 d5 f& M
) p- ~) p! y# L6 w: s
这定义了一个名为justtry的函数，它接受六个参数：当前行数i，棋盘大小n，当前皇后的排列chess，主对角线和副对角线的状态（main和deputy），以及解的数量number。
9 H) I6 M, h- `
if i == 9
1 e7 Q6 e. s& O$ @- ^. p
number = number + 1;
' h9 W/ r1 \' F9 A$ K- B( g
chess
6 P( _/ s. o, V9 _0 _
else
6 @% s* t; b+ b G N( t
for k = i:8
6 j7 |: P0 {' d5 X6 I
if main(i - chess(k) + n) == 0 && deputy(i + chess(k) - 1) == 0
: X# V! H1 M' G4 \! k6 ?! R
6 _$ g. F8 C, T
这检查是否已经到达第9行。如果是这样，它会递增解的数量(number)并显示当前皇后在棋盘上的排列。否则，它进入一个从当前行(i)到8的循环。
' X& o* n1 d# {8 j" ]
嵌套的if语句检查当前棋盘位置是否有效（即没有皇后互相威胁）。如果条件满足，它将继续放置皇后。
$ f& r8 ]) n/ Q! `
t = chess(k); % 交换位置
1 P0 W# i6 s6 O# I( _+ j
chess(k) = chess(i);
- H" |! c6 d W5 k2 x( \
chess(i) = t;
. `1 e/ M; U. X0 b: q, [
1 I2 J$ y5 b1 ?3 k
main(i - chess(k) + n) = 1;
7 k2 ^" t5 E& X" l/ r4 R
deputy(i + chess(k) - 1) = 1;
2 D& w$ b* p9 I# Z) M$ P4 b5 }
& } N. n+ J! N# U" H- J, @) \- j
[chess, main, deputy, number] = justtry(i + 1, n, chess, main, deputy, number); % 递归调用
" V/ v% o1 b, J j! s- s
/ y n' F+ A1 M+ t+ H, T
t = chess(k); % 回溯
" n$ b, i- J! _5 q
chess(k) = chess(i);
k6 {0 i/ |- d8 l
chess(i) = t;
$ ?/ R- W( [' Q2 ^9 g' o( \
. r' P9 ]8 K7 n. s7 l7 ]; ]( h
main(i - chess(k) + n) = 0;
' ^+ y& t0 G$ i6 |
deputy(i + chess(k) - 1) = 0;
7 n9 L( k1 M2 H u. P
: G/ g, t7 b8 c& x6 ]
这部分是回溯算法的核心。它交换皇后的位置，更新对角线的状态，对下一行进行递归调用，然后通过恢复原始状态进行回溯。
6 ^0 I- ]% b2 ~' x
end
9 p/ p2 G' w0 }
end
# M' U5 H+ U# D# W! q4 v4 ^) E3 [
end
2 M5 d& T7 ]% A3 Z
. p8 ]: L d8 }+ M* y
这结束了循环和函数。如果i不是9，循环将继续到下一行。
" U }+ F8 J+ B# W4 }
clear all
$ q/ m0 O0 x2 k7 t {( A. v
clc
- y9 n& L1 H g! b8 s
. e# d# g) h% u% E1 u" p7 B
这些命令清除工作区和命令窗口。
! V4 w7 t- e- U; @, A* D6 W
n = 8;
% ?8 U( U3 e) U* J1 K; L9 O8 G' ~
chess = zeros(1, n);
# g& d1 H' y x9 ^7 @
for i = 1:n
, A7 q- x# R& v: w6 O* R
chess(i) = i;
; t* a4 D% x% E& ^9 p4 i
end
) b1 X" n# ?; D6 V0 H P& c8 w
4 Y: p; F8 ]% F4 x% V$ F/ t& G: k
这初始化了一个带有皇后的第一行的棋盘。
, T3 F6 z. S4 L% a/ K1 [
main = zeros(1, 2 * n - 1); % 记录主对角线的使用情况
2 r- l2 P8 ^9 a ~7 z1 [0 f
deputy = zeros(1, 2 * n - 1); % 记录副对角线的使用情况
& P( b0 m5 j' t3 v$ l2 c
number = 0;
6 _$ v) \3 x: |2 v+ B6 }
[chess, main, deputy, number] = justtry(1, n, chess, main, deputy, number);
3 A9 Q5 k* d- }( Y2 U4 {2 v
% ^" \& ]4 p7 F, w: j
这初始化了数组以跟踪主对角线和副对角线的情况，并通过调用justtry开始了递归回溯。整个过程将探索在8x8棋盘上所有可能的皇后排列，并打印每个有效排列以及解的总数。
4 Z% r& A0 p0 B+ c
8 a3 f k" y- ]+ K6 o6 [
i6 ~5 R8 ^2 @. {5 d, W" i- f
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5