Whats wrong with the following backtracking "Knight's Tour" program?

Nikhar (41)
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:-

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
 
#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?
Last edited on
Denis (350)
Your problem is mf function.
print method will be called only if (in your case) count1 == 10.
As I see, you leave function [/code] mf[/code] early then this condition is reached.
So your need to do the following:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
 
 
#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))
        return; //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.print();
    example.mf(0,0);
}
Nikhar (41)
Thanks for the reply but that did not work.

Maybe I'll write the algorithm I'm using.


Algorithm:-

As we know, from a particular position, the knight can make 8 legal moves. My program keeps "marking" the moves made until it reaches a dead end from where it backtracks by unmarking.

Count1 represents the number of moves made.
Each time, an index is marked, count1 is incremented by 1. Each time, an index is unmarked, count1 is decremented by 1.
From marking a move I mean the following:-

Suppose after 9 moves, the knight has reached the index [0,5], then the array[0][5] holds the value '9'.

So, if size is the number of rows/column, after the size*size move, each index in the array would contain a unique number from 1 to size*size.

So, when count1=size*size+1, it prints the array. I hope this helps you better to understand my program and help me.
Denis (350)
Output of my version:
Knight went to the 0,0 block in 0th turn!
Knight went to the 0,1 block in 0th turn!
Knight went to the 0,2 block in 0th turn!
Knight went to the 1,0 block in 0th turn!
Knight went to the 1,1 block in 0th turn!
Knight went to the 1,2 block in 0th turn!
Knight went to the 2,0 block in 0th turn!
Knight went to the 2,1 block in 0th turn!
Knight went to the 2,2 block in 0th turn!
Nikhar (41)
Thats the output I get here too.

But the output shouldn't be that.

It should be somehting like:-

Knight went to the 0,0 block in 5th turn!
Knight went to the 0,1 block in 1th turn!
Knight went to the 0,2 block in 9th turn!
Knight went to the 1,0 block in 8th turn!
Knight went to the 1,1 block in 4th turn!
Knight went to the 1,2 block in 7th turn!
Knight went to the 2,0 block in 6th turn!
Knight went to the 2,1 block in 3th turn!
Knight went to the 2,2 block in 2th turn!
Denis (350)
After mark you call unmark, that set value of arr[i][j] to 0 again.
Last edited on
Nikhar (41)
I call unmark so that it could backtrack.
jRaskell (347)
Couple things.

1. Your algorithm isn't checking all possible moves from a given location, only the first valid move from a given location. "if/else if" is a mutually exclusive conditional, and that's not what you want. You want to step through every possible move, so use a series of independant if statements.

2. You aren't handling your return conditions properly. You're unmarking ALL traversals of the board, so even if you were to find a complete tour, your unwind would still erase all the moves of that tour.
Nikhar (41)
Thanks jRaskell for your reply. :)

I just removed all the else's. But that did not work and I sort of knew it wouldn't. Because it just need s to check one valid movement at one time. If after following that movement, the knight reaches a dead end, it backtracks, clears the mark it had set, and sets out to follow some other route.

Though you are probably right about the second point. How do I go about improving it?
Nikhar (41)
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
 
#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);
}
jRaskell (347)
I modified your print method as follows to more easily check the output, and your 'solution' missed a location:

1
2
3
4
5
6
7
8
 
void knight::print()
{
    for(int i=0;i<=size-1;i++){
        for(int j=0;j<=size-1;j++)
             cout << setw(3) << arr[i][j]; // need to include iomanip for setw(3)
		cout << endl;
	}
}
 

  1 14  7  0
  8 11  4 13
 15  2  9  6
 10  5 12  3


As you can see, the upper right corner was not visited.

I just removed all the else's. But that did not work and I sort of knew it wouldn't. Because it just need s to check one valid movement at one time. If after following that movement, the knight reaches a dead end, it backtracks, clears the mark it had set, and sets out to follow some other route.


With the else/if's, the backtracking will never follow another route.

Here's some tweaks to your code to show a functional example (and the output on a 6x6 board starting at 0,0):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
 
#include <iostream>
#include <iomanip>
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();
        bool 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 << setw(3) << arr[i][j];
		cout << endl;
	}
}

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

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


int main()
{
	
    knight example(6);
    if(example.mf(0,0))
	cout << "Complete Tour Found." << endl;
    else
	cout << "No Complete Tour Found." << endl;
		
    example.print();

}
 
Complete Tour Found.
  1 30 33 22 25 12
 34 21 26 13 32 23
 29  2 31 24 11 14
 20 35 18 27  8  5
 17 28  3  6 15 10
 36 19 16  9  4  7
Last edited on
Nikhar (41)
Oh jRaskell...thanks a ton for your help! I absolutely love you :D :p

I'm absolutely straight though. lol


I just understood the part of if/else. Thanks for that.

Though I'm still not absolutely sure that I understood this part-->

1
2
3
4
 
if(!mf(x+2,y+1))
				unmark(arr[x][y]);
			else
				return true;


Kindly explain it to me. Meanwhile, I'll try to decipher it on my own.


Edit:-= Oh, I understood this part too. :D

Btw, apart from the if/else's what was wrong about my piece of code?
Last edited on
Topic archived. No new replies allowed.