所以,简而言之,我正在研究骑士的巡回演出。如果你不知道那是什么,马就会被放到棋盘上,你必须将它移动到棋盘上的每个位置恰好一次。我正在使用递归函数,但无法让我的回溯工作。我可以在 5x5 板上完成 22 步,但程序不会备份并尝试不同的路径。我只发布了我的代码的递归部分(抱歉它有点长)任何见解都会非常有帮助。非常感谢!
`bool findPath ( int board[][boardSize + 4], int &currRow, int &currCol, int &currMove,int boardSize )
{
int i, j;
bool foundSpot;
board[currRow][currCol] = currMove;
if ( currMove == boardSize * boardSize )
return true;
for ( i = 0; i < boardSize + 4; i++ )
{
for ( j = 0; j < boardSize + 4; j++ )
cout << setw (3) << board[i][j];
cout<<endl;
}
cout << endl;
if ( board[currRow - 2][currCol - 1] == 0 )
{
currMove += 1;
board[currRow - 2][currCol - 1] = currMove;
currRow -= 2;
currCol -= 1;
if ( findPath( board, currRow, currCol, currMove, boardSize ) )
return true;
}
if ( board[currRow - 2][currCol + 1] == 0 )
{
currMove += 1;
board[currRow - 2][currCol + 1] = currMove ;
currRow -= 2;
currCol += 1;
if ( findPath( board, currRow, currCol, currMove, boardSize ) )
return true;
}
if ( board[currRow - 1][currCol + 2] == 0 )
{
currMove += 1;
board[currRow - 1][currCol + 2] = currMove ;
currRow -= 1;
currCol += 2;
if ( findPath( board, currRow, currCol, currMove, boardSize ) )
return true;
}
if ( board[currRow + 1][currCol + 2] == 0 )
{
currMove += 1;
board[currRow + 1][currCol + 2] = currMove ;
currRow += 1;
currCol += 2;
if ( findPath( board, currRow, currCol, currMove, boardSize ) )
return true;
}
if ( board[currRow + 2][currCol + 1] == 0 )
{
currMove += 1;
board[currRow + 2][currCol + 1] = currMove ;
currRow += 2;
currCol += 1;
if ( findPath( board, currRow, currCol, currMove, boardSize ) )
return true;
}
if ( board[currRow + 2][currCol - 1] == 0 )
{
currMove += 1;
board[currRow + 2][currCol - 1] = currMove ;
currRow += 2;
currCol -= 1;
if ( findPath( board, currRow, currCol, currMove, boardSize ) )
return true;
}
if ( board[currRow + 1][currCol - 2] == 0 )
{
currMove += 1;
board[currRow + 1][currCol - 2] = currMove ;
currRow += 1;
currCol -= 2;
if ( findPath( board, currRow, currCol, currMove, boardSize ) )
return true;
}
if ( board[currRow - 1][currCol - 2] == 0 )
{
currMove += 1;
board[currRow - 1][currCol - 2] = currMove ;
currRow -= 1;
currCol -= 2;
if ( findPath( board, currRow, currCol, currMove, boardSize ) )
return true;
}
board[currRow][currCol] = 0;
currMove -= 2;
return false;
}`