What's wroing with the following backtracking "Knight's Tour" program.

[Nikhar]

I have made a program to the follwoing problem:-

Another chessboard puzzle (this one reputedly solved by GAUSS at the age of four) is to find a sequence of moves by a knight that will visit every square of the board exactly once. Write a backtracking program that will input an initial position and search for a knight’s tour starting at the given position and going to every square once and no square more than once.

The program is:-

#include<iostream>

using namespace std;

int max_size=10;
int count1=1;
class knight
{
    public:
        knight(int);
        int size;
        int arr[10][10];
        void mark(int &);
        void unmark(int &);
        void print();
        void mf(int, int);
        bool unvisited(const int&);
};

knight::knight(int a)
{
    int i,j;
    size=a;
    for(i=0;i<=a-1;i++)
        for(j=0;j<=a-1;j++)
            arr[i][j]=0;
}

void knight::mark(int &a)
{
    a=count1;
    count1++;
}

void knight::unmark(int &a)
{
    a=0;
    count1--;
}

void knight::print()
{
    for(int i=0;i<=size-1;i++)
        for(int j=0;j<=size-1;j++)
            cout<<"\nKnight went to the "<<i<<','<<j<<" block in "<<arr[i][j]<<"th turn!";
}

void knight::mf(int x, int y)
{
    if(count1==((size*size)+1))
        print();
    else if(unvisited(arr[x][y])&&(x+2<=(size-1))&&(y+1<=(size-1)))
    {
        mark(arr[x][y]);
        mf(x+2,y+1);
        unmark(arr[x][y]);
    }
    else if(unvisited(arr[x][y])&&(x+1<=(size-1))&&(y+2<=(size-1)))
    {
        mark(arr[x][y]);
        mf(x+1,y+2);
        unmark(arr[x][y]);
    }
    else if(unvisited(arr[x][y])&&(x+2<=(size-1))&&(y-1>=0))
    {
        mark(arr[x][y]);
        mf(x+2,y-1);
        unmark(arr[x][y]);
    }
    else if(unvisited(arr[x][y])&&(x+1<=(size-1))&&(y-2>=0))
    {
        mark(arr[x][y]);
        mf(x+1,y-2);
        unmark(arr[x][y]);
    }
    else if(unvisited(arr[x][y])&&(x-2>=0)&&(y+1<=(size-1)))
    {
        mark(arr[x][y]);
        mf(x-2,y+1);
        unmark(arr[x][y]);
    }
    else if(unvisited(arr[x][y])&&(x-1>=0)&&(y+2<=(size-1)))
    {
        mark(arr[x][y]);
        mf(x-1,y+2);
        unmark(arr[x][y]);
    }
    else if(unvisited(arr[x][y])&&(x-2>=0)&&(y-1>=0))
    {
        mark(arr[x][y]);
        mf(x-2,y-1);
        unmark(arr[x][y]);
    }
    else if(unvisited(arr[x][y])&&(x-1>=0)&&(y-2>=0))
    {
        mark(arr[x][y]);
        mf(x-1,y-2);
        unmark(arr[x][y]);
    }
}

bool knight::unvisited(const int& a)
{
    if(a==0)
        return 1;
    else return 0;
}


int main()
{
    knight example(3);
    example.mf(0,0);
}

When, I run this program, nothing happens. Nothing is displayed.
Whats wrong with the program?

[Nick Evan]

you need to output the values of "x","y", "count1" and "size" inside your ::mf() function. That way you can see for yourself why none of the if-statements are true. The keyword here is "debugging"

[edit]
Oh, and please do not use global variables.. You can declare them as private members of your class, no need for them to be global. (is there ever a need? )

[Nikhar]

Thanks a lot for your quick response.:)

But I am don't think I understood your meaning. What do you mean when you say that I need to "output" those values?

Edit:-

Ah, I think I got you!

When I change the function ::mf() to this-->

void knight::mf(int x, int y)
{

    cout<<x<<endl<<y<<endl<<size<<endl<<count1<<endl<<endl;
    if(count1==((size*size)+1))
        print();
    else if(unvisited(arr[x][y])&&(x+2<=(size-1))&&(y+1<=(size-1)))
    {
        mark(arr[x][y]);
        mf(x+2,y+1);
        unmark(arr[x][y]);
    }
    else if(unvisited(arr[x][y])&&(x+1<=(size-1))&&(y+2<=(size-1)))
    {
        mark(arr[x][y]);
        mf(x+1,y+2);
        unmark(arr[x][y]);
    }
    else if(unvisited(arr[x][y])&&(x+2<=(size-1))&&(y-1>=0))
    {
        mark(arr[x][y]);
        mf(x+2,y-1);
        unmark(arr[x][y]);
    }
    else if(unvisited(arr[x][y])&&(x+1<=(size-1))&&(y-2>=0))
    {
        mark(arr[x][y]);
        mf(x+1,y-2);
        unmark(arr[x][y]);
    }
    else if(unvisited(arr[x][y])&&(x-2>=0)&&(y+1<=(size-1)))
    {
        mark(arr[x][y]);
        mf(x-2,y+1);
        unmark(arr[x][y]);
    }
    else if(unvisited(arr[x][y])&&(x-1>=0)&&(y+2<=(size-1)))
    {
        mark(arr[x][y]);
        mf(x-1,y+2);
        unmark(arr[x][y]);
    }
    else if(unvisited(arr[x][y])&&(x-2>=0)&&(y-1>=0))
    {
        mark(arr[x][y]);
        mf(x-2,y-1);
        unmark(arr[x][y]);
    }
    else if(unvisited(arr[x][y])&&(x-1>=0)&&(y-2>=0))
    {
        mark(arr[x][y]);
        mf(x-1,y-2);
        unmark(arr[x][y]);
    }
    cout<<"\nEnd of loop!\n";
}

I get this output-->

0
0
4
1

2
1
4
2

3
3
4
3

1
2
4
4

3
3
4
5

End of Loop!
End of Loop!
End of Loop!
End of Loop!
End of Loop!

[Nick Evan]

Ok good. Now you can clearly see that with these values, the print() function will never be reached. The next step is to trace your program (by hand) with these values to see which if-statements were executed and why. This should give you an idea what your current programflow is opposed to your desired flow.

[Nikhar]

Hi...I just wanted to inform you that I corrected the program myself. Thanks for your replies.

Just in case you are interested, this is the corrected version of the program.

#include<iostream>

using namespace std;

int max_size=10;

class knight
{
    public:
        int count1;
        knight(int);
        int size;
        int arr[4][4];
        void mark(int ,int);
        void unmark(int , int);
        void print();
        void mf(int, int);
        bool unvisited(const int&);
};

knight::knight(int a)
{
    count1=1;
    int i,j;
    size=a;
    for(i=0;i<=a-1;i++)
        for(j=0;j<=a-1;j++)
            arr[i][j]=0;
}

void knight::mark(int x, int y)
{
    arr[x][y]=count1;
    count1++;
}

void knight::unmark(int x, int y)
{
    arr[x][y]=0;
    count1--;
}

void knight::print()
{
    for(int i=0;i<=size-1;i++)
        for(int j=0;j<=size-1;j++)
            cout<<"\nKnight went to the "<<i<<','<<j<<" block in "<<arr[i][j]<<"th turn!";
}

void knight::mf(int x, int y)
{
    if(count1==((size*size)))
        print();
    else if((x+2<=(size-1))&&(y+1<=(size-1))&&unvisited(arr[x+2][y+1]))
    {
        x+=2;
        y+=1;
        mark(x,y);
        mf(x,y);
        unmark(x,y);
    }
    else if((x+1<=(size-1))&&(y+2<=(size-1))&&unvisited(arr[x+1][y+2]))
    {
        x+=1;
        y+=2;
        mark(x,y);
        mf(x,y);
        unmark(x,y);
    }
    else if((x+2<=(size-1))&&(y-1>=0)&&unvisited(arr[x+2][y-1]))
    {
        x+=2;
        y-=1;
        mark(x,y);
        mf(x,y);
        unmark(x,y);
    }
    else if((x+1<=(size-1))&&(y-2>=0)&&unvisited(arr[x+1][y-2]))
    {
        x+=1;
        y-=2;
        mark(x,y);
        mf(x,y);
        unmark(x,y);
    }
    else if((x-2>=0)&&(y+1<=(size-1))&&unvisited(arr[x-2][y+1]))
    {
        x-=2;
        y+=1;
        mark(x,y);
        mf(x,y);
        unmark(x,y);
    }
    else if((x-1>=0)&&(y+2<=(size-1))&&unvisited(arr[x-1][y+2]))
    {
        x-=1;
        y+=2;
        mark(x,y);
        mf(x,y);
        unmark(x,y);
    }
    else if((x-2>=0)&&(y-1>=0)&&unvisited(arr[x-2][y-1]))
    {
        x-=2;
        y-=1;
        mark(x,y);
        mf(x,y);
        unmark(x,y);
    }
    else if((x-1>=0)&&(y-2>=0)&&unvisited(arr[x-1][y-2]))
    {
        x-=1;
        y-=2;
        mark(x,y);
        mf(x,y);
        unmark(x,y);
    }
}

bool knight::unvisited(const int& a)
{
    if(a==0)
        return 1;
    else return 0;
}


int main()
{
    knight example(4);
    example.mark(0,0);
    example.mf(0,0);
}