Re: [Dev-C++] reg-Knight's tour problem
Open Source C & C++ IDE for Windows
Brought to you by:
claplace
Menu
▾
▴
Re: [Dev-C++] reg-Knight's tour problem
|
From: Brian M. <str...@ho...> - 2002-03-08 20:35:48
|
Wow. For someone who is new to programming, you sure can pound out some
serious code. I think the biggest problem you have with this program is
that the algorithm is too complex (i'm not exactly sure what algorithm it is
you are working with, it just seems self-evident). There is a trick to the
knight's tour quandary that lends itself to a very simple algorithm.
The sure-fire way (has not failed my yet) to make it through the Knight's
Tour completely without getting stuck is to always move to one of the spaces
(out of a max of 8) which has the lowest "escape value." A square's escape
value is simply the number of squares that the knight can legally move from
after landing on that square. Here is an example of all the escape values
on the board for the first few moves of the knight's tour:
2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2
2 3 3 4 3 4 3 2
3 3 6 6 6 5 4 3
4 6 8 K 8 8 6 4
4 5 8 8 8 7 6 4
4 6 7 8 7 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2
2 3 K 4 3 4 3 2
2 3 6 6 5 5 4 3
4 5 8 X 8 8 6 4
4 5 8 8 8 7 6 4
4 6 7 8 7 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2
2 3 X 4 3 4 3 2
K 3 6 6 5 5 4 3
4 5 7 X 8 8 6 4
4 4 8 8 8 7 6 4
4 6 7 8 7 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2
2 3 X 4 3 4 3 2
X 3 5 6 5 5 4 3
4 5 7 X 8 8 6 4
4 K 8 8 8 7 6 4
4 6 7 7 7 8 6 4
3 6 7 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2
If you keep moving the knight accross the board in this manner, going to the
square with the lowest escape value, you will eventually complete the
knights tour.
So, the algorithm for the knights tour is simply:
while the knight's tour is not complete:
find all next possible squares to move to
find the square with the lowest "escape value"
move there
loop
Don't ask me why this works, i just know it does.
>From: "Mohammed Riyaz" <p_m...@ho...>
>To: dev...@li...
>Subject: [Dev-C++] reg-Knight's tour problem
>Date: Thu, 07 Mar 2002 12:00:22 +0000
>
>hey,
>I had a look at the code sent in. Am new to programming, my code sux when
>compared to that. :D .If any one of you cud fix this code ,help me
>out.
>-Riyaz
>
>#include <iostream.h>
>#include <stdlib.h>
>#include <process.h>
>class knight
> {
> int chess[8][8],location[65][10],denied[64];
> int row_loc,pos,i,j;
> public:
> knight();
> void assignment(void);
> int value(int);
> void refresh(void);
> int append(int ,int);
> };
>knight::knight(void)
> {
> row_loc=-1;
> i=j=0;
> for(int m=0;m<8;m++)
> for(int n=0;n<8;n++)
> chess[m][n]=0;
> for(int m=0;m<65;m++)
> for(int n=0;n<10;n++)
> location[m][n]=0;
> for(int m=0;m<64;m++)
> denied[m]=99;
> assignment();
> }
>void knight::assignment(void)
> {
> chess[i][j]=1;
> refresh();
> pos=value(j+(8*i));
> i=pos/8;
> j=pos%8;
> assignment();
> }
>int knight::value(int val)
> {
> row_loc++;
> int temp=1;
> int lock,ii,jj;
> location[row_loc][0]=val;
> ii=val/8;
> jj=val%8;
> if(jj==0)
> {
> if(ii>=1)
> {
> if(ii>=2)
> {lock=append(val-15,temp);if(lock==0) {temp++;}}
> lock=append(val-6,temp);if(lock==0) {temp++;}
> }
> if(ii<=6)
> {
> if(ii<=5)
> {lock=append(val+17,temp);if(lock==0) {temp++;}}
> lock=append(val+10,temp);if(lock==0) {temp++;}
> }
> }
> if(jj==7)
> {
> if(ii>=1)
> {
> if(ii>=2)
> {lock=append(val-17,temp);if(lock==0) {temp++;}}
> lock=append(val-10,temp);if(lock==0) {temp++;}
> }
> if(ii<=6)
> {
> if(ii<=5)
> {lock=append(val+15,temp);if(lock==0) {temp++;}}
> lock=append(val+6,temp);if(lock==0) {temp++;}
> }
> }
> if(jj==1)
> {
> if(ii>=1)
> {
> if(ii>=2)
> {
> lock=append(val-15,temp);if(lock==0) {temp++;}
> lock=append(val-17,temp);if(lock==0) {temp++;}
> }
> lock=append(val-6,temp);if(lock==0) {temp++;}
> }
> if(ii<=6)
> {
> if(ii<=5)
> {
> lock=append(val+17,temp);if(lock==0) {temp++;}
> lock=append(val+15,temp);if(lock==0) {temp++;}
> }
> lock=append(val+10,temp);if(lock==0) {temp++;}
> }
> }
> if(jj==6)
> {
> if(ii>=1)
> {
> if(ii>=2)
> {
> lock=append(val-15,temp);if(lock==0) {temp++;}
> lock=append(val-17,temp);if(lock==0) {temp++;}
> }
> lock=append(val-10,temp);if(lock==0) {temp++;}
> }
> if(ii<=6)
> {
> if(ii<=5)
> {
> lock=append(val+17,temp);if(lock==0) {temp++;}
> lock=append(val+15,temp);if(lock==0) {temp++;}
> }
> lock=append(val+6,temp);if(lock==0) {temp++;}
> }
> }
> if(jj>1 && jj<6)
> {
> if(ii>=1)
> {
> if(ii>=2)
> {
> lock=append(val-17,temp);if(lock==0) {temp++;}
> lock=append(val-15,temp);if(lock==0) {temp++;}
> }
> lock=append(val-10,temp);if(lock==0) {temp++;}
> lock=append(val-6,temp);if(lock==0) {temp++;}
> }
> if(ii<=6)
> {
> if(ii<=5)
> {
> lock=append(val+15,temp);if(lock==0) {temp++;}
> lock=append(val+17,temp);if(lock==0) {temp++;}
> }
> lock=append(val+6,temp);if(lock==0) {temp++;}
> lock=append(val+10,temp);if(lock==0) {temp++;}
> }
> }
> lock=append(-1,temp);
> code:
> if(location[row_loc][1]==-1)
> {
> ii=location[row_loc][0]/8;
> jj=location[row_loc][0]%8;
> chess[ii][jj]=0;
> row_loc--;
> if(row_loc<0) {cout<<"NO SOLUTION";system("pause");exit(0);}
> for(int m=1;m<9;m++)
> location[row_loc][m]=location[row_loc][m+1];
> goto code;
> }
> return location[row_loc][1];
> }
>void knight::refresh(void)
> {
> int l,tot;
> l=tot=0;
> for(int m=0;m<64;m++)
> denied[m]=99;
> for(int m=0;m<8;m++)
> {
> for(int n=0;n<8;n++)
> {
> if(chess[m][n]==1)
> {
> if(l==63)
> {
> cout<<"RESULT :"<<endl;
> for(int k=0;k<64;k++)
> cout<<denied[k]<<" ";
> system("pause");
> }
> tot=n+(8*m);
> denied[l]=tot;
> l++;
> }
> }
> }
> }
>int knight::append(int val1,int temp1)
> {
> int lock=0;
> for(int m=0;m<64;m++)
> if(denied[m]==val1)
> {lock=1;break;}
> if(!lock)
> location[row_loc][temp1]=val1;
> return lock;
> }
>void main()
> {knight k;}
>
>
>
>_________________________________________________________________
>MSN Photos is the easiest way to share and print your photos:
>http://photos.msn.com/support/worldwide.aspx
>
>
>_______________________________________________
>Dev-cpp-users mailing list
>Dev...@li...
>https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
_________________________________________________________________
Chat with friends online, try MSN Messenger: http://messenger.msn.com
|
