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

Question

Nikhar 19 Junior Poster in Training

14 Years Ago

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?

c++

Edited 14 Years Ago by Nikhar because: n/a

2 Contributors
4 Replies
170 Views
22 Hours Discussion Span
Latest Post 14 Years Ago Latest Post by Nikhar

All 4 Replies

Nick Evan 4,005 Industrious Poster

14 Years Ago

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? )

Edited 14 Years Ago by Nick Evan because: n/a

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Nikhar 19 Junior Poster in Training · Answer 1 · 2010-01-13T18:11:09+00:00

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 4,005 Industrious Poster Team Colleague Featured Poster · Answer 2 · 2010-01-13T18:44:11+00:00

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 19 Junior Poster in Training · Answer 3 · 2010-01-14T10:47:01+00:00

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

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

Recommended Answers Collapse Answers

All 4 Replies

Recommended Answers