debugging 使用递归的c++骑士之旅

6qftjkof  于 2023-01-13  发布在  其他
关注(0)|答案(1)|浏览(109)

我知道我的代码非常接近,除了moveKnight之外,我的所有函数都在工作()函数如果你不知道什么是骑士巡回赛,这是我们正在编写的一个程序,用于帮助学生在课堂上学习递归。假设马只接触8*8棋盘上的每一个空格一次,然后打印出到达那里所用的步数。它目前只打印出第一个位置棋盘[0][0]=1但不给予“没有解决方案”。我想不出我应该从哪里开始寻找问题,任何帮助都非常感谢。

#include <iostream>
using namespace std;
//Global Variables

//Defining the 8 possible Moves in the order from class
int yMove[8] = { 1,2, 2, 1,-1,-2,-2,-1 };
int xMove[8] = { 2,1,-1,-2,-2,-1, 1, 2 };

int board[8][8];
int startx, starty = 0;
int movecount = 1;

//checks if move is safe
bool checkSafe(int x, int y)
{
return (x >= 0 && x < 8 && y >= 0 && y < 8 && board[x][y] == 0);
}

//Prints Current board
void printBoard(int board[8][8])
{
for (int x = 0; x < 8; x++)
{
    for (int y = 0; y < 8; y++)
        cout << " " << board[x][y] << " ";
    cout << endl;
}
}

bool moveKnight(int x, int y, int movecount)
{
if (!checkSafe(x, y))
{
    board[x][y] = movecount;
    return true;
}
//end condition
if (movecount == 64)
    return true;
if (moveKnight(x + xMove[1], y + yMove[1], movecount + 1))
    return true;
else if (moveKnight(x + xMove[0], y + yMove[0], movecount + 1))
    return true;
else if (moveKnight(x + xMove[2], y + yMove[2], movecount + 1))
    return true;
else if (moveKnight(x + xMove[3], y + yMove[3], movecount + 1))
    return true;
else if (moveKnight(x + xMove[4], y + yMove[4], movecount + 1))
    return true;
else if (moveKnight(x + xMove[5], y + yMove[5], movecount + 1))
    return true;
else if (moveKnight(x + xMove[6], y + yMove[6], movecount + 1))
    return true;
else if (moveKnight(x + xMove[7], y + yMove[7], movecount + 1))
    return true;
else
{
    board[x][y] = 0;
    return false;
}
}

int KnightTour()
{
//creating board
for (int x = 0; x < 8; x++)
{
    for (int y = 0; y < 8; y++)
        board[x][y] = 0;
}
board[startx][starty] = 1;
movecount + 1;
//No possible moves
if (!moveKnight(startx, starty, movecount))
    cout << "Not possible";
else
{
    //yes possible now print
    printBoard(board);
}
//exits
return 0;
}

int main()
{
//calls knights tour
KnightTour();
cout << endl;
system("pause");
return 0;
}
m528fe3b

m528fe3b1#

moveKnight函数立即返回,因为它确定第一个位置不是有效的移动,原因是您在开始位置用非零值初始化了棋盘。
main中删除以下两行:

board[startx][starty] = 1;
movecount + 1;

第一个函数中断了递归,第二个函数什么也不做。
另外,调用checkSafe()之后的逻辑是扭曲的,因为当你确定一个移动是出界的或者已经玩过的时候,你正在向棋盘写入一个值,这将导致未定义的行为。
纠正这些问题,并简化递归调用:

bool moveKnight(int x, int y, int movecount)
{
    if (checkSafe(x, y))
    {
        board[x][y] = movecount;
        if (movecount == 64)
            return true;

        for (int i = 0; i < 8; i++)
        {
            if (moveKnight(x + xMove[i], y + yMove[i], movecount + 1))
                return true;
        }

        board[x][y] = 0;
    }
    return false;
}

相关问题