QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2287|回复: 0
打印 上一主题 下一主题

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

[复制链接]
字体大小: 正常 放大

1189

主题

4

听众

2934

积分

该用户从未签到

跳转到指定楼层
1#
发表于 2023-12-22 16:28 |只看该作者 |倒序浏览
|招呼Ta 关注Ta
这是一个MATLAB实现的N皇后问题,这是一个经典的组合问题。其目标是在一个N×N的棋盘上放置N个皇后,使得它们之间互不攻击。提供的代码使用了递归回溯的方法来找到N皇后问题的所有解决方案。
* }# t8 A5 `$ N  h3 [8 ~: W! e让我们逐步解释这段代码:
$ W) r9 ?( ?, X- m4 I8 hfunction [chess, main, deputy, number] = justtry(i, n, chess, main, deputy, number)
4 p2 V; F% O: }; C0 W6 F3 q% P& n
这定义了一个名为justtry的函数,它接受六个参数:当前行数i,棋盘大小n,当前皇后的排列chess,主对角线和副对角线的状态(main和deputy),以及解的数量number。
% W& l3 B: e: Q. ~" sif i == 94 k: K  [7 {8 D! Z, a, i: S% A
    number = number + 1;
! F$ n" }# y; v1 [! Q    chess+ h1 d! v8 K: r
else
" r1 {) J* m4 V5 ?    for k = i:8
* q6 t/ Q3 h0 Z- c6 y        if main(i - chess(k) + n) == 0 && deputy(i + chess(k) - 1) == 0( U5 m( [) D$ x8 A! G8 C- ?
. n0 z0 Y+ u. Q! ~  ]8 U/ u) Q
这检查是否已经到达第9行。如果是这样,它会递增解的数量(number)并显示当前皇后在棋盘上的排列。否则,它进入一个从当前行(i)到8的循环。# v, U$ a! Y: j* u* }5 l
嵌套的if语句检查当前棋盘位置是否有效(即没有皇后互相威胁)。如果条件满足,它将继续放置皇后。
/ Y1 u$ F# O3 V* W9 U- F            t = chess(k); % 交换位置9 Z* q9 O! s$ O; A4 b* n* t
            chess(k) = chess(i);5 t7 O5 Z8 j$ h
            chess(i) = t;
$ o' Z1 b7 t+ i
; @9 d3 L: i+ z            main(i - chess(k) + n) = 1;6 F  k' Q) V$ [' v, u9 \7 O
            deputy(i + chess(k) - 1) = 1;2 w) ]' j/ ], X

+ S4 O2 K+ d4 N& @            [chess, main, deputy, number] = justtry(i + 1, n, chess, main, deputy, number); % 递归调用5 o* Q$ w5 ]  P0 X( h6 X

6 l. e3 j) i; S            t = chess(k); % 回溯& t5 X5 b, D' M0 P
            chess(k) = chess(i);- l3 ?2 V6 D  t
            chess(i) = t;
# a6 K2 S$ U! t
& {7 ^5 ~( c4 u/ P/ l. O8 S1 |            main(i - chess(k) + n) = 0;
6 B3 ?+ w) Y8 B8 k% p: a            deputy(i + chess(k) - 1) = 0;
, K: y! G7 M6 z+ [1 u( v) x9 S% z; X" V! q- R! X4 ^' L) X
这部分是回溯算法的核心。它交换皇后的位置,更新对角线的状态,对下一行进行递归调用,然后通过恢复原始状态进行回溯。9 j8 f( p' s, U6 P
        end  T2 F6 R5 k8 F( j
    end
- v) a6 v) h+ X1 Jend
- L8 }3 e  c( H3 @0 I' d. Z( }# D/ l: s# a
这结束了循环和函数。如果i不是9,循环将继续到下一行。
; F) n" C% }4 w1 ^: {# jclear all" U& x! C/ C; |# U. c
clc0 p+ ^: ]0 {0 ^' [
! Q7 ^3 c1 ^, ?$ {4 l/ v7 @8 ]# F
这些命令清除工作区和命令窗口。( f4 |4 n8 U% o5 T
n = 8;. B% R  c7 ~4 Y( \8 ^8 b1 S) R
chess = zeros(1, n);6 F6 H# x3 O  R: P8 J
for i = 1:n
3 h+ r5 @2 f" a: R) ?6 a    chess(i) = i;
/ U! \) O/ q1 t3 R9 v$ nend
  `) Z' A5 }$ t
  `' n% ~9 h* ?8 T9 k  V这初始化了一个带有皇后的第一行的棋盘。( _6 t( E5 M" k5 k4 z( U7 b: n
main = zeros(1, 2 * n - 1); % 记录主对角线的使用情况  M( @1 w! m5 W7 \
deputy = zeros(1, 2 * n - 1); % 记录副对角线的使用情况' l- V" x8 x( j7 h2 y( o- v
number = 0;! |( e" k1 k4 j7 Z
[chess, main, deputy, number] = justtry(1, n, chess, main, deputy, number);
8 c  S6 W0 v4 F/ x! S2 [' @# B8 m& n. u, p- ^6 r
这初始化了数组以跟踪主对角线和副对角线的情况,并通过调用justtry开始了递归回溯。整个过程将探索在8x8棋盘上所有可能的皇后排列,并打印每个有效排列以及解的总数。
  s$ U* K8 x9 Q/ i6 ~$ Z7 x, O4 ~8 P& ^2 D/ t

) ]  A2 j; a' t  _2 {% }' }
zan
转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
您需要登录后才可以回帖 登录 | 注册地址

qq
收缩
  • 电话咨询

  • 04714969085
fastpost

关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

手机版|Archiver| |繁體中文 手机客户端  

蒙公网安备 15010502000194号

Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

GMT+8, 2026-6-14 11:07 , Processed in 0.433584 second(s), 51 queries .

回顶部