qq空间老贴转载-骑士周游问题我的做法
自己写的，也做了优化但效果不大，求出所有结果是世界级的难题，貌似没什么好办法SIN<8时很快 >=8很慢，无结果，改进法在后面#include <conio.h>
#include <iostream>
#include <time.h>using namespace std;#define SIN 8
#define MAX SIN*SIN
int sum=0;
struct POINT
{
int x;
int y;
};
class HorsePuzzle
{
POINT horse;
boolpermit;//防越界
public:
HorsePuzzle();
void printOut();
bool IsValid(int n);
void placeHorse(int n,int x,int y);
};HorsePuzzle::HorsePuzzle()
{
int i,j;
for(i=0;i<MAX;i++)
{
horse.x=0;
horse.y=0;
*((bool*)permit+i)=true;
}
for(i=2;i<SIN+2;i++)
{
for(j=0;j<SIN+2;j++)
{
permit=true;//中间位置允许放置
}
}
//0/1/SIN+2/SIN+3行列不允许放置
for(i=0;i<SIN+4;i++)
{
permit=false;
permit=false;
permit=false;
permit=false;
permit=false;
permit=false;
permit=false;
permit=false;
}
}void HorsePuzzle::printOut()
{
int data,i,j;
cout<<"解法"<<++sum<<':'<<endl;
for(i=0;i<MAX;i++)
{
data.x].y]=i;
}
for(i=0;i<SIN;i++)
{
for(j=0;j<SIN;j++)
{
cout<<data<<'\t';
}
cout<<endl;
}
cout<<endl;
}void HorsePuzzle::placeHorse(int n,int x,int y)
{
horse.x=x;
horse.y=y;
if(permit.x+2].y+2])
{
permit=false;
n++;
if(n == MAX)
{
printOut();
permit=true;
return;
}placeHorse(n,x-2,y-1);
placeHorse(n,x-1,y-2);
placeHorse(n,x+1,y-2);
placeHorse(n,x+2,y-1);
placeHorse(n,x-2,y+1);
placeHorse(n,x-1,y+2);
placeHorse(n,x+1,y+2);
placeHorse(n,x+2,y+1);permit=true;
}
}void main()
{
time_t begin=time(NULL);
HorsePuzzle horse;
horse.placeHorse(0,0,0);
cout<<"共"<<sum<<"组解,时间:"<<time(NULL)-begin<<endl;
}今天看了《c/c++常用算法》这本书，10.8节也是骑士周游问题，我把他的代码改成通用的，数组维数可以变化，代码如下：#include <stdio.h>
#include <stdlib.h>
#define MYSIZE 7
typedef struct
{
int x;
int y;
}Coordinate;
int chessboard;
int curstep;
Coordinate fangxiang={{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};
void Move(Coordinate curpos)
{
Coordinate next;
int i,j;
if(curpos.x < 0 || curpos.x > MYSIZE-1 || curpos.y < 0 || curpos.y > MYSIZE-1)
return;
if(chessboard)
return;
chessboard=curstep;
curstep++;
if(curstep > MYSIZE*MYSIZE)
{
for(i=0;i<MYSIZE;i++)
{
for(j=0;j<MYSIZE;j++)
{
printf("%5d",chessboard);
}
printf("\n");
}
exit(0);
}
else
{
for(i=0;i<8;i++)
{
next.x=curpos.x+fangxiang.x;
next.y=curpos.y+fangxiang.y;
if(next.x < 0 || next.x > MYSIZE-1 || next.y < 0 || next.y > MYSIZE-1)
{
}
else
{
Move(next);
}
}
}
chessboard=0;
curstep--;
}
void main()
{
int i,j;
Coordinate start;
scanf("%d%d",&start.x,&start.y);
if(start.x < 1 || start.y < 1 || start.x > MYSIZE || start.y > MYSIZE)
{
printf("error");
exit(0);
}
for(i=0;i<MYSIZE;i++)
{
for(j=0;j<MYSIZE;j++)
{
chessboard=0;
}
}
start.x--;
start.y--;
curstep=1;
Move(start);
}
结果发现他的程序居然在MYSIZE=8时很快找到了答案。。。百思不得其解，遂看了一下他的程序。
乍一看，觉得写得很一般，效率应该没我的高，验证了一下MYSIZE=7的时候都卡，证明了我的想法
，因为我用的判断直接是判断数组，不需要函数，于是我找原因，
开始的时候我发现他传的参数类型是coordinate，在底层实现的时候，其实传的参数是2个int了。考虑到压栈可能耗费时间，
所以我把我的程序中的placeHorse递归也从3个参数改成2个参数，结果发现还是没结果，我又找，发现书中代码有fangxiang这个数组，
用来存储8个方向，在函数中以for循环遍历，我想，我直接手写的，你用for循环永远不可能比我快啊，，不解，肯定还有猫腻，
果然不出我所料，后来我发现 数组为{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}，这8个方向为顺时针排列，再看我的，明白了，
原来出结果的速度与这个顺序也是有关的，打个比方，起始点选0,0的话，如果前几个搜索方向为横向和纵向数轴的相反方向，则由于方向问题导致需要遍历到根部，而如果为数轴正方向的话，开始的搜索方向总是正确的，循环是从开始遍历的，所以开始错的越少，效率越高，从根部循环越容易找到。。。 最后换用他的数组，很快得到结果。
不过话说到这里，要想遍历所有解，还是遍历不出来的，或者说很慢很慢，世界难题没那么好解。
还有，给定初始位置，其实可以选最合适的初始方向的。。。不过我没继续研究了到此为止，最后最优代码如下：
#include <conio.h>#include <iostream>
#include <time.h>
using namespace std;
#define SIN 8
#define MAX SIN*SIN
int sum=0;
struct POINT
{
int x;
int y;
};
class HorsePuzzle
{
POINT horse;
boolpermit;//防越界
public:
HorsePuzzle();
void printOut();
void placeHorse(/*int n,*/int x,int y);
};
HorsePuzzle::HorsePuzzle()
{
int i,j;
for(i=0;i<MAX;i++)
{
horse.x=0;
horse.y=0;
*((bool*)permit+i)=true;
}
for(i=2;i<SIN+2;i++)
{
for(j=0;j<SIN+2;j++)
{
permit=true;//中间位置允许放置
}
}
//0/1/SIN+2/SIN+3行列不允许放置
for(i=0;i<SIN+4;i++)
{
permit=false;
permit=false;
permit=false;
permit=false;
permit=false;
permit=false;
permit=false;
permit=false;
}
}
void HorsePuzzle::printOut()
{
int data,i,j;
cout<<"解法"<<++sum<<':'<<endl;
for(i=0;i<MAX;i++)
{
data.x].y]=i;
}
for(i=0;i<SIN;i++)
{
for(j=0;j<SIN;j++)
{
cout<<data<<'\t';
}
cout<<endl;
}
cout<<endl;
}
int n=0;
void HorsePuzzle::placeHorse(int x,int y)
{
if(permit)
{
horse.x=x;
horse.y=y;
n++;
permit=false;
if(n != MAX)
{
placeHorse(x-2,y+1);
placeHorse(x-1,y+2);
placeHorse(x+1,y+2);
placeHorse(x+2,y+1);
placeHorse(x+2,y-1);
placeHorse(x+1,y-2);
placeHorse(x-1,y-2);
placeHorse(x-2,y-1);
}
else
{
printOut();
}
permit=true;
n--;
}
}
void main()
{
time_t begin=time(NULL);
HorsePuzzle horse;
horse.placeHorse(0,0);
cout<<"共"<<sum<<"组解,时间:"<<time(NULL)-begin<<endl;
}
如果你还能提出效率高出很多的建议，并可以实现求所有解的更快方法，欢迎和我讨论！！！
页:
[1]