QQ登录

只需要一步,快速开始

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

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

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

1189

主题

4

听众

2934

积分

该用户从未签到

跳转到指定楼层
1#
发表于 2023-12-22 16:52 |只看该作者 |倒序浏览
|招呼Ta 关注Ta
这是一个MATLAB实现的N皇后问题,这是一个经典的组合问题。其目标是在一个N×N的棋盘上放置N个皇后,使得它们之间互不攻击。提供的代码使用了递归回溯的方法来找到N皇后问题的所有解决方案。: v3 J# K- N/ q, m- d
让我们逐步解释这段代码:
  k1 R+ b- @: J  K; O* P. X+ Vfunction [chess, main, deputy, number] = justtry(i, n, chess, main, deputy, number)7 @# k* P3 \+ n1 E' {: O9 k3 M$ I, r

+ D. @4 E4 O9 o3 `  h这定义了一个名为justtry的函数,它接受六个参数:当前行数i,棋盘大小n,当前皇后的排列chess,主对角线和副对角线的状态(main和deputy),以及解的数量number。* h1 \& L) H, N8 @8 r+ m1 r
if i == 9/ o$ m6 [' B# J3 b( W: ^
    number = number + 1;; s2 u" i- r1 X
    chess+ F/ E: x* D5 R7 J$ {$ k+ c
else
3 G. a8 W0 _& E1 {" Z# ]! y+ w    for k = i:8
7 Y& Z* K" Y9 j' Q! k        if main(i - chess(k) + n) == 0 && deputy(i + chess(k) - 1) == 0' Y- h- c' J) O
* T1 j; A8 l/ e* C8 h* \0 a2 c
这检查是否已经到达第9行。如果是这样,它会递增解的数量(number)并显示当前皇后在棋盘上的排列。否则,它进入一个从当前行(i)到8的循环。
4 Y* E3 m/ i2 Y- G2 m嵌套的if语句检查当前棋盘位置是否有效(即没有皇后互相威胁)。如果条件满足,它将继续放置皇后。
6 {  T0 Y0 u* J5 x* F$ t% k            t = chess(k); % 交换位置: `( T2 c5 ~& [; [' h9 S+ K. {- a
            chess(k) = chess(i);9 D5 v: V* ~8 m. ~+ M* C
            chess(i) = t;
% q3 u$ a, ^6 S% G; _7 r7 s3 |
) d3 A) V# x) X0 S- a% Y$ ?5 r            main(i - chess(k) + n) = 1;  t0 c- |5 I$ v8 q8 i  F# r
            deputy(i + chess(k) - 1) = 1;2 U. p: v( H7 B8 s: S
0 E6 G2 J( r  e* X% o- H1 {, {
            [chess, main, deputy, number] = justtry(i + 1, n, chess, main, deputy, number); % 递归调用
0 J- s  c% V' O
, H% e3 D2 e9 y1 h            t = chess(k); % 回溯7 L0 [1 Z" ^) U4 ^
            chess(k) = chess(i);
& ~6 X. y  j) w0 ~            chess(i) = t;" I/ L4 j  t! V% }5 r% O$ @
9 w3 T8 m6 g( N7 w1 r& y& h
            main(i - chess(k) + n) = 0;
: b, J8 N: l: x$ U, U  S            deputy(i + chess(k) - 1) = 0;
  {3 s& g, c! P7 ~2 S& j' I$ `7 e8 I
这部分是回溯算法的核心。它交换皇后的位置,更新对角线的状态,对下一行进行递归调用,然后通过恢复原始状态进行回溯。
& A" i3 B3 }5 ?9 E        end
# u- v8 E: U9 ~# A0 S( v* i( c0 j    end- m5 B! N, U' i8 h( I* B8 \
end% Y3 F! M- u5 i# \+ c5 k

- N% F3 p/ h. i& H这结束了循环和函数。如果i不是9,循环将继续到下一行。# e. |% \$ _5 r' B- c
clear all
1 F( ]6 d* t. _* C$ ^; i' b3 e; oclc
; t' a! d! r3 }6 `+ ?! ^4 p: V1 B5 r$ R2 W) W2 C: f
这些命令清除工作区和命令窗口。, z, A# a& F" g/ v3 _9 p
n = 8;
; ^: y/ E2 g  |/ Z- G2 V( m8 c2 t$ ochess = zeros(1, n);
6 q" x" ?) Y, o' Hfor i = 1:n
; x& ^$ L$ \$ C, g$ |+ m    chess(i) = i;
8 n4 N2 x7 P+ A# Rend8 L5 Z7 M8 N4 j& g$ V. o

' `! {. T* z' \" X" d8 @) A这初始化了一个带有皇后的第一行的棋盘。2 k9 g4 w- P- M7 E* u
main = zeros(1, 2 * n - 1); % 记录主对角线的使用情况
( f# P0 N, I& X) [% ideputy = zeros(1, 2 * n - 1); % 记录副对角线的使用情况
1 Z' O5 a: v2 Hnumber = 0;
6 g3 ~8 V! b" l) {+ i! k" L9 g[chess, main, deputy, number] = justtry(1, n, chess, main, deputy, number);  C: _8 z. `9 V+ P5 P% w. U7 d) W

# v( d; W& I. V8 |这初始化了数组以跟踪主对角线和副对角线的情况,并通过调用justtry开始了递归回溯。整个过程将探索在8x8棋盘上所有可能的皇后排列,并打印每个有效排列以及解的总数。& f' y0 X4 H2 `2 {1 ]

: F1 y# E3 O) p5 h. u7 G! X, c3 P0 o2 g, \( u
( u& K, ?' M! j; u0 F% n

排列树的回溯搜索.rar

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

售价: 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-12 20:53 , Processed in 0.421071 second(s), 55 queries .

回顶部