qq空间老贴转载-骑士周游问题我的做法

元始天尊

自己写的，也做了优化但效果不大，求出所有结果是世界级的难题，貌似没什么好办法

SIN<8时很快 >=8很慢，无结果，

改进法在后面

1. [/align][align=left]#include <conio.h>
   
2. #include <iostream>
   
3. #include <time.h>[/align][align=left]using namespace std;[/align][align=left]#define SIN 8
   
4. #define MAX SIN*SIN
   
5. int sum=0;[/align][align=left]
   
6. struct POINT
   
7. {
   
8. int x;
   
9. int y;
   
10. };[/align]
    
11. [align=left]class HorsePuzzle
    
12. {
    
13. POINT horse[MAX];
    
14. bool  permit[SIN+4][SIN+4];//防越界
    
15. public:
    
16. HorsePuzzle();
    
17. void printOut();
    
18. bool IsValid(int n);
    
19. void placeHorse(int n,int x,int y);
    
20. };[/align][align=left]HorsePuzzle::HorsePuzzle()
    
21. {
    
22. int i,j;
    
23. for(i=0;i<MAX;i++)
    
24. {
    
25.   horse[i].x=0;
    
26.   horse[i].y=0;
    
27.   *((bool*)permit+i)=true;
    
28. }
    
29. for(i=2;i<SIN+2;i++)
    
30. {
    
31.   for(j=0;j<SIN+2;j++)
    
32.   {
    
33.    permit[i][j]=true;//中间位置允许放置
    
34.   }
    
35. }
    
36. //0/1/SIN+2/SIN+3行列不允许放置
    
37. for(i=0;i<SIN+4;i++)
    
38. {
    
39.   permit[0][i]=false;
    
40.   permit[1][i]=false;
    
41.   permit[SIN+2][i]=false;
    
42.   permit[SIN+3][i]=false;
    
43.   permit[i][0]=false;
    
44.   permit[i][1]=false;
    
45.   permit[i][SIN+2]=false;
    
46.   permit[i][SIN+3]=false;
    
47. }
    
48. }[/align][align=left]void HorsePuzzle::printOut()
    
49. {
    
50. int data[SIN][SIN],i,j;
    
51. cout<<"解法"<<++sum<<':'<<endl;
    
52. for(i=0;i<MAX;i++)
    
53. {
    
54.   data[horse[i].x][horse[i].y]=i;
    
55. }
    
56. for(i=0;i<SIN;i++)
    
57. {
    
58.   for(j=0;j<SIN;j++)
    
59.   {
    
60.    cout<<data[i][j]<<'\t';
    
61.   }
    
62.   cout<<endl;
    
63. }
    
64. cout<<endl;
    
65. }[/align][align=left]void HorsePuzzle::placeHorse(int n,int x,int y)
    
66. {
    
67. horse[n].x=x;
    
68. horse[n].y=y;
    
69. if(permit[horse[n].x+2][horse[n].y+2])
    
70. {
    
71.   permit[x+2][y+2]=false;
    
72.   n++;
    
73.         if(n == MAX)
    
74.   {
    
75.    printOut();
    
76.    permit[x+2][y+2]=true;
    
77.    return;
    
78.   }[/align][align=left]  placeHorse(n,x-2,y-1);
    
79.   placeHorse(n,x-1,y-2);
    
80.   placeHorse(n,x+1,y-2);
    
81.   placeHorse(n,x+2,y-1);
    
82.   placeHorse(n,x-2,y+1);
    
83.   placeHorse(n,x-1,y+2);
    
84.   placeHorse(n,x+1,y+2);
    
85.   placeHorse(n,x+2,y+1);[/align][align=left]  permit[x+2][y+2]=true;
    
86. }
    
87. }[/align][align=left]void main()
    
88. {
    
89. time_t begin=time(NULL);
    
90. HorsePuzzle horse;
    
91. horse.placeHorse(0,0,0);
    
92. cout<<"共"<<sum<<"组解,时间:"<<time(NULL)-begin<<endl;
    
93. }[/align][align=left]

复制代码

今天看了《c/c++常用算法》这本书，10.8节也是骑士周游问题，我把他的代码改成通用的，数组维数可以变化，代码如下：

1. [/align]#include <stdio.h>
   
2. #include <stdlib.h>
   
3. #define MYSIZE 7
   
4. typedef struct
   
5. {
   
6. int x;
   
7. int y;
   
8. }Coordinate;
   
9. int chessboard[MYSIZE][MYSIZE];
   
10. int curstep;
    
11. Coordinate fangxiang[8]={{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};
    
12. void Move(Coordinate curpos)
    
13. {
    
14. Coordinate next;
    
15. int i,j;
    
16. if(curpos.x < 0 || curpos.x > MYSIZE-1 || curpos.y < 0 || curpos.y > MYSIZE-1)
    
17. return;
    
18. if(chessboard[curpos.x][curpos.y])
    
19. return;
    
20. chessboard[curpos.x][curpos.y]=curstep;
    
21. curstep++;
    
22. if(curstep > MYSIZE*MYSIZE)
    
23. {
    
24. for(i=0;i<MYSIZE;i++)
    
25. {
    
26. for(j=0;j<MYSIZE;j++)
    
27. {
    
28. printf("%5d",chessboard[i][j]);
    
29. }
    
30. printf("\n");
    
31. }
    
32. exit(0);
    
33. }
    
34. else
    
35. {
    
36. for(i=0;i<8;i++)
    
37. {
    
38. next.x=curpos.x+fangxiang[i].x;
    
39. next.y=curpos.y+fangxiang[i].y;
    
40. if(next.x < 0 || next.x > MYSIZE-1 || next.y < 0 || next.y > MYSIZE-1)
    
41. {
    
42. 
    
43. }
    
44. else
    
45. {
    
46. Move(next);
    
47. }
    
48. }
    
49. }
    
50. chessboard[curpos.x][curpos.y]=0;
    
51. curstep--;
    
52. }
    
53. 
    
54. void main()
    
55. {
    
56. int i,j;
    
57. Coordinate start;
    
58. scanf("%d%d",&start.x,&start.y);
    
59. if(start.x < 1 || start.y < 1 || start.x > MYSIZE || start.y > MYSIZE)
    
60. {
    
61. printf("error");
    
62. exit(0);
    
63. }
    
64. for(i=0;i<MYSIZE;i++)
    
65. {
    
66. for(j=0;j<MYSIZE;j++)
    
67. {
    
68. chessboard[i][j]=0;
    
69. }
    
70. }
    
71. start.x--;
    
72. start.y--;
    
73. curstep=1;
    
74. Move(start);
    
75. }
    
76. [align=left]

复制代码

结果发现他的程序居然在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的话，如果前几个搜索方向为横向和纵向数轴的相反方向，则由于方向问题导致需要遍历到根部，而如果为数轴正方向的话，开始的搜索方向总是正确的，循环是从开始遍历的，所以开始错的越少，效率越高，从根部循环越容易找到。。。 最后换用他的数组，很快得到结果。
不过话说到这里，要想遍历所有解，还是遍历不出来的，或者说很慢很慢，世界难题没那么好解。
还有，给定初始位置，其实可以选最合适的初始方向的。。。不过我没继续研究了到此为止，最后最优代码如下：

1. [/align][align=left]#include <conio.h>[/align]#include <iostream>
   
2. #include <time.h>
   
3. using namespace std;
   
4. 
   
5. #define SIN 8
   
6. #define MAX SIN*SIN
   
7. int sum=0;
   
8. 
   
9. struct POINT
   
10. {
    
11. int x;
    
12. int y;
    
13. };
    
14. 
    
15. class HorsePuzzle
    
16. {
    
17. POINT horse[MAX];
    
18. bool  permit[SIN+4][SIN+4];//防越界
    
19. public:
    
20. HorsePuzzle();
    
21. void printOut();
    
22. void placeHorse(/*int n,*/int x,int y);
    
23. };
    
24. 
    
25. HorsePuzzle::HorsePuzzle()
    
26. {
    
27. int i,j;
    
28. for(i=0;i<MAX;i++)
    
29. {
    
30. horse[i].x=0;
    
31. horse[i].y=0;
    
32. *((bool*)permit+i)=true;
    
33. }
    
34. for(i=2;i<SIN+2;i++)
    
35. {
    
36. for(j=0;j<SIN+2;j++)
    
37. {
    
38. permit[i][j]=true;//中间位置允许放置
    
39. }
    
40. }
    
41. //0/1/SIN+2/SIN+3行列不允许放置
    
42. for(i=0;i<SIN+4;i++)
    
43. {
    
44. permit[0][i]=false;
    
45. permit[1][i]=false;
    
46. permit[SIN+2][i]=false;
    
47. permit[SIN+3][i]=false;
    
48. permit[i][0]=false;
    
49. permit[i][1]=false;
    
50. permit[i][SIN+2]=false;
    
51. permit[i][SIN+3]=false;
    
52. }
    
53. }
    
54. 
    
55. void HorsePuzzle::printOut()
    
56. {
    
57. int data[SIN][SIN],i,j;
    
58. cout<<"解法"<<++sum<<':'<<endl;
    
59. for(i=0;i<MAX;i++)
    
60. {
    
61. data[horse[i].x][horse[i].y]=i;
    
62. }
    
63. for(i=0;i<SIN;i++)
    
64. {
    
65. for(j=0;j<SIN;j++)
    
66. {
    
67. cout<<data[i][j]<<'\t';
    
68. }
    
69. cout<<endl;
    
70. }
    
71. cout<<endl;
    
72. }
    
73. 
    
74. int n=0;
    
75. 
    
76. void HorsePuzzle::placeHorse(int x,int y)
    
77. {
    
78. if(permit[x+2][y+2])
    
79. {
    
80. horse[n].x=x;
    
81. horse[n].y=y;
    
82. n++;
    
83. permit[x+2][y+2]=false;
    
84. 
    
85.         if(n != MAX)
    
86. {
    
87. placeHorse(x-2,y+1);
    
88. placeHorse(x-1,y+2);
    
89. placeHorse(x+1,y+2);
    
90. placeHorse(x+2,y+1);
    
91. placeHorse(x+2,y-1);
    
92. placeHorse(x+1,y-2);
    
93. placeHorse(x-1,y-2);
    
94. placeHorse(x-2,y-1);
    
95. }
    
96. else
    
97. {
    
98. printOut();
    
99. }
    
100. 
     
101. permit[x+2][y+2]=true;
     
102. n--;
     
103. }
     
104. }
     
105. 
     
106. void main()
     
107. {
     
108. time_t begin=time(NULL);
     
109. HorsePuzzle horse;
     
110. horse.placeHorse(0,0);
     
111. cout<<"共"<<sum<<"组解,时间:"<<time(NULL)-begin<<endl;
     
112. }
     
113. 
     
114. [align=left]

复制代码

如果你还能提出效率高出很多的建议，并可以实现求所有解的更快方法，欢迎和我讨论！！！