Алгоритм тура моего рыцаря, возможно, работает по бесконечному циклу

Question

Вот код, который я написал.

#include "genlib.h"
#include <iostream>
#include <math.h>
#include "vector.h"

struct square
{
    int x;
    int y;

};


bool knighttour(square start,int &counter,int cb[][8]);
Vector <square> generatemoves (square start);
void Marksquare(int &cb,int ctr);
void Unmarksquare(int &cb);
bool IsLegal(square a,int cb[][8]);




int main() 
{
    int chessboard[8][8];

    for (int i=0;i<8;i++)
        for (int j=0;j<8;j++)
            chessboard[i][j]=-1;

    int counter=1;

    for (int i=0;i<8;i++){
        for (int j=0;j<8;j++){
            square temp;
            temp.x=i;
            temp.y=j;
            if (knighttour(temp,counter,chessboard))
            {
                for (int k=0;k<8;k++){
                    cout<<chessboard[k][0]<<chessboard[k][1]<<chessboard[k][2]<<chessboard[k][3]<<chessboard[k][4]<<chessboard[k][5];
                    cout<<chessboard[k][6]<<chessboard[k][7]<<endl;}


            }

        }
    }


    return 0;
}


bool knighttour(square pt,int &counter,int cb[][8])
{

    Marksquare(cb[pt.x][pt.y],counter);
    if (counter==64)
        return true;

    counter++;

    Vector <square> temp = generatemoves(pt);

    for (int i=0;i<temp.size();i++)
    {
        if (IsLegal(temp[i],cb))
            knighttour(temp[i],counter,cb);
    }

    Unmarksquare(cb[pt.x][pt.y]);
    counter--;
    return false;

}



Vector <square> generatemoves (square start)
{
    Vector <square> temp;
    Vector <square> temp2;

        square mv1;
        mv1.x=start.x+2;
        mv1.y=start.y+1;
        temp.add(mv1);

        square mv2;
        mv2.x=mv1.x;
        mv2.y=start.y-1;
        temp.add(mv2);


        square mv3;
        mv3.y=start.y+2;
        mv3.x=start.x+1;
        temp.add(mv3);

        square mv4;
        mv4.y=start.y+2;
        mv4.x=start.x-1;
        temp.add(mv4);

        square mv5;
        mv5.x=start.x-2;
        mv5.y=start.y+1;
        temp.add(mv5);

        square mv6;
        mv6.x=start.x-2;
        mv6.y=start.y-1;
        temp.add(mv6);

        square mv7;
        mv7.y=start.y-2;
        mv7.x=start.x-1;
        temp.add(mv7);

        square mv8;
        mv8.y=start.y-2;
        mv8.x=start.x+1;
        temp.add(mv8);


        for (int i=0;i<temp.size();i++)
            if (temp[i].x>=0 && temp[i].x<=7 && temp[i].y>=0 && temp[i].y<=7)
                temp2.add(temp[i]);




        return temp2;
}



void Marksquare(int &a,int ctr)
{
    a=ctr;

}



void Unmarksquare(int &a)
{
    a=-1;
}


bool IsLegal(square a,int cb[][8])
{
    if (cb[a.x][a.y]==-1)
        return true;
    else 
        return false;
}

Небольшое объяснение.Я использую int [8] [8] для представления шахматной доски, и первоначально я помещаю в каждый квадрат доски число -1.

Когда Рыцарь перемещается, он отмечает квадрат, с которым он посещаетсчетчик (int counter) и оттуда (и для всех законных ходов, которые может предпринять рыцарь) делает рекурсивные вызовы, чтобы найти путь (цель состоит в том, чтобы посетить каждый квадрат ровно один раз).

Как только счетчик достигнет 64, функция bool knighttour(square start,int &counter,int cb[][8]) должна вернуть значение true, и тогда главная программа должна отобразить «путешествие коня», как это отмечено на шахматной доске [8] [8].

Я считаю, что приведенный выше код работает по бесконечному циклу.Я позволил ему работать в течение 3 минут.

Answer 1

Теория гласит: :

... Важно отметить, что исчерпывающий метод грубой силы (который повторяет все возможные последовательности ходов) никогда не может быть применен кпроблема Knight's Tour (за исключением очень маленьких размеров доски).Для обычной шахматной доски 8x8 существует примерно 4 × 1051 возможных последовательностей ходов, [9] и потребуется непостижимое количество времени, чтобы пройти через такое большое количество ходов.

Так чтоубедитесь, что ваша программа работает, попробуйте использовать меньший размер платы (скажем, 4x4).

Чтобы ваша программа работала в течение 8x8 в разумные сроки, вам придется изменить алгоритм.Есть много помимо перечисленных здесь .

- edit -

, также чтобы убедиться, что ваша программа что-то делает, всегда полезно добавитьнекоторые следы, пока вы еще его разрабатываете.

Например

bool knighttour(square pt,int &counter,int cb[][8]) {

printf("\r%d    ", counter);  // <<<---
Marksquare(cb[pt.x][pt.y],counter);
if (counter==64)
    return true;

counter++;

Vector <square> temp = generatemoves(pt);

for (int i=0;i<temp.size();i++)
{
    if (IsLegal(temp[i],cb))
        knighttour(temp[i],counter,cb);
}

Unmarksquare(cb[pt.x][pt.y]);
counter--;
return false;

}

Answer 2

Этот код, вероятно, пытается найти все возможные маршруты в туре рыцарей и возвращает последний найденный маршрут.

Вместо

for (int i=0;i<temp.size();i++)
{
    if (IsLegal(temp[i],cb))
        knighttour(temp[i],counter,cb);
}

Попробуйте

for (int i=0;i<temp.size();i++)
{
    if (IsLegal(temp[i],cb))
    {
        if(knighttour(temp[i],counter,cb))
        { 
             return true;
        }
    }

}

Answer 3

Одна вещь, которую я вижу, это то, что, хотя вы return true когда counter==64 в knighttour, это не распространяется, функция, вызывающая его, вернет false .. поэтому вы никогда не заметите это в main ().

Тем не менее, даже если вы исправите свой алгоритм, он может не завершиться в течение вашей жизни.