QQ登录

只需要一步,快速开始

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

matlab解决n皇后问题

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

1186

主题

4

听众

2922

积分

该用户从未签到

跳转到指定楼层
1#
发表于 2023-12-22 16:10 |只看该作者 |倒序浏览
|招呼Ta 关注Ta
"N皇后问题"是一个著名的组合问题,其目标是在一个N×N的棋盘上放置N个皇后,使得它们彼此之间无法互相攻击。在国际象棋中,皇后可以在水平、垂直和对角线方向上移动,因此在棋盘上放置皇后时,需要确保任意两个皇后都不在同一行、同一列或同一对角线上。7 R8 K- e/ w" H: h$ U6 h
具体来说,N皇后问题的规则是:6 U7 u7 [% P1 l- q9 f$ c
0 a+ q1 j+ x0 ]$ }5 @+ f' |. r
1.每一行只能放置一个皇后。0 [# B6 O! p' e* O9 v
2.每一列只能放置一个皇后。
  i, f1 C# e0 U5 j: K3.每条对角线只能放置一个皇后。
7 b3 @8 z8 M' d- w( N1 _( p+ K: i/ [$ U! X9 P; \
N皇后问题是一个经典的递归和回溯问题,它的解法要求找到所有满足上述规则的皇后布局。问题的难度在于确保在放置每个皇后时都满足约束条件,同时要考虑到适当的优化以提高算法的效率。
8 i! Y4 g' A4 F% X解决N皇后问题的一种方法是使用回溯算法,通过逐行放置皇后并检查是否满足规则,如果不满足则回溯到前一步重新尝试。这个问题的解法通常会利用递归和回溯的思想,以及对棋盘状态的合理剪枝,以降低搜索的复杂度。- s, O1 _( }: {/ ^* K  O" o  s
N皇后问题是一个经典的组合问题,也是算法设计和递归思想的典型例子。
  1. clear all2 {( ?2 r5 `/ s\" {9 \, a/ r
  2. clc
复制代码
这两行命令清除工作空间中的所有变量,并清除命令窗口。
9 t& P2 C2 @. Y) Q  m" |%n皇后问题
  1. n=8;
    6 ~8 H; w& Y- |\" i% i
复制代码
这个注释指出代码是解决N皇后问题的,并将n的值设置为8,表示棋盘的大小为8x8。
  1. chess=zeros(n,n);! N9 C  E* I$ f0 V% v9 B
  2. row=zeros(1,n); %记录n列被占用的情况: L# k4 o  I/ c! J
  3. main=zeros(1,2*n-1); %记录主对角线的使用情况
    + G6 K6 ?* T# M
  4. deputy=zeros(1,2*n-1); %记录从对角线的使用情况% A8 ?) T; N1 J: u
  5. number=0;1 I1 E' m2 ^. ?6 L
  6. [chess,row,main,deputy,number]=justtry(1,n,chess,row,main,deputy,number);
复制代码
在这里,矩阵和数组被初始化。chess是一个NxN矩阵,表示棋盘,最初全部填充为零。row、main和deputy是用于跟踪特定行、主对角线或副对角线是否被占用的数组。number是解的数量计数器。然后调用justtry函数,传递初始参数。
  1. function [chess,row,main,deputy,number]=justtry(i,n,chess,row,main,deputy,number);
复制代码
这一行定义了justtry函数,它接受当前行i、棋盘大小n、棋盘chess、有关行和对角线占用的信息(row、main、deputy)以及当前解的计数number。它将在处理后返回这些变量的更新版本。, ]/ q/ t3 q0 H2 D0 b8 b
for k=1:82 O, C0 N$ ]( A9 z
) o& I6 S0 z( d5 y3 X% T
这开始一个循环,迭代处理当前行的每一列(k)。
* r+ E3 E+ U. M& p/ Y7 v2 jif row(k)==0 & main(i-k+n)==0 & deputy(i+k-1)==0/ S6 m; b% q. y! u8 A# t, m  A
* |: s/ O/ \+ E% b! l
这个条件检查当前列、主对角线和副对角线是否没有被占用。如果为真,则考虑在此位置放置皇后。
  1.     chess(i,k)=1;% M* d. F) V* f, n+ y# I) b& R
  2.     row(k)=1;$ w7 x8 L) |) j2 {2 t
  3.     main(i-k+n)=1;\" S  l\" H' M% ]
  4.     deputy(i+k-1)=1;
    ! v- W- W4 i# m5 B9 N+ @; j' T
复制代码
如果条件满足,就在当前位置放置一个皇后,并更新相应的数组(row、main、deputy)来标记占用。
7 X/ ]# G1 o* P! w( S- p    if i==8( K) ]# Z" U2 \9 l; G) L7 u# I

# |3 i! @1 T+ I+ u* h" L4 |4 F这检查是否已经到达了最后一行。如果为真,说明找到了一个解。
  1.         number=number+1;  _/ S4 ~! @4 T; A, z$ d
  2.         chess
复制代码
解的计数增加,并打印当前的棋盘配置。
$ q( T6 H7 Y9 g3 i' u    else
# r2 H: z! u/ J5 p1 o0 x5 G7 t* p+ A& y4 `
如果不在最后一行,函数继续搜索,通过递归调用自身处理下一行。
  1. [chess,row,main,deputy,number]=justtry(i+1,n,chess,row,main,deputy,number);
复制代码
用更新的参数递归调用函数处理下一行。4 d- M1 {: m) u( X% a( W+ \
    end# D& M+ s% a0 ]' U

( ?3 F& _7 q/ q" h2 {/ {4 L" j2 V- r这标志着对最后一行的条件检查结束。
  1.     chess(i,k)=0;
    2 m. z\" k$ K% z' _6 C: h\" o
  2.     row(k)=0;( _9 d7 P9 J9 C; o; m( C$ G& v
  3.     main(i-k+n)=0;
    / I2 v8 y- D5 N7 m/ d$ d
  4.     deputy(i+k-1)=0;
    * O. _- U* Q% x+ p9 I% d
复制代码
这是回溯的部分。如果在递归调用中找不到合适的位置放置皇后,则移除放置的皇后,并更新相应的数组,以回溯并尝试其他可能性。2 E# G& _* R6 z/ M: B" k
end
$ }: Q+ d, r7 K$ |! Y2 ]end
2 U% ]% I1 m( z/ {/ V! Y8 Y+ r7 X
  l3 B. M- i2 z$ c) h" o" L这标志着循环的结束和justtry函数的结束。循环迭代所有列,尝试在当前行找到可以放置皇后的有效位置。7 z6 G0 F$ I5 c
end
1 M! S+ @- v4 W, c- p% W2 ]; p- `
这标志着主脚本的结束。整个过程由使用初始参数调用justtry函数开始。找到解时,它们将被打印出来。) ]' z$ c" [3 C" @+ w
/ W( R0 e7 n/ k

+ X: ]' w! r. T  {0 v
- N6 K! Z# |2 H1 t7 S
0 `. ]* y+ u8 K! L& k" U

n皇后.rar

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

售价: 1 点体力  [记录]  [购买]

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-4-15 01:31 , Processed in 0.495587 second(s), 55 queries .

回顶部