C++

Forum

 
Kings tour

Doobler (2)
Homework Question : Model a "knights tour"where the initial knight's position is chosen at random, and each successive move is chosen at random. One problem you need to solve in this task is enabling your program to determine when the Knight has hit a dead end; that is no valid moves remain, thus ending the tour. Run your program several times to see if a full or closed tour is ever found at random. Print the board contents after a successful run of finding a full or closed tour. Compute the average length of a random tour over 100 experiments.


Here is what I have so far. I thought I was going in the right direction but now I'm kind of at a loss. I think I may have added to much at once.
My variables, board, chooseRow and chooseCol keep corrupting and everything stopped working. Any hints in the right direction would be gladly accepted. Thanks.

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
 
  // ConsoleApplication2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int SIZE = 8;
const int DELAY = 40000; // set delay for animation
void displayBoard(int board[SIZE][SIZE]);
bool isValidMove(int rowLoc, int colLoc, int cboard[SIZE][SIZE], int testMove);
void makeRandomKnightMove(int curRow, int curCol, int &chooseRow, int &chooseCol, int cboard[SIZE][SIZE]);
int oneRun(int totalMoves);
bool go = true;
int rowChange[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int colChange[] = { -1, -2, -2, -1, 1, 2, 2, 1 };
int wins = 0;

int game = 0;



int oneRun(int totalMoves){
	game++;
	srand((unsigned)time(NULL));
	int moveCounter = 1;
	int board[SIZE][SIZE] = { 0 };    //array for values on board
	int KnightcurRow = rand() % 9; int KnightcurCol = rand() % 9; board[KnightcurRow][KnightcurCol] = 1;  //initial location of Knight
	//displayBoard(board);

	int chooseRow=0, chooseCol=0; // used to store upcoming move


	while (go){
		//Knight's Move
		makeRandomKnightMove(KnightcurRow, KnightcurCol, chooseRow, chooseCol, board);
		board[KnightcurRow][KnightcurCol] = moveCounter;
		moveCounter++;
		board[chooseRow][chooseCol] = moveCounter;
		KnightcurRow = chooseRow; KnightcurCol = chooseCol;
		if (go == false){

			if (moveCounter>64){
				cout << "The knight finished its tour on game: " << game << endl;
				cout << "The knight moved: " << moveCounter << " time(s)." << endl;
				cout << "The board looks like: " << endl;
				displayBoard(board);
				totalMoves = totalMoves + (moveCounter - 1);
				wins++;
				for (int k = 0; k<DELAY; k++) for (int j = 0; j<DELAY; j++);
				
			}
			else{
				//cout <<"The knight ran out of moves!"<<endl;
				//cout << "The knight moved: " << moveCounter<< " time(s)." << endl;
				//displayBoard(board);
				totalMoves = totalMoves + (moveCounter - 1);

			}
		}
	}

	return totalMoves;
}
void makeRandomKnightMove(int curRow, int curCol, int &chooseRow, int &chooseCol, int cboard[SIZE][SIZE]){
	int testMove = rand() % 9;
	int x = 0;
	int testRow = curRow + rowChange[testMove];
	int testCol = curCol + colChange[testMove];
	while (!isValidMove(testRow, testCol, cboard, testMove)){
		// choose again
		testMove = rand() % 9;
		testRow = curRow + rowChange[testMove];
		testCol = curCol + colChange[testMove];
		x++;
		if (x>100){
			go = false;
			break;
		}
	}
	//cout << endl;
	chooseRow = testRow;
	chooseCol = testCol;
}


bool isValidMove(int rowLoc, int colLoc, int cboard[SIZE][SIZE], int testMove){
	if ((rowLoc >= 0) && (rowLoc <SIZE) && (colLoc >= 0) && (colLoc <SIZE) && (cboard[rowLoc][colLoc] == 0))
		return true;
	else return false;
}//END iHasValidMove


void displayBoard(int board[][SIZE])
{
	for (int row = 0; row < 8; row++){
		for (int column = 0; column < 8; column++){
			if (board[row][column] < 10){
				cout << " " << board[row][column] << " ";
			}
			else{
				cout << board[row][column] << " ";
			}
		}
		cout << "\n";
	}

	// for(int k =0;k<DELAY; k++) for(int j=0;j<DELAY;j++);
}//END displayBoard function


int main()
{
	int totalMoves = 0;
	for (int x = 0; x < 100; x++){
		totalMoves = oneRun(totalMoves);
	}
	cout << "The total number of games was: " << game << endl;
	cout << "There were " << wins << " completed tour(s) and " << game - wins << " failed tour(s)." << endl;
	cout << "The average tour was " << totalMoves / 6400 << " moves long." << endl;
	
	char x;  cin >> x;
	
	return 0;
}//END main function
coder777 (8444)
rand() % 9 is a problem (the reason for the crash). It returns values from 0 to 8, but 8 is out of bounds. You may replace it with rand() % SIZE

I suggest that you reduce global variables. For instance go. If makeRandomKnightMove() would return bool you could make it local to oneRun().

I suggest one expression per line. Line 52 is utterly useless.

srand((unsigned)time(NULL)); is supposed to be called only once at the very beginning of main()
Doobler (2)
Alright I fixed a few of the things you mentioned. Correct me if I'm wrong but i think i made makeRandomKnightMove() return a bool properly.

The program is still not running correctly and says the stack around board is corrupted (Run-Time Check Failure #2 - Stack around the variable 'board' was corrupted.), which I'm not completely sure what it means, or gives the error: Unhandled exception at 0x00DE6BD0 in ConsoleApplication2.exe: 0xC0000005: Access violation writing location 0xFFFFFFF5 so I'm still at a loss of what to do. I'm guessing it has something to do with either how I'm passing board or I'm asking for an address that doesn't exist in it but I am not sure.

Sorry for the bad coding or mistakes, I'm very new to c++ and programming in general.

Here is the new code:

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
 
// ConsoleApplication2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int SIZE = 8;
void displayBoard(int board[SIZE][SIZE]);
bool isValidMove(int rowLoc, int colLoc, int cboard[SIZE][SIZE], int testMove);
bool makeRandomKnightMove(int curRow, int curCol, int &chooseRow, int &chooseCol, int cboard[SIZE][SIZE]);
int oneRun(int totalMoves);
int rowChange[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int colChange[] = { -1, -2, -2, -1, 1, 2, 2, 1 };
int wins = 0;
int game = 0;



int oneRun(int totalMoves){
	game++;
	int moveCounter = 1;
	int board[SIZE][SIZE] = { 0 };    //array for values on board
	int KnightcurRow = rand() % 9; 
	int KnightcurCol = rand() % 9; 
	board[KnightcurRow][KnightcurCol] = 1; 
	//initial location of Knight

	int chooseRow = 0, chooseCol = 0; // used to store upcoming move


	while (!makeRandomKnightMove(KnightcurRow, KnightcurCol, chooseRow, chooseCol, board)){
		//Knight's Move
		makeRandomKnightMove(KnightcurRow, KnightcurCol, chooseRow, chooseCol, board);
		board[KnightcurRow][KnightcurCol] = moveCounter;
		moveCounter++;
		board[chooseRow][chooseCol] = moveCounter;
		KnightcurRow = chooseRow; KnightcurCol = chooseCol;
		if (!makeRandomKnightMove(KnightcurRow, KnightcurCol, chooseRow, chooseCol, board)){

			if (moveCounter>64){
				cout << "The knight finished its tour on game: " << game << endl;
				cout << "The knight moved: " << moveCounter << " time(s)." << endl;
				cout << "The board looks like: " << endl;
				displayBoard(board);
				totalMoves = totalMoves + (moveCounter - 1);
				wins++;

			}
			else{
				totalMoves = totalMoves + (moveCounter - 1);

			}
		}
	}

	return totalMoves;
}
bool makeRandomKnightMove(int curRow, int curCol, int &chooseRow, int &chooseCol, int cboard[SIZE][SIZE]){
	int testMove = rand() % 8;
	int x = 0;
	int testRow = curRow + rowChange[testMove];
	int testCol = curCol + colChange[testMove];
	while (!isValidMove(testRow, testCol, cboard, testMove)){
		// choose again
		testMove = rand() % 8;
		testRow = curRow + rowChange[testMove];
		testCol = curCol + colChange[testMove];
		x++;
		if (x>100){
			return false;
		}
	}
	
	chooseRow = testRow;
	chooseCol = testCol;
        return true;
}


bool isValidMove(int rowLoc, int colLoc, int cboard[SIZE][SIZE], int testMove){
	if ((rowLoc >= 0) && (rowLoc <SIZE) && (colLoc >= 0) && (colLoc <SIZE) && (cboard[rowLoc][colLoc] == 0))
		return true;
	else return false;
}//END iHasValidMove


void displayBoard(int board[][SIZE])
{
	for (int row = 0; row < 8; row++){
		for (int column = 0; column < 8; column++){
			if (board[row][column] < 10){
				cout << " " << board[row][column] << " ";
			}
			else{
				cout << board[row][column] << " ";
			}
		}
		cout << "\n";
	}
}//END displayBoard function


int main()
{
	srand((unsigned)time(NULL));
	int totalMoves = 0;
	

	for (int x = 0; x < 100; x++){
		totalMoves = oneRun(totalMoves);
	}
	
	cout << "The total number of games was: " << game << endl;
	cout << "There were " << wins << " completed tour(s) and " << game - wins << " failed tour(s)." << endl;
	cout << "The average tour was " << totalMoves /100 << " moves long." << endl;

	char x;  cin >> x;

	return 0;
}//END main function
Last edited on
coder777 (8444)
There are still several 9 in your code. I suggest to search (also 8) and replace them with SIZE

The advantage of using SIZE instead of a number (like 8): you can change the size of your board without changing anything across your code
Topic archived. No new replies allowed.