C++

Forum

 
Recursive backtracking question

oboeninja (9)
So, in short I'm working on a knight's tour program. If you don't know what that is, the knight gets put on the chess board and you have to move it to every spot on the board exactly once. I'm using a recursive function but am having trouble getting my backtracking to work. I can get to 22 steps in a 5x5 board but the program won't back up and try a different path. I'm posting just the recursive part of my code (sorry it's a little long) Any insight would be extremely helpful. Thanks a lot!


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
 
bool findPath ( int board[][boardSize + 4], int &currRow, int &currCol, int &currMove,int boardSize )
{
	int i, j;
	bool foundSpot;

	board[currRow][currCol] = currMove;
		
	if ( currMove == boardSize * boardSize )
		return true;

	for ( i = 0; i < boardSize + 4; i++ )
	{
		for ( j = 0; j < boardSize + 4; j++ )
			cout << setw (3) << board[i][j];
		cout<<endl;
	}
	cout << endl;

	if ( board[currRow - 2][currCol - 1] == 0 )
	{
		currMove += 1;
		board[currRow - 2][currCol - 1] = currMove;
		currRow -= 2;
		currCol -= 1;
		if ( findPath( board, currRow, currCol, currMove, boardSize ) )
			return true;
	}

	if ( board[currRow - 2][currCol + 1] == 0 )
	{
		currMove += 1;
		board[currRow - 2][currCol + 1] = currMove ;
		currRow -= 2;
		currCol += 1;
		if ( findPath( board, currRow, currCol, currMove, boardSize ) )
			return true;
	}

	if ( board[currRow - 1][currCol + 2] == 0 )
	{
		currMove += 1;
		board[currRow - 1][currCol + 2] = currMove ;
		currRow -= 1;
		currCol += 2;
		if ( findPath( board, currRow, currCol, currMove, boardSize ) )
			return true;
	}

	if ( board[currRow + 1][currCol + 2] == 0 )
	{		
		currMove += 1;
		board[currRow + 1][currCol + 2] = currMove ;
		currRow += 1;
		currCol += 2;
		if ( findPath( board, currRow, currCol, currMove, boardSize ) )
			return true;
	}

	if ( board[currRow + 2][currCol + 1] == 0 )
	{
		currMove += 1;
		board[currRow + 2][currCol + 1] = currMove ;
		currRow += 2;
		currCol += 1;
		if ( findPath( board, currRow, currCol, currMove, boardSize ) )
			return true;
	}

	if ( board[currRow + 2][currCol - 1] == 0 )
	{
		currMove += 1;
		board[currRow + 2][currCol - 1] = currMove ;
		currRow += 2;
		currCol -= 1;
		if ( findPath( board, currRow, currCol, currMove, boardSize ) )
			return true;
	}

	if ( board[currRow + 1][currCol - 2] == 0 )
	{		
		currMove += 1;
		board[currRow + 1][currCol - 2] = currMove ;
		currRow += 1;
		currCol -= 2;
		if ( findPath( board, currRow, currCol, currMove, boardSize ) )
			return true;
	}

	if ( board[currRow - 1][currCol - 2] == 0 )
	{		
		currMove += 1;
		board[currRow - 1][currCol - 2] = currMove ;		
		currRow -= 1;
		currCol -= 2;
		if ( findPath( board, currRow, currCol, currMove, boardSize ) )
			return true;
	}
	board[currRow][currCol] = 0;
	currMove -= 2;
	return false;
}
Topic archived. No new replies allowed.