0

目前我正在尝试理解递归。在实现了一些简单的递归算法（如阶乘）之后，我决定尝试一些更难的东西。

我发现了有关骑士之旅的问题，并尝试制作一个程序来找到有效的骑士之旅。

当然它不起作用，输出是一个无限循环。

我看不到错误。我正在自学，没有人问这个问题，所以我决定在这里问。

这是我的 C++ 代码：

#include<iostream>
using namespace std;
#define N 8
int tab[N][N];
void fill_with_zeros();
void display_array();
bool is_move_correct(int nx,int ny);
bool try_moving(int x,int y,int &nx,int &ny,int option);
bool knights_tour(int x,int y,int move_number);

int main()
{
    fill_with_zeros();
    knights_tour(0,0,1); //Passing coordinates and number of moves
    return 0;
}



bool is_move_correct(int nx,int ny) //This functions checks if coordinates are valid
{
    if(nx<N && ny<N && nx>=0 && ny>=0 && tab[nx][ny] == 0) return true;

    return false;
}


bool try_moving(int x,int y,int &nx,int &ny,int option)
{
    switch(option)
    {
    case 1 :  { if(is_move_correct(x+2,y+1)==true)  { nx = x +2,ny = y+ 1;return true;}}

    case 2 :  { if(is_move_correct(x+2,y-1)==true)  { nx = x +2,ny = y- 1;return true;}}

    case 3 :  { if(is_move_correct(x-2,y+1)==true)  { nx = x -2,ny = y + 1;return true;}}

    case 4 :  { if(is_move_correct(x-2,y-1)==true)  { nx = x -2,ny = y - 1;return true;}}

    case 5 :  { if(is_move_correct(x+1,y+2)==true)  { nx = x +1,ny = y +2;return true;}}

    case 6 :  { if(is_move_correct(x+1,y-2)==true)  { nx = x +1,ny = y -2;return true;}}

    case 7 :  { if(is_move_correct(x-1,y+2)==true)  { nx = x -1,ny = y +2;return true;}}

    case 8 :   { if(is_move_correct(x-1,y-2)==true)  { nx = x -1,ny = y -2;return true;}}

    }

    return false;
}


bool knights_tour(int x,int y,int move_number)
{
    tab[x][y] = move_number;

    if(move_number == N*N-1)
    {
        cout<<"Here is the knight's path : "<<endl;
        display_array();
        return true;
    }

// ******************************************************************************
//PROBLEM MUST BE IN THIS PART OF FUNCTION BUT I'M NOT ABLE TO TELL WHERE EXACTLY 
    else
    {
        //cout<<"Current move number : "<<move_number<<endl;
        int nx = 0,ny = 0;

        for(int w = 1; w<=8; w++)
        {
            if (    try_moving(x,y,nx,ny,w) == true )
            {
                if( knights_tour(nx,ny,move_number+1) == true )
                {
                    return true;
                }
            }
        }
    tab[x][y] = 0;
    }
    return false;
}
// ******************************************************************************
// These functions don't need any commentary : 

void fill_with_zeros()
{
    for(int i =0; i<N; i++)
    {
        for(int j = 0; j<N; j++)
        {
            tab[i][j] = 0;
        }
    }
}

void display_array()
{
    for(int i =0; i<N; i++)
    {
        for(int j = 0; j<N; j++)
        {
            cout<<tab[i][j]<<" ";
        }
        cout<<endl;
    }
}
4

1 回答 1

1

我不认为这是无限的。但是，您正在运行具有 O(8^N) 迭代的指数递归函数。这将需要很长时间才能完成——数小时，甚至数年。您应该改进您的算法，看看您是否可以在多项式时间内完成。（看起来@HansKlünder 指出了同样的事情。）

在网上搜索“knight's tour algorithm”会发现许多可以尝试实现的好算法。 这个问题在几天前才发布了一个 Java 实现，作者主动提供帮助。

于 2014-12-28T23:45:22.397 回答