Question
I wanted to solve knights tour puzzle. When I searched it I come to know that there are many ways of solving it. In fact very efficient and fast algorithms for solving it including Warnsdoff's rule. But actually I never wanted to copy any of them. Then I saw a video describing a way of solving this on paper.Link of the video is www.youtube.com%2Fwatch%3Fv%3DdWM5pKYZCHw&b=28 I do not know if that way is already used or not but I decided to follow that. This is the link of algorithm. Firstly I will explain about that way of solving the knights tour. We suppose that we have an 8*8 chess board and we have given the starting position of the knight. Now I have subdivided the board into 4 systems of boxes. Left diamond system, right diamond system, left square system, right square system. First I will check that in which system the knight is in start. Then I will fill that system first and then I will move to the next one. And for filling that system I will first move into the current block. The whole board is subdivided into 4 blocks(each block is (4*4) as you can see form the video. After filling that block I will move to the next block and so on. And after filling all blocks I will move to the next system. Now I have almost made it. I have made certain functions for finding current block, current system, whether a move is possible or not, next move of knight in block, block shifting and finally system shifting. Now I am using a 3D array to store some important information about each box. Array size is [8][8][2]. In the first element of each box I am storing the system number i.e I have assigned specific numbers to each of the four systems to recognize them later. Left diamond system=1, right diamond system=2, left square system=3, right square system=4. And in the next element of each box I am storing information about the box whether I have already moved into it or not. In the start these are all zero but as I will progress I will make them 1 which box I have moved. Now I am in the pre testing mode and I am facing some logical problem in the nextmove function. Rest of the functions are working perfect. I am giving the coded here but I am only giving the selected portion of the code which is important. One thing I forgot is that I am storing the current position of knight in an array named current position and I will change the current position as I move. In the whole code m represents the current row of the knight and k represents the current column. Here is the code
https://stackoverflow.com/questions/19935978
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian#include<iostream>
using namespace std;
// zero element for storing current row and 1 element for current column of knight.
int currentposition[2]={0,0};
// 3d array for storing information
int l[8][8][2]={ {{1,0} , {3,0} , {4,0} , {2,0} , {1,0} , {3,0} , {4,0} ,{2,0}},
{{4,0} , {2,0} , {1,0} , {3,0} , {4,0} , {2,0} , {1,0} , {3,0}},
{{3,0} , {1,0} , {2,0} , {4,0} , {3,0} , {1,0} , {2,0} , {4,0}},
{{2,0} , {4,0} , {3,0} , {1,0} , {2,0} , {4,0} , {3,0} , {1,0}},
{{1,0} , {3,0} , {4,0} , {2,0} , {1,0} , {3,0} , {4,0} , {2,0}},
{{4,0} , {2,0} , {1,0} , {3,0} , {4,0} , {2,0} , {1,0} , {3,0}},
{{3,0} , {1,0} , {2,0} , {4,0} , {3,0} , {1,0} , {2,0} , {4,0}},
{{2,0} , {4,0} , {3,0} , {1,0} , {2,0} , {4,0} , {3,0} ,{1,0}}};
//function for finding current block
int currentblock(int m , int k) // m and k are current box co-ordinates
{
int block;
if ((m>=0 && m<=3) && (k>=0 && k<=3))
block= 1;
if ((m>=0 && m<=3) && (k>3 && k<=7))
block= 2;
if ((m>3 && m<=7) && (k>=0 && k<=3))
block= 3;
if ((m>3 && m<=7) && (k>3 && k<=7))
block= 4;
return block;
}
//function telling that move is possible or not.
int movepossible(int m,int k,int i, int j)
// m and k represents current position and I and j represents the wanted position.
{
int ans=0;
if ( ( (m-i)==1 && (k-j)==2 ) || ( (m-i)==2 && (k-j)==1 ) )
ans=1;
if ( ( (m-i)==-1 && (k-j)==-2 ) || ( (m-i)==-2 && (k-j)==-1 ) )
ans=1;
if ( ( (m-i)==-1 && (k-j)==2 ) || ( (m-i)==2 && (k-j)==-1 ) )
ans=1;
if ( ( (m-i)==1 && (k-j)==-2 ) || ( (m-i)==-2 && (k-j)==1 ) )
ans=1;
return ans;
}
//function to find the current system.
int currentsystem(int l[8][8][2],int m,int )
{
int ans=l[m][k][0];
return ans;
}
// function which move the knight in the specified box. 1 time calling of function moves knight one time.
void nextmove(int l[8][8][2],int m,int k)
{ int block=currentblock(m,k);
int system=currentsystem(l,m,k);
int a,b,c,d;
a,b,c,d, represents the range of the rows and columns for a specified block. There is no problem in this section I think.
if (block==1)
{ a=0;b=3;c=0;d=3;}
else
{ if (block==2)
{ a=0;b=3;c=4;d=3;}
else
{ if (block==3)
{ a=4;b=7;c=0;d=3;}
else
{ a=4;b=7;c=4;d=7;}
}
}
// now this will search the whole block for next move and it will check 3 conditions to move to a box.
for ( int rowmin=a; rowmin<=b ; rowmin+=1)
{ for (int colmin=c ;colmin<=d;colmin+=1)
{
if (l[rowmin][colmin][1]!=1) //this checks if we have already moved into that box or not
{ if (l[rowmin][colmin][0]==system)
// this checks if box belongs to current system.
{ if (movepossible(m,k,rowmin,colmin))
//this checks if move is possible or not
{
currentposition[0]=rowmin;
// if all 3 conditions are satisfied knight will move to the box.
currentposition[1]=colmin;
l[rowmin][colmin][1]=1;
//this will change the value of the box to 1 in which we have moved.
}
}
}
}
}
}
int main()
{ //int backtrackarray[8][8][2];
int m,k,i,j;
cout<<"Enter m:"; //Enters starting position(row)
cin>>m;
cout<<"Enter k:";
// Enters starting position(column)
cin>>k;
currentposition[0]=m;
// this updates the current position of knight in the currentposition array
currentposition[1]=k;
l[m][k][1]=1;
for (int u=0 ; u<3; u++) // this loop is for testing of the nextmove function.
{
nextmove(l,currentposition[0],currentposition[1]);
//calling of nextmove function.
cout<<currentposition[0]<<" ,"<<currentposition[1];
//displaying current position.
cout<<endl;
}
cout<<"current block is"<<currentblock(m,k)<<endl; //testing the current block function. Working perfect.
cout<<"current system"<<currentsystem(l,m,k)<<endl; //testing of current system function. Working perfect.
return 0;
}
Moreover, movepossible function is also working perfect. Now problem is when I calls the next move function, It makes first and second move correctly but it does not make the third move in the block. In fact there are total three moves in a block of a particular system, In other words it does not move to the last one box in block. It does not depends on starting position, for every starting position it is behaving like this. Now I have spent lot of time to find what is the problem but did not find it. So please tell me where is the problem. Also if you have any suggestions to improve the logic and code. The output of the code is like this when I enter starting position (4,3)
6,2 //first move
7,0 //second move
7,0 //not moved to the third one which is (5,1)
current block is3 //these are working perfect.
movepossible is1
current system2
But output should be like this (for (4,3) only)
6,2 //first move
7,0 //second move
5,1 //third move
current block is3 //these are working perfect.
movepossible is1
current system2
Solution 2
After a long debugging i come to know that
if (l[rowmin][colmin][1]!=1) //this checks if we have already moved into that box or not
was only responsible for the whole problem. The problem was that i was writing it inside the loop and when the function searches for the next move it changes the value to 1 before the final decision. When i put it out of the curly braces the problem was solved.
OTHER TIPS
A quick debug lead me to the following line failing for your case:
if (l[rowmin][colmin][1]!=1) //this checks if we have already moved into that box or not
