声振论坛

 找回密码
 我要加入

QQ登录

只需一步,快速开始

查看: 3425|回复: 5

[编程技巧] 用arrayfun求解八皇后问题

[复制链接]
发表于 2010-12-30 10:10 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?我要加入

x
看了萝卜的程序,http://luobo.ycool.com/post.866141.html
用剔除的思想去求解八皇后问题
决定用arrayfun来重写一下这个问题,发现arrayfun的效率并不高
这样做只为代码的简洁,欢迎大家讨论



  1. clear;clc;close all
  2. tic
  3. N=8;
  4. T=N-2;
  5. rows=1:N; % 皇后所在行的位置
  6. cols=perms(rows); % 皇后所在列的位置
  7. S=size(cols,1);
  8. M=zeros(N,N,S); % 存储所以情况的矩阵
  9. linearInd = sub2ind(size(M), repmat(rows',1,S), cols', repmat(1:S,N,1));
  10. M(linearInd) = 1;
  11. dv=arrayfun(@(k)max([arrayfun(@(x)sum(diag(M(:,:,k),x)),-T:T),arrayfun(@(x)sum(diag(rot90(M(:,:,k)),x)),-T:T)]),1:S);
  12. M(:,:,dv>1)=[];
  13. toc
复制代码


评分

2

查看全部评分

回复
分享到:

使用道具 举报

发表于 2010-12-30 10:54 | 显示全部楼层
个人认为解决八皇后问题还是用递归有效率些吧。
不过qibbxxt的意思也许是在于arrayfun的用法?
学习了,呵呵。

点评

赞成: 2.0
赞成: 2
恩,的确,递归是比较有效的解决办法,但很难将所有解都求出来,arrayfun的效率并不高,只是看起来简洁一些  发表于 2010-12-30 10:59
发表于 2010-12-30 11:11 | 显示全部楼层
本帖最后由 Rainyboy 于 2010-12-30 11:18 编辑

作为对本帖简洁的非递归算法的对比,贴一个我大一时用C写的递归八皇后,可以解出所有的92个解,编译后的程序见附件。
那时候刚刚开始学习编程,注释有些自言自语……也不想改了……大家凑合看吧。

1.jpg


  1. // 8queens.cpp : 定义控制台应用程序的入口点。
  2. //八皇后问题:范雨,2005年11月19日。
  3. /*程序以第一列第一行开始,当第一列的皇后移动到第八个位置还要求向下移动时,程序结束*/
  4. #include "stdio.h"
  5. #include "dos.h"
  6. #include "time.h"
  7. double timer;//全局变量:跨函数计时。
  8. int count;//全局变量:计解的个数。
  9. void output(int b[][9]);//输出处理好的二维数组。
  10. void backup(int piont,int b[][9]);//重新标定,注意,此处的piont值为当前即将标定到的最大line值。在函数体中调用sign()函数。
  11. void sign(int b[][9],int row,int line);//标定,每判断成功一个位置,就用此函数标定,但是只需要标定其后的line即可。
  12. int select(int b[][9]);//选出合适的,至少是和前面的line不重复的位置,在此函数中调用output(),sign(),backup()函数。
  13. int _tmain(int argc, _TCHAR* argv[])
  14. {
  15.         int b[9][9];int i,n;
  16.         for(i=1;i<=8;i++)
  17.                 for(n=1;n<=8;n++)
  18.                   b[n][i]=1;//初始化棋盘。
  19.   timer=time(0);//第一次计时。
  20.         count=0;//解的个数初始化。
  21.         select(b);//核心代码。
  22.         printf("计算结束:八皇后问题共%d解!",count);
  23.         getchar();
  24.         return 0;
  25. }
  26. int select(int b[][9])//选出合适的,至少是和前面的line不重复的位置,在此函数中调用output(),sign(),backup()函数。
  27. {
  28.         static i;i++;//静态变量控制列的移动,注意每次调用的值都不会重新初始化。
  29.         int n=i;int control;//用局部变量n来转移i的值,用来控制本次内部的循环&判断,以免在递归之间出现不可预料的i值改变。
  30.         for(control=1;1;control++)//先让这个循环看似为死循环,在循环体内部控制转向。
  31.         {
  32.                 if(control==9) return 1;//如果本行里面找不到位置,那么返回上一步重新找皇后的位置。
  33.                 else if(b[control][n]==0) continue;//如果值为0,当然不能插入皇后。
  34.                 b[control][n] = 8;//若不是上面的两种情况,那么值必定为1,插入皇后。
  35.                 if(n==8)
  36.                 {
  37.                         output(b);//输出一个结果。
  38.                         return 1;//如果已经获得了一个解,那么当然要返回求下一个解。
  39.                 }
  40.                 sign(b,control,n);//当然,得当一个皇后值之后,当然要标定。
  41.                 if(select(b))//递归调用,找下一个皇后,如果返回值为1,即需要返回本次运算,执行下面的语句:
  42.                 {
  43.                         i--;//i的值必须通过这种方式回到上一步。
  44.                         if(n-1)backup(n-1,b);//即n不等于1的时候执行backup对前n-1列进行重新标定。
  45.                         b[control][n]=1;//无论n是否等于1都要将当前值标定为1,为下一次判断作准备。
  46.                         if(n==1)backup(1,b);//但是当n=1时并没有重新标定,此处补上。
  47.                         continue;//跳过本次循环,直接在本列内找下一个位置。
  48.                 }
  49.         }
  50. }
  51. void output(int b[][9])//输出处理好的二维数组。
  52. {
  53.         count++;
  54.         int row,line;
  55.         printf("八皇后问题第【%2d】解!\n",count);
  56.         for(row=1;row<=8;row++)
  57.         {
  58.                 for(line=1;line<=8;line++)
  59.                 {
  60.                         if(b[row][line]==8)printf("※ ");
  61.                         else printf("○ ");
  62.                 }
  63.                 printf("\n");
  64.         }
  65.         printf("消耗时间:%.4f秒\n",difftime(time(0),timer));
  66.         printf("按回车(Enter)键查看下一解:");
  67.     getchar();
  68.         timer=time(0);//第二次及以后的计时在此处完成。
  69.         system("cls");
  70. }
  71. void backup(int piont,int b[][9])//重新标定,注意,此处的piont值为当前即将标定到的最大line值。在函数体中调用sign()函数。
  72. {
  73.         int out,in;
  74.         int t_control,i_control;
  75.         for(out=1;out<=8;out++)
  76.         {
  77.                 for(in=1;in<=8;in++)
  78.                 {
  79.                         if(b[out][in]==0)b[out][in]=1;
  80.                 }
  81.         }//首先回到初始状态,即除了从1到piont列的为8的值保留外,其余全部标为1【(piont+1)列的值在select函数调用backup函数之后会被标定为1】。
  82.     for(i_control=1;i_control<=piont;i_control++)
  83.         {
  84.                 for(t_control=1;t_control<=8;t_control++)
  85.                         if(b[t_control][i_control]==8)
  86.                                 sign(b,t_control,i_control);//t_control,i_control应该分别对应sign函数参数中的row和line。
  87.         }//如果找到了值为8的点,就送到sign函数进行标定。
  88. }
  89. void sign(int b[][9],int row,int line)//标定,每判断成功一个位置,就用此函数标定,但是只需要标定其后的line即可。
  90. {
  91.         int row_control,line_control;
  92.         for(row_control=row,line_control=line;line_control<=8;row_control--,line_control++)
  93.         {
  94.                 if(row_control>=1&&line_control<=8)b[row_control][line_control]=0;//标定右上方。
  95.                 b[row][line_control]=0;//标定本行。
  96.         }
  97.         for(row_control=row,line_control=line;line_control<=8;row_control++,line_control++)
  98.         {
  99.                 if(row_control<=8&&line_control<=8)b[row_control][line_control]=0;//标定右下方。
  100.         }
  101.         b[row][line]=8;//由于在函数体中没有考虑到b[row][line]的值,所以在执行完标定之后在重新赋值。
  102. }
复制代码


VC++:八皇后问题.rar

43.08 KB, 下载次数: 0

编译后的程序

评分

1

查看全部评分

发表于 2010-12-30 13:28 | 显示全部楼层
本帖最后由 Rainyboy 于 2010-12-30 13:34 编辑

再来一个简洁的递归算法,用python写的。除去注释只有很短的代码,可以解决N皇后的问题。
  1. # -*- coding: cp936 -*-
  2. #使用生成器解决 N皇后问题
  3. #本质上是递归算法
  4. #范雨 2010.12.30 改编自《Practical Python》

  5. def conflict(state, nextX):
  6.     '''
  7.     如果有冲突发生,则返回True,没有则返回False
  8.     state:已有的(无冲突)皇后列位置,是一个列表
  9.     nextX:欲新增的皇后列位置
  10.     '''
  11.     nextY = len(state);
  12.     for i in range(nextY):
  13.         if abs(state[i]-nextX) in (0, nextY-i):
  14.             return True;
  15.     return False;

  16. def queens(num, state=()):
  17.     '''
  18.     num 是皇后的数量,问题的规模,在求解过程中不会变化
  19.     state 在每次递归中不断连接,变长,最终形成N皇后问题的一个解
  20.     '''
  21.     if len(state) == num-1:
  22.         #该分支描述的是最后一个皇后的情形
  23.         for pos in range(num):
  24.             if not conflict(state,pos):
  25.                 yield (pos,);
  26.     else:
  27.         #该分支描述的是一般的情形
  28.         for pos in range(num):
  29.             if not conflict(state,pos):
  30.                 for result in queens(num,state + (pos,)):
  31.                     yield (pos,) + result;
  32.                     
  33. def prettyprint(solution):
  34.     '''输出一个解'''
  35.     def line(pos,length=len(solution)):
  36.         return u'● '*(pos) + u'□ ' + u'● '*(length-pos-1)
  37.     for pos in solution:
  38.         print line(pos);

  39. def main():
  40.     numofQueen = 4;#皇后的个数,同时确定了棋盘的大小
  41.     allsolu = list(queens(numofQueen));#使用生成器构造出所有的解
  42.     #输出
  43.     count = 1;
  44.     for solu in allsolu:
  45.         print numofQueen,'皇后问题第',count,'解';
  46.         count = count + 1;
  47.         prettyprint(solu);
  48.     print '求解完毕:',numofQueen,'皇后问题共',count-1,'解';
  49.    
  50. if __name__ == "__main__":main();
复制代码

图示一:
2.jpg


图示二:
1.jpg

除去注释后的代码:
3.jpg





点评

To ChaChing: Python中的yield是非常妙的一种返回值方式,与return有些不同,一言难尽……有兴趣的同学自会去查找资料的,所以我就没过多解释,呵呵~  发表于 2011-1-3 00:43
虽评分但我不懂, 汗  发表于 2011-1-3 00:37

评分

1

查看全部评分

发表于 2010-12-30 13:44 | 显示全部楼层
这几天咱们两个分区的交流方式个人很是喜欢,感觉大开眼界啊!
早些时候我是想推动这样的交流来着,但是帖子发在了算法及编程语言分区,是一个关于TTM方法分网格的例子,分别用python和MATLAB写成。

用TTM方法生成翼型网格(Python & MATLAB)
http://forum.vibunion.com/forum- ... fromuid-159019.html

欢迎大家指正!
 楼主| 发表于 2011-1-19 16:10 | 显示全部楼层
今天用0-1规划写了一个
前段时间写过剔除法求解八皇后问题,可以求出所有解,今天用0-1规划写了一个程序,每次只能求出一个解

  1. clear;clc;close all
  2. N=8;
  3. c=ones(N);
  4. % 行求和
  5. blkele=num2cell(c,2);
  6. A1=blkdiag(blkele{:});
  7. % 列求和
  8. A2=repmat(eye(N),1,N);
  9. Aeq=[A1;A2];
  10. beq=ones(2*N,1);
  11. % 斜线情况判断
  12. M=N-2;
  13. A=zeros(4*M+2,N*N);
  14. d{1}=arrayfun(@(i)find(diag(diag(c,i),i)),-M:M,'UniformOutput',0);
  15. d{2}=arrayfun(@(i)find(fliplr(diag(diag(c,i),i))),-M:M,'UniformOutput',0);
  16. d0=cat(1,d{:});
  17. linearIndex=arrayfun(@(x)sub2ind(size(A),x+zeros(1,length(d0{x})),...
  18.     d0{x}'),1:numel(d0),'UniformOutput',0);
  19. A(cell2mat(linearIndex))=1;
  20. b=ones(4*M+2,1);
  21. x=bintprog([],A,b,Aeq,beq);
  22. Res=reshape(x,[],N);
复制代码
下面是我用lingo写的一个版本,还有待改进

  1. model:
  2. sets:
  3. Node/1..8/:N;
  4. link(Node,Node):x;
  5. plus1/1..15/:;
  6. minus1/1..6/:;
  7. endsets
  8. @for(Node(i):@sum(Node(j):x(i,j))=1);
  9. @for(Node(j):@sum(Node(i):x(i,j))=1);
  10. @for(plus1(k)|k#ge#3:@sum(link(i,j)|i+j#eq#k:x(i,j))<1);
  11. @for(minus1(k):@sum(link(i,j)|i-j#eq#k:x(i,j))<1);
  12. @for(minus1(k):@sum(link(i,j)|j-i#eq#k:x(i,j))<1);
  13. @sum(Node(i):x(i,i))<1;
  14. @for(link(i,j):@bin(x(i,j)));
复制代码

评分

1

查看全部评分

您需要登录后才可以回帖 登录 | 我要加入

本版积分规则

QQ|小黑屋|Archiver|手机版|联系我们|声振论坛

GMT+8, 2024-11-24 16:56 , Processed in 0.057922 second(s), 22 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表