50

n色方柱问题 把算法变成代码

void search()
{
int i,t,cube,newg,over,ok;
int *vert=new int[n];
int *edge=new int[n*2];
for(i=0;i t=-1;newg=1;
while(t>-2){
t++;
cube=t%n; //每个立方体找2次
if(newg)edge[t]=-1;
over=0;ok=0;
while(!ok && !over){
edge[t]++;
if(edge[t]>2)over=1; //每个立方体只有3条边
else ok=(t }
if(!over){
if(++vert[board[cube][edge[t]*2]]>2+t/n*2)ok=0;
if(++vert[board[cube][edge[t]*2+1]]>2+t/n*2)ok=0;
if(t%n==n-1&&ok) //check that each vertex is order 2
for(i=0;i2+t/n*2)ok=0;
if(ok){if(t==n*2-1){ //找到解
ans++;
out(edge);
return;
}
else newg=1;
} //ok
else{ //取下一条边
--vert[board[cube][edge[t]*2]];
--vert[board[cube][edge[t]*2+1]];
t--;newg=0;
}
} //over
else{ //回溯
t--;
if(t>-1){
cube=t%n;
--vert[board[cube][edge[t]*2]];
--vert[board[cube][edge[t]*2+1]];
}
t--;newg=0;
}
}

}

找到一个解由out输出。

void out(int edge[])
{
int k,a,b,c,d;
for(int i=0;i<2;i++){
for(int j=0;j<n;j++) used[j]=0;
do{
j=0; //找下一条未用边
d=c=-1;
while(j<n&&used[j]) j++;
if(j<n)
do{
a=board[j][edge[i*n+j]*2];
b=board[j][edge[i*n+j]*2+1];
if(b==d)(k=a;a=b;b=k;)
solu[j][i*2]=a;
solu[j][i*2+1]=b;
used[j]=1;
if(c<0)c=a; //开始顶点
d=b;
for(k=0;k<n;k++) //找下一个立方体
if(!used[k]&&(board[k][edge[i*n+k]*2]==b ||
board[k][edge[i*n+k]*2+1]==b))j=k;
}while(b!=c);
}while(j<n);
}
for(int j=0;j<n;j++){
k=3-edge[j]-edge[j+n];
a=board[j][k*2];
b=board[j][k*2+1];
solu[j][4]=a;
solu[j][5]=b;
}
for(i=0;i<n;i++){
for(j=0;j<6;j++)
cout<<color[solu[i][j]];
cout<<endl;
}

}

执行算法的主要函数如下

int main()
{
readin();
search();
if(ans==0)cout<<"No Solution!"<<endl;
return 0;

}

初始数据由readin读入。

void readin()
{
fin>>n;
Make2DArray(board,n,6);
Make2DArray(solu,n,6);
color=new char[n];
used=new int[n];
for(int j=0;j>color[j];
for(int i=0;i for(int j=0;j>board[i][j];
}

查看全部
u012928797
➕Debugging
2015/06/30 14:32
  • 算法
  • 点赞
  • 收藏
  • 回答
    私信

1个回复