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

Question

Nikhar 19 Junior Poster in Training

16 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++ puzzle

Edited 16 Years Ago by Nikhar because: n/a

2 Contributors
4 Replies
192 Views
22 Hours Discussion Span
Latest Post 16 Years Ago Latest Post by Nikhar

Dani AI

Generated 6 Months Ago

Nice debugging work by and well done on fixing it, . The behaviour you saw (a few recursive calls, then a bunch of "End of loop" returns and never reaching the full-tour print) is textbook for a few common backtracking mistakes. The important lessons here are: always check the destination square before you move, mark/unmark the destination (not the current cell) around the recursive call, and iterate all eight knight moves instead of chaining them with else if (which stops you trying remaining moves after the first failing branch). Also keep the visited counter as part of the object state (not a loose global) and make your base case a clear equality to N*N (watch for off-by-one).

A compact, easier-to-read pattern to follow is to iterate a small move table and do the bounds+unvisited checks on the target before recursing:

const int dx[8] = {2,1,-1,-2,-2,-1,1,2};
const int dy[8] = {1,2,2,1,-1,-2,-2,-1};

void search(int x,int y) {
  if (visitedCount == N*N) printSolution();
  for (int k=0;k<8;k++) {
    int nx = x + dx[k], ny = y + dy[k];
    if (inBounds(nx,ny) && board[nx][ny]==0) {
      board[nx][ny] = ++visitedCount;
      search(nx,ny);
      board[nx][ny] = 0; --visitedCount;
    }
  }
}

Debug tips: log x,y and visitedCount on function entry and on return to trace why branches fail; assert bounds before indexing; test on very small boards first. For larger boards consider move-ordering heuristics (Warnsdorff) to dramatically prune search. Finally, print the final path only when you hit the base case to avoid overwhelming output.

All 4 Replies

Nick Evan 4,005 Industrious Poster

16 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 16 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.

Dani AI

Recommended Answers Collapse Answers

All 4 Replies

Recommended Answers