My knight's tour algorithm possibly is running on an infinite loop

Question

Here's the code i wrote.

#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;
}

A little explanation. I am using an int [8][8] to represent the board of chess and initially i put in every square of the board the number -1.

As the Knight moves it marks the square that he visits with the counter (int counter) and from there (and for all the legal moves the knight can take) makes recursive calls to find a path (the goal is to visit each square exactly once).

Once the counter hits 64 the function bool knighttour(square start,int &counter,int cb[][8]) must return true and the main program then should display "the knight's tour" as it is marked on the [8][8] chessboard.

I believe that the above code i provided runs on an infinite loop. I let it run for 3 minutes.

Answer 1

This code probably tries to find all possible routes in knights tour and will return last found route.

Instead of

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

Try

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

}

Answer 2

Theory says:

...It is important to note that an exhaustive brute force approach (one which iterates through all possible move sequences) can never be applied to the Knight's Tour problem (except for very small board sizes). For a regular 8x8 chess board, there are approximately 4×1051 possible move sequences,[9] and it would take an unfathomable amount of time to iterate through such a large number of moves.

So to ensure that your program works, try with smaller board size (say 4x4).

To ensure your program works for 8x8 in reasonable time you'll have to change the algorithm. There are many in addition to those listed here.

--edit--

also to ensure that your program is doing something, it's always a good idea to add some traces while you're still developing it.

E.g.

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 3

One thing I see is that although you return true when counter==64 in knighttour, that doesn't get propagated, the function calling it will return false.. so you'll never notice it in main().

That said, even if you fix your algorithm it might not finish in your lifetime.