我想解决骑士巡回问题。当我搜索时，我发现有很多解决方法。事实上，有非常高效和快速的算法来解决它，包括Warnsdoff的规则。但实际上，我从未想过复制任何一个算法。然后我看到了一个视频描述了一种在纸上解决这个问题的方法。视频链接是www.youtube.com%2Fwatch%3Fv%3DdWM5pKYZCHw&b=28。
我不知道那种方法是否已经被使用，但我决定跟随那种方法。这是算法的链接。
首先，我将解释一下解决骑士巡回问题的方法。我们假设有一个8*8的棋盘，并且我们已经给出了骑士的起始位置。现在，我将棋盘分成4个系统的盒子。左菱形系统、右菱形系统、左方系统、右方系统。首先，我将检查骑士在开始时处于哪个系统中。然后我将首先填充该系统，然后移动到下一个系统。为了填充该系统，我将首先进入当前块。整个棋盘被分成4个块(每个块都是(4*4)，如您从视频中所见)。填充完该块后，我将移动到下一个块，依此类推。在填充所有块之后，我将移动到下一个系统。现在，我几乎做到了。我制作了一些函数，用于查找当前块、当前系统、是否可以进行移动、骑士在块中的下一个移动、块移位和最后系统移位。现在，我正在使用一个3D数组来存储有关每个盒子的一些重要信息。数组大小为[8][8][2]。在每个盒子的第一个元素中，我存储系统号，即我已经为每个四个系统分配了特定的数字以后识别它们。左菱形系统=1，右菱形系统=2，左方系统=3，右方系统=4。在每个盒子的下一个元素中，我存储有关该盒子的信息，无论我是否已经进入该盒子。在开始时，这些都是零，但随着我的进展，我会使它们成为1，表示我已经移动了该盒子。现在，我正在预测试模式下，并且在nextmove函数中遇到了一些逻辑问题。其他函数都运行完美。我在此处提供编码，但我只提供重要部分的选定代码。有一件事我忘记说的是，我正在一个名为current position的数组中存储骑士的当前位置，并且我将随着移动而更改当前位置。在整个代码中，m表示骑士的当前行，k表示当前列。以下是代码。
此外，movepossible函数也运行得很好。现在的问题是当我调用下一个move函数时，它可以正确地进行第一和第二次移动，但无法进行块中的第三次移动。实际上，在特定系统的块中有三个移动，换句话说，它无法移动到块中的最后一个方框中。它不依赖于起始位置，对于每个起始位置都会出现这种情况。现在我已经花了很多时间找出问题所在，但没有找到。因此，请告诉我问题出在哪里。如果您对改进逻辑和代码有任何建议，请提出。当我输入起始位置（4,3）时，代码的输出如下：
但是输出应该像这样（仅适用于（4,3））：
#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;
}
此外，movepossible函数也运行得很好。现在的问题是当我调用下一个move函数时，它可以正确地进行第一和第二次移动，但无法进行块中的第三次移动。实际上，在特定系统的块中有三个移动，换句话说，它无法移动到块中的最后一个方框中。它不依赖于起始位置，对于每个起始位置都会出现这种情况。现在我已经花了很多时间找出问题所在，但没有找到。因此，请告诉我问题出在哪里。如果您对改进逻辑和代码有任何建议，请提出。当我输入起始位置（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
但是输出应该像这样（仅适用于（4,3））：
6,2 //first move
7,0 //second move
5,1 //third move
current block is3 //these are working perfect.
movepossible is1
current system2