用arrayfun求解八皇后问题

qibbxxt · 发表于 2010-12-30 10:10

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

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

x

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

clear;clc;close all
tic
N=8;
T=N-2;
rows=1:N; % 皇后所在行的位置
cols=perms(rows); % 皇后所在列的位置
S=size(cols,1);
M=zeros(N,N,S); % 存储所以情况的矩阵
linearInd = sub2ind(size(M), repmat(rows',1,S), cols', repmat(1:S,N,1));
M(linearInd) = 1;
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);
M(:,:,dv>1)=[];
toc

复制代码

Rainyboy · 发表于 2010-12-30 10:54

个人认为解决八皇后问题还是用递归有效率些吧。
不过qibbxxt的意思也许是在于arrayfun的用法？
学习了，呵呵。

Rainyboy · 发表于 2010-12-30 11:11

本帖最后由 Rainyboy 于 2010-12-30 11:18 编辑

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

// 8queens.cpp : 定义控制台应用程序的入口点。
//八皇后问题:范雨，2005年11月19日。
/*程序以第一列第一行开始，当第一列的皇后移动到第八个位置还要求向下移动时，程序结束*/
#include "stdio.h"
#include "dos.h"
#include "time.h"
double timer;//全局变量：跨函数计时。
int count;//全局变量：计解的个数。
void output(int b[][9]);//输出处理好的二维数组。
void backup(int piont,int b[][9]);//重新标定，注意，此处的piont值为当前即将标定到的最大line值。在函数体中调用sign()函数。
void sign(int b[][9],int row,int line);//标定，每判断成功一个位置，就用此函数标定，但是只需要标定其后的line即可。
int select(int b[][9]);//选出合适的，至少是和前面的line不重复的位置，在此函数中调用output(),sign(),backup()函数。
int _tmain(int argc, _TCHAR* argv[])
{
int b[9][9];int i,n;
for(i=1;i<=8;i++)
for(n=1;n<=8;n++)
b[n][i]=1;//初始化棋盘。
timer=time(0);//第一次计时。
count=0;//解的个数初始化。
select(b);//核心代码。
printf("计算结束：八皇后问题共%d解！",count);
getchar();
return 0;
}
int select(int b[][9])//选出合适的，至少是和前面的line不重复的位置，在此函数中调用output(),sign(),backup()函数。
{
static i;i++;//静态变量控制列的移动，注意每次调用的值都不会重新初始化。
int n=i;int control;//用局部变量n来转移i的值，用来控制本次内部的循环＆判断，以免在递归之间出现不可预料的i值改变。
for(control=1;1;control++)//先让这个循环看似为死循环，在循环体内部控制转向。
{
if(control==9) return 1;//如果本行里面找不到位置，那么返回上一步重新找皇后的位置。
else if(b[control][n]==0) continue;//如果值为0，当然不能插入皇后。
b[control][n] = 8;//若不是上面的两种情况，那么值必定为1，插入皇后。
if(n==8)
{
output(b);//输出一个结果。
return 1;//如果已经获得了一个解，那么当然要返回求下一个解。
}
sign(b,control,n);//当然，得当一个皇后值之后，当然要标定。
if(select(b))//递归调用，找下一个皇后，如果返回值为1，即需要返回本次运算，执行下面的语句：
{
i--;//i的值必须通过这种方式回到上一步。
if(n-1)backup(n-1,b);//即n不等于1的时候执行backup对前n-1列进行重新标定。
b[control][n]=1;//无论n是否等于1都要将当前值标定为1，为下一次判断作准备。
if(n==1)backup(1,b);//但是当n＝1时并没有重新标定，此处补上。
continue;//跳过本次循环，直接在本列内找下一个位置。
}
}
}
void output(int b[][9])//输出处理好的二维数组。
{
count++;
int row,line;
printf("八皇后问题第【%2d】解！\n",count);
for(row=1;row<=8;row++)
{
for(line=1;line<=8;line++)
{
if(b[row][line]==8)printf("※ ");
else printf("○ ");
}
printf("\n");
}
printf("消耗时间：%.4f秒\n",difftime(time(0),timer));
printf("按回车(Enter)键查看下一解：");
getchar();
timer=time(0);//第二次及以后的计时在此处完成。
system("cls");
}
void backup(int piont,int b[][9])//重新标定，注意，此处的piont值为当前即将标定到的最大line值。在函数体中调用sign()函数。
{
int out,in;
int t_control,i_control;
for(out=1;out<=8;out++)
{
for(in=1;in<=8;in++)
{
if(b[out][in]==0)b[out][in]=1;
}
}//首先回到初始状态，即除了从1到piont列的为8的值保留外，其余全部标为1【（piont+1）列的值在select函数调用backup函数之后会被标定为1】。
for(i_control=1;i_control<=piont;i_control++)
{
for(t_control=1;t_control<=8;t_control++)
if(b[t_control][i_control]==8)
sign(b,t_control,i_control);//t_control，i_control应该分别对应sign函数参数中的row和line。
}//如果找到了值为8的点，就送到sign函数进行标定。
}
void sign(int b[][9],int row,int line)//标定，每判断成功一个位置，就用此函数标定，但是只需要标定其后的line即可。
{
int row_control,line_control;
for(row_control=row,line_control=line;line_control<=8;row_control--,line_control++)
{
if(row_control>=1&&line_control<=8)b[row_control][line_control]=0;//标定右上方。
b[row][line_control]=0;//标定本行。
}
for(row_control=row,line_control=line;line_control<=8;row_control++,line_control++)
{
if(row_control<=8&&line_control<=8)b[row_control][line_control]=0;//标定右下方。
}
b[row][line]=8;//由于在函数体中没有考虑到b[row][line]的值，所以在执行完标定之后在重新赋值。
}

复制代码

Rainyboy · 发表于 2010-12-30 13:28

本帖最后由 Rainyboy 于 2010-12-30 13:34 编辑

再来一个简洁的递归算法，用python写的。除去注释只有很短的代码，可以解决N皇后的问题。

# -*- coding: cp936 -*-
#使用生成器解决 N皇后问题
#本质上是递归算法
#范雨 2010.12.30 改编自《Practical Python》
def conflict(state, nextX):
'''
如果有冲突发生，则返回True,没有则返回False
state:已有的（无冲突）皇后列位置，是一个列表
nextX：欲新增的皇后列位置
'''
nextY = len(state);
for i in range(nextY):
if abs(state[i]-nextX) in (0, nextY-i):
return True;
return False;
def queens(num, state=()):
'''
num 是皇后的数量，问题的规模，在求解过程中不会变化
state 在每次递归中不断连接，变长，最终形成N皇后问题的一个解
'''
if len(state) == num-1:
#该分支描述的是最后一个皇后的情形
for pos in range(num):
if not conflict(state,pos):
yield (pos,);
else:
#该分支描述的是一般的情形
for pos in range(num):
if not conflict(state,pos):
for result in queens(num,state + (pos,)):
yield (pos,) + result;
def prettyprint(solution):
'''输出一个解'''
def line(pos,length=len(solution)):
return u'● '*(pos) + u'□ ' + u'● '*(length-pos-1)
for pos in solution:
print line(pos);
def main():
numofQueen = 4;#皇后的个数，同时确定了棋盘的大小
allsolu = list(queens(numofQueen));#使用生成器构造出所有的解
#输出
count = 1;
for solu in allsolu:
print numofQueen,'皇后问题第',count,'解';
count = count + 1;
prettyprint(solu);
print '求解完毕：',numofQueen,'皇后问题共',count-1,'解';
if __name__ == "__main__":main();

复制代码

图示一：

图示二：

除去注释后的代码：

Rainyboy · 发表于 2010-12-30 13:44

这几天咱们两个分区的交流方式个人很是喜欢，感觉大开眼界啊！
早些时候我是想推动这样的交流来着，但是帖子发在了算法及编程语言分区，是一个关于TTM方法分网格的例子，分别用python和MATLAB写成。

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

欢迎大家指正！

qibbxxt · 发表于 2011-1-19 16:10

今天用0-1规划写了一个
前段时间写过剔除法求解八皇后问题，可以求出所有解，今天用0-1规划写了一个程序，每次只能求出一个解

clear;clc;close all
N=8;
c=ones(N);
% 行求和
blkele=num2cell(c,2);
A1=blkdiag(blkele{:});
% 列求和
A2=repmat(eye(N),1,N);
Aeq=[A1;A2];
beq=ones(2*N,1);
% 斜线情况判断
M=N-2;
A=zeros(4*M+2,N*N);
d{1}=arrayfun(@(i)find(diag(diag(c,i),i)),-M:M,'UniformOutput',0);
d{2}=arrayfun(@(i)find(fliplr(diag(diag(c,i),i))),-M:M,'UniformOutput',0);
d0=cat(1,d{:});
linearIndex=arrayfun(@(x)sub2ind(size(A),x+zeros(1,length(d0{x})),...
d0{x}'),1:numel(d0),'UniformOutput',0);
A(cell2mat(linearIndex))=1;
b=ones(4*M+2,1);
x=bintprog([],A,b,Aeq,beq);
Res=reshape(x,[],N);

复制代码

下面是我用lingo写的一个版本，还有待改进

model:
sets:
Node/1..8/:N;
link(Node,Node):x;
plus1/1..15/:;
minus1/1..6/:;
endsets
@for(Node(i):@sum(Node(j):x(i,j))=1);
@for(Node(j):@sum(Node(i):x(i,j))=1);
@for(plus1(k)|k#ge#3:@sum(link(i,j)|i+j#eq#k:x(i,j))<1);
@for(minus1(k):@sum(link(i,j)|i-j#eq#k:x(i,j))<1);
@for(minus1(k):@sum(link(i,j)|j-i#eq#k:x(i,j))<1);
@sum(Node(i):x(i,i))<1;
@for(link(i,j):@bin(x(i,j)));

复制代码

账号		自动登录	找回密码
密码			我要加入

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

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

评分

点评

评分

点评

评分

评分