国际象棋中马的遍历问题

home_king

标志已访问棋格能保证不走重复步，可是我在你的程序里看不到这一步骤啊。
请指点。

devel

有点不好意思啊。。。。。。
这个脚本没有走过的一步就做个标记，是整8个关联数组，%0,%1,%2....。里面的key 是0,1,2,3,4,.....
%0=( 0,"00", 1,"01", 2,"02", 3,"03", 4,"04", 5,"05", 6,"06", 7,"07" );
.............................
$i代表关联数组名和$j代表key合起来就当是棋盘的座标了。马每走一步就删去那个数组元素直到8个关联数组全为空。[0-7]限制了马走步的范围。
if    (($i+1) =~ /[0-7]/ && ($j+2) =~ /[0-7]/ ) {delete${($i+1)}{($j+2)}; }
要是第一个条件不行就下一个，直到找到条件符合的为止，不懂得这个脚本怎么会不行。正确的输出是元素逐渐少的，直到全被清空.


还要请教高手啊。。。
用C怎么写，按照C的算法用PERL写个也行吧。。。。
我可能没说清楚，不明白的请提出来。

devel

发现错误了。:sorry:sorry 少了赋值了，要是没有$i +=1; $j +=2,$i 和$j就一直不变。还有把输出弄得好看些。
#!/usr/bin/perl -w
%0=( 0,"00", 1,"01", 2,"02", 3,"03", 4,"04", 5,"05", 6,"06", 7,"07" );
%1=( 0,"10", 1,"11", 2,"12", 3,"13", 4,"14", 5,"15", 6,"16", 7,"17" );
%2=( 0,"20", 1,"21", 2,"22", 3,"23", 4,"24", 5,"25", 6,"26", 7,"27" );
%3=( 0,"30", 1,"31", 2,"32", 3,"33", 4,"34", 5,"35", 6,"36", 7,"37" );
%4=( 0,"40", 1,"41", 2,"42", 3,"43", 4,"44", 5,"45", 6,"46", 7,"47" );
%5=( 0,"50", 1,"51", 2,"52", 3,"53", 4,"54", 5,"55", 6,"56", 7,"57" );
%6=( 0,"60", 1,"61", 2,"62", 3,"63", 4,"64", 5,"65", 6,"66", 7,"67" );
%7=( 0,"70", 1,"71", 2,"72", 3,"73", 4,"74", 5,"75", 6,"76", 7,"77" );
srand; $i=int(rand(8)); $j=int(rand(8));delete${$i}{$j}; print "$i $j\n";
for ($count=1;$count<=63;$count++) {
if    (($i+1) =~ /[0-7]/ && ($j+2) =~ /[0-7]/ ) {$i +=1; $j +=2; delete${$i}{$j}; @a=keys(%{$i})
; @a=sort(@a); print "@a\n"; }
elsif (($i+1) =~ /[0-7]/ && ($j-2) =~ /[0-7]/ ) {$i +=1; $j -=2; delete${$i}{$j}; @a=keys(%{$i})
; @a=sort(@a); print "@a\n"; }
elsif (($i-1) =~ /[0-7]/ && ($j+2) =~ /[0-7]/ ) {$i -=1; $j +=2; delete${$i}{$j}; @a=keys(%{$i})
; @a=sort(@a); print "@a\n"; }
elsif (($i-1) =~ /[0-7]/ && ($j-2) =~ /[0-7]/ ) {$i -=1; $j -=2; delete${$i}{$j}; @a=keys(%{$i})
; @a=sort(@a); print "@a\n"; }
elsif (($i+2) =~ /[0-7]/ && ($j+1) =~ /[0-7]/ ) {$i +=2; $j +=1; delete${$i}{$j}; @a=keys(%{$i})
; @a=sort(@a); print "@a\n"; }
elsif (($i+2) =~ /[0-7]/ && ($j-1) =~ /[0-7]/ ) {$i +=2; $j -=1; delete${$i}{$j}; @a=keys(%{$i})
; @a=sort(@a); print "@a\n"; }
elsif (($i-2) =~ /[0-7]/ && ($j+1) =~ /[0-7]/ ) {$i -=2; $j +=1; delete${$i}{$j}; @a=keys(%{$i})
; @a=sort(@a); print "@a\n"; }
elsif (($i-2) =~ /[0-7]/ && ($j-1) =~ /[0-7]/ ) {$i -=2; $j -=1; delete${$i}{$j}; @a=keys(%{$i})
; @a=sort(@a); print "@a\n"; }
else { print "not match, the scripte will exit\n"; exit ; } }

输出是这样：
0 1 2 3 5 6 7
0 1 2 3 4 5 7
0 1 2 3 5 6 7
0 1 2 3 4 5 7
0 1 2 3 5 6 7
.........................
0 1 2 3 4 5 7 #这样有64行

不知道为什么delete${$i}{$j}; 不起作用。用数字做关联数组名是行的。看下面的例子：
#!/usr/bin/perl -w
%0=(0,"00",1,"01",2,"02");
$i=0; $j=1; delete ${$i}{$j}; @d=keys(%{$i}); print "@d\n";
#
这是输出：
0 2

搞不明白，现在关键可能是怎么删元素，请大家指教！！

georgek

樓主在c 中有沒有?現這個? 照樓主的要求應該有一格是行不到的啊, 落棋用了一格再行一步便沒有三格了, 如此最後應該還留下一格不能行的啊

home_king

的确，落棋已用一格，如果按半步计算，那再走一步又用两格，共三格。以后每走一步将占用两格。(64-3)%2!=0哦，也就是说根本不能走完整个棋盘，最后将只走半步而已。这样任何算法都没有意义啦。
所以，所谓跳完全棋盘，每一整步算一跳，而中间跳过的半步不算数。

home_king

还是那句话，课业繁重。现在我们期考10多门(这个星期考的是我最怕的电磁场与电磁波啊:-)每天早晚都出去复习，只有中午或吃完饭回来洗澡才有点时间。
不过考完试后我会给出实现这个算法的成功的求精过的C程序。请各位兄弟见谅。
还有，马确实能无重复遍历全棋盘，我们数据结构的老师就用程序实现啦，和我不同的是，它用的是数组，而我为了进一步降低空间复杂度，用的是位图(C的强项之一哦)。

georgek

那兄弟?作了沒有?

devel

嘿嘿~~物理的我最怕电子电路啦。。。。。。最好的是关于气体的那章。。。。

georgek

妹子你這副急性子弄什麼氣體的好像不好吧, 不然氣體爆炸就不好啦 :p


嘿嘿~~~~~俺弄空气动力学的说，设计飞机模型啊。。。。

home

这是在LOVEUNIX的C程序 棋盘是6*6

#include <stdio.h>
#include <dos.h>
#include <graphics.h>
#define N 6
int  v[]={-1,1,-2,2,-2,2,-1,1};
int  h[]={-2,-2,-1,-1,1,1,2,2};
int count=0;
int nl=0,nk=0,ndirec=0;
int nosolve=0;
struct square{
int x;
int y;
int direc;
}a[N*N];
int board[N][N]={0};
int valid(int i,int j);
void jump(int i,int j,int d);
void outroute(FILE* fp);
void cartoon();
void main(){
int x,y;
int l,k,direc;
int gdriver=DETECT,gmode;
initgraph(&gdriver,gmode,"c:\\tc20\\bgi");
printf("\n\nPlease input start position,range: (1,1)~(6,6)\n");
scanf("%d,%d",&l,&k);
l--;k--;
direc=0;
count=0;
setcolor(WHITE);
while(1){
jump(k,l,direc);
if(nosolve){break;}
l=nl;
k=nk;
direc=ndirec;
}
closegraph();
getch();
}
/*  跳到棋盘上某一格  */
void jump(int k,int l,int direc){
int i,j;
a[count].x=l;
a[count].y=k;
a[count].direc=direc;
board[k][l]=count+1;
if(count>=N*N-1){
/* outroute(fp); */
cartoon();
count++;
return;
}
else {
count++;
nl=l+v[direc];
nk=k+h[direc];
if(valid(nk,nl)){
ndirec=0;
return;
}
else{
count--;
while(count>=0&&a[count].direc>=7){
board[a[count].y][a[count].x]=0;
count--;
}
if(count<0){
printf("No solve!\n");
nosolve=1;
getch();
return;
}
nl=a[count].x;
nk=a[count].y;
ndirec=a[count].direc+1;
}
}
}

int valid(int i,int j){
if(i<N&&i>=0&&j<N&&j>=0&&board[j]==0)
return 1;
return 0;
}
/* 动画输出结果 */
void cartoon(){
int i,j,k,count=1,size;
void *buf;
cleardevice();
drawhorse();
size=imagesize(0,0,49,49);
buf=malloc(size);
getimage(0,0,49,49,buf);
cleardevice();
for(i=0;i<=N;i++){
line(100+50*i,100,100+50*i,100+50*N);
line(100,100+50*i,100+50*N,100+50*i);
}
for(k=0;k<N*N;k++){
for(i=0;i<N;i++)
for(j=0;j<N;j++)
if(board[j]==k+1){
setcolor(WHITE);
putimage(100+j*50,100+i*50,buf,XOR_PUT);
if(k==0)getch();
if(k==N*N-1){getch();return;}
delay(120000);
putimage(100+j*50,100+i*50,buf,XOR_PUT);
setcolor(BLUE);
setfillstyle(SOLID_FILL,BLUE);
bar(101+j*50,101+i*50,149+j*50,149+i*50);
     }
}
}
drawhorse(){
line(4,16,24,16);
line(12,16,6,22);
line(24,16,30,22);
line(24,16,32,8);
line(32,8,34,8);
line(34,8,38,12);
}

LOVEUNIX的carol发表：
超酷的马踏棋盘（在DOS下运行）

#include<stdio.h>
#include<graphics.h>
#include<conio.h>
#define PF cprintf("\n****************************************************\n");
int deltai[]={2,1,-1,-2,-2,-1,1,2};
int deltaj[]={1,2,2,1,-1,-2,-2,-1};
int board[8][8];


/* 求(i,j)的出口数和各出口号于a[] */
int exitn(int i,int j,int a[])
{ int i1,j1,k,count;
for(count=k=0;k<8;k++)
{ i1=i+deltai[k%8];
j1=j+deltaj[k%8];
if(i1>=0&&i1<8&&j1>=0&&j1<8&&board[i1][j1]==0)
a[count++]=k%8;
}
return count;
}


/* 选择下一个出口 */
int next(int i,int j)
{ int m,k,kk,min,a[8],b[8],temp;
m=exitn(i,j,a);                     /* 确定(i,j)的出口个数 */
if(m==0)
return -1;                          /* 没有出口 */
for(min=9,k=0;k<m;k++)              /* 逐一考察各个出口 */
{ temp=exitn(i+deltai[a[k>,j+deltaj[a[k>,b);
if(temp<min)                        /* 找出有最少出口数的出口 */
{ min=temp;kk=a[k];
}}
return kk;                           /* 返回选中的着法 */
}


/* 欢迎界面 */
void preface()
{
int graphdrive=VGA;
int graphmode=VGAHI;
initgraph(&graphdrive,&graphmode,"");
setbkcolor(5);
rectangle(0,9,638,475);
setfillstyle(1,9);
bar(10,30,637,10);
bar(1,10,20,339);
bar(10,290,637,339);
bar(618,320,637,30);
setfillstyle(1,4);
bar(40,50,590,250);
setcolor(10);
rectangle(40,50,591,250);
setcolor(12);
rectangle(60,70,570,230);
moveto(100,100);
settextstyle(0,0,3);
setcolor(10);
outtext("WELECOME TO USE!");
moveto(400,170);
settextstyle(1,0,2);
outtext("淮海工学院");
setcolor(WHITE);
line(0,340,638,340);
gotoxy(2,23);
printf("*软件设计要求: \n\n");
printf("           设计一个国际象棋的马踏遍棋盘的演示程序.\n\n");
printf("\n  *任意键进入*\n");
getch();
closegraph();
}


/* 程序的演示图 */
/*****************************************************************************/

/* 画棋盘 */
qipan()
{
int i;
for(i=0;i<9;i++)
{
line(100+i*50,50,100+i*50,450);
line(100,50+i*50,500,50+i*50);
}
}


/* 清屏 */
clears(i,j)
{
setfillstyle(1,BLACK);
bar(101+i*50,51+j*50,149+i*50,99+j*50);
}


/*  马根据所得结果的演示走法 */
void qipan1()
{
void *trp;
int graphdrive=VGA,i,j,c,k=1;
int graphmode=VGAHI;
initgraph(&graphdrive,&graphmode," ");
qipan();
setbkcolor(8);
setcolor(10);
circle(25,25,15);
setcolor(WHITE);
gotoxy(10,2);
printf("棋子＂马＂");
trp=(void*)malloc(sizeof(imagesize(9,9,41,41)));
getimage(9,9,41,41,trp);
do{
for(i=0;i<8;i++)
for(j=0;j<8;j++)
{
if(board[j]==k)
{
gotoxy(1,4);
printf("board[%d][%d]:",i,j);
qipan();
putimage(110+j*50,60+i*50,trp,COPY_PUT);
for(c=0;c<5;c++)
delay(900000);
clears(j,i);
k++;
break;
}
}
}while(k<65);
closegraph();
}
/*****************************************************************************/


void main()
{
int sx,sy,i,j,step,no,k;
char c;
clrscr();
preface();
while(1){
clrscr();
Loop1:  textcolor(GREEN);
cprintf("\nInput the sx[0--7] and sy[0--7]:");
printf("\n");
cprintf("      ( board[sx][sy] )");
printf("\n");
cprintf("  sx=");
scanf("%d",&sx);
printf("\n");
cprintf("  sy=");
scanf("%d",&sy);
if(sx>7||sx<0||sy>7||sy<0)
{ sound(1000);
delay(9999);
nosound();
textcolor(RED);
cprintf("Warning:\n");
cprintf("\n\n  The number must between 0 and 7 !!");
printf("\n");
cprintf("   Please input again!");
printf("\n");
goto Loop1;
}
clrscr();
textcolor(YELLOW);
cprintf("\nThe board[%d][%d] is:",sx,sy);
printf("\n");
do{
for(i=0;i<8;i++)
for(j=0;j<8;j++)
board[j]=0;
board[sx][sy]=1;
i=sx;
j=sy;
for(step=2;step<=64;step++)
{ if((no=next(i,j))==-1)
break;
i+=deltai[no];
j+=deltaj[no];
board[j]=step;
}
if(step>64)
break;
}while(step<=64);
textcolor(LIGHTRED);
printf("          ");
PF;
printf("\n          ");
textcolor(LIGHTBLUE);
for(i=0;i<8;i++)
{ for(j=0;j<8;j++)
cprintf("%6d",board[j]);
printf("\n\n          ");
}
textcolor(LIGHTRED);
PF;
printf("\n");
printf(" 是否查看图形演示 y/n\n");
c=getch();
if(c!='y'&&c!='Y')
goto Loop2;
qipan1();
printf("\n");
Loop2: textcolor(YELLOW);
cprintf("\n是否继续输入?(y/n)");
c=getch();
if(c!='Y'&&c!='y')
exit(0);
printf("\n");
}
}

LOVEUNIX的幽灵发表：

//加入了各点的权值，速度极快
//输入范例：
//1，1
#include "stdio.h"
#define N 8
int w=0;
int way1[8]={-2,-1,1,2, -1,-2,2, 1};
int way2[8]={ 1,2, 2,1,-2,-1,-1,-2};
int ch[N*N]={0};
int a[N*N+1][3]={0};
int dir[N][N][8];
int st=1;
char c='y';
int weight[N][N];


void caculate();
void dirctions();
void print();
int check(int i,int j);

void caculate() /*计算各点的权值*/
{
int i,j,k;
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
for(k=0;k<N;k++)
{
int x,y;
x=i+way1[k];
y=j+way2[k];
if(x>=1&&x<=N&&y>=1&&y<=N)
weight[i-1][j-1]++;
}

}

int check(int i,int j) /*检查(i,j)是否在棋盘内*/
{
if(i<1||i>8||j<1||j>8)
return 0;
return 1;
}


void directions() /*求出各点的最佳方向序列，即优先向权值小的方向*/
{
int i,j,k,m,n1,n2,x1,y1,x2,y2,way_1,way_2;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
{
for(k=0;k<8;k++)
dir[j][k]=k;
for(k=0;k<8;k++)
{

for(m=k+1;m<8;m++) /*对每个方向考察看有没有更好的*/
{
way_1=dir[j][k];
x1=i+way1[way_1];
y1=j+way2[way_1];
way_2=dir[j][m];
x2=i+way1[way_2];
y2=j+way2[way_2];
n1=check(x1+1,y1+1);
n2=check(x2+1,y2+1);
if(
( n1==0 && n2 ) || /*k方向不可达到，而m方向可达到*/
( n1 && n2&&weight[x1][y1]>weight[x2][y2] )/*都可达到但m方向权值小*/
)
{

dir[j][k]=way_2;
dir[j][m]=way_1; /*交换两个方向值*/
}
}
}






}

}


void print()
{
int x,y;

printf("\n------%d answer----\n",++w);

for(x=1;x<N+1;x++)
{
printf("\n");
for(y=1;y<N+1;y++)
printf("%2d ",ch[(x-1)*N+y-1]);
printf("\n");
}
printf("\nPress n to quit ,press any other key to continue.\n");

c=getchar(); /*询问是否继续输出结果*/
}

main()
{
int x,y,way,way0;
caculate();
directions();
printf("lease enter the row and column of the starting point.\n");
scanf("%d,%d",&a[1][0],&a[1][1]);/*输入行数和列数*/
getchar(); /*接收回车符*/
x=a[1][0],y=a[1][1];
ch[(x-1)*N+y-1]=1; /*在ch数组中对相应点赋值*/


while(1)
{
if(a[1][2]>=8) /*出发点的八个方向都已走过，表示所有的方法均已找出*/
break;

if(a[st][2]>=8) /*此点的八个方向都已走过，应该退回到上一次走的点*/
{
x=a[st][0];
y=a[st][1];
ch[(x-1)*N+y-1]=0; /*将这一点被走过的痕迹抹去*/
a[st][0]=a[st][1]=a[st][2]=0;
a[st-1][2]++; /*使上一次走的点走的方向发生变化*/
st--; /*步数减一*/
}

else /*此点的八个方向未全走过，应走此方向*/
{
way0=a[st][2];
a[st][2]++; /*确定下次应走的方向*/
x=a[st][0];
y=a[st][1];
way=dir[x-1][y-1][way0];
x=a[st][0]+way1[way];
y=a[st][1]+way2[way]; /*确定按这次的方向走应走到的x,y坐标*/


if(x<1||y<1||x>N||y>N||ch[(x-1)*N+y-1]!=0)/*此点不满足要求*/
continue;
ch[(x-1)*N+y-1]=++st; /*走到这一点 */
a[st][0]=x;
a[st][1]=y;
a[st][2]=0; /*标记这一步*/

if(st==N*N) /*步数已满*/
{
print(); /*输出结果*/
if(c=='n')
break;
ch[(x-1)*N+y-1]=0;
a[st][0]=a[st][1]=a[st][2]=0;
a[st-1][2]++;
st--; /*退回前一步*/
}
}
}
}