Im working on a knights tour problem. And ive run into some issues. Im able to get the program to run randomly till it finds a full tour but how would i go about running it only a 100 times and then printing the average number of moves the knight made before faulting?

#include<iostream>
#include<iomanip>
#include<time.h>

using namespace std;

const int MAX_ROWS = 8;
const int MAX_COLUMNS = 8;

const int HorizonalMoves[] = { 2, 1,-1,-2,-2,-1, 1, 2};
const int VerticalMoves[] =  {-1,-2,-2,-1, 1, 2, 2, 1};

void InitializeBoard(int Board[][MAX_COLUMNS]);
void DisplayBoard(int Board[][MAX_COLUMNS]);
int PossibleMoves(int CurrentRow, int CurrentColumn, int Board[][MAX_COLUMNS], int MoveCount);
bool IsValidKnightsMove(int CurrentRow, int CurrentColumn, int NewRow, int NewColumn, int MoveCount);
void GetMove(int& CurrentRow, int& CurrentColumn, int& MoveCount, int Board[][MAX_COLUMNS]);

void main()
{
	
	srand((unsigned int)time(0));

	int Board[MAX_ROWS][MAX_COLUMNS] = {0};

	int CurrentRow = 0;
	int CurrentColumn = 0;
	
	int MoveCount = 0;
	
	while (MoveCount < 64)
	{
		
		MoveCount = 0;
		InitializeBoard(Board);
		do
		{
			GetMove(CurrentRow, CurrentColumn, MoveCount, Board);
		}
		while (PossibleMoves(CurrentRow, CurrentColumn, Board, MoveCount) > 0 );
		
		cout << MoveCount << endl;
	}

	
	
}

void GetMove(int& CurrentRow, int& CurrentColumn, int& MoveCount, int Board[][MAX_COLUMNS])
{
	int NewRow;
	int NewColumn;

	if (PossibleMoves(CurrentRow, CurrentColumn, Board, MoveCount) > 0)
	{
		do
		{
			int RandomMove = rand()%8;
			NewRow = CurrentRow + VerticalMoves[RandomMove];
			NewColumn = CurrentColumn + HorizonalMoves[RandomMove];
		}
		while(NewRow >= MAX_ROWS || NewRow < 0 ||
			NewColumn >= MAX_COLUMNS || NewColumn < 0 || 
			Board[NewRow][NewColumn] != 0 || 
			!IsValidKnightsMove(CurrentRow, CurrentColumn, NewRow, NewColumn, MoveCount));


		MoveCount++;
		Board[NewRow][NewColumn] = MoveCount;
		CurrentRow = NewRow;
		CurrentColumn = NewColumn;
	}
}
void DisplayBoard(int Board[][MAX_COLUMNS])
{
	
	cout << "     1  2  3  4  5  6  7  8" << endl;
	cout << "   ------------------------" << endl;
	
	for (int Row = 0; Row < MAX_ROWS; Row++)
	{
		cout << Row + 1 << "| ";

		for (int Column = 0; Column < MAX_ROWS; Column++)
		{
			cout << setw(3) << Board[Row][Column];
		}

		cout << endl;
	}
}

void InitializeBoard(int Board[][MAX_COLUMNS])
{
	for (int Row = 0; Row < MAX_ROWS; Row++)
	{
		for (int Column = 0; Column < MAX_ROWS; Column++)
		{
			Board[Row][Column] = 0;
		}
	}
}

int PossibleMoves(int CurrentRow, int CurrentColumn, int Board[][MAX_COLUMNS], int MoveCount)
{
	int Result = 0;

	if (MoveCount == 0)
	{
		Result = 64;
	}
	else
	{
		for(int i = 0; i < 8; i++)
		{
			int Row = 	CurrentRow + VerticalMoves[i] + 1;
			int Column = CurrentColumn + HorizonalMoves[i] + 1;

			if (Row > 0 && Row <= MAX_ROWS && 
				Column > 0 && Column <= MAX_COLUMNS && 
				Board[Row-1][Column-1] == 0)
			{
				Result++;
			}
		}
	}

	return Result;
}


bool IsValidKnightsMove(int CurrentRow, int CurrentColumn, int NewRow, int NewColumn, int MoveCount)
{
	bool Result = false;

	if (MoveCount > 0)
	{
		for(int i = 0; i < 8; i++)
		{
			if(CurrentRow + VerticalMoves[i] == NewRow &&
				CurrentColumn + HorizonalMoves[i] == NewColumn )
			{
				Result = true;
			}
		}
	}
	else
	{
		Result = true;
	}

	return Result;
}

Wouldn't you just put the program into a loop that executes 100 times and counts the number of moves it makes in each iteration, stores those numbers in an array (one number stored each time the iteration completes) and divide the sum of all of the contents of the array by 100?

I'm not entirely convinced that this is what you want to achieve though...

Yes, Could you put that in code? Cause the way i keep writing it doesnt work.

Show us your code and we'll see where you're going wrong :)

I'm allergic to writing actual chunks of code. I can only modify other peoples code.

Edit: Hey mods, can we write structured pseudo code? Or is that too much of a handout?

Edited 6 Years Ago by HealBrains: n/a

Im getting funky numbers. But i changed the while to an if and it runs better now.

void main()
{
	
	srand((unsigned int)time(0));

	int Board[MAX_ROWS][MAX_COLUMNS] = {0};

	int CurrentRow = 0;
	int CurrentColumn = 0;
	
	int MoveCount = 0;

	for (int i=0; i<100;i++)
	
	if (MoveCount < 64)
	{		
		MoveCount = 0;
		InitializeBoard(Board);
		do
		{
			GetMove(CurrentRow, CurrentColumn, MoveCount, Board);
		}
		while (PossibleMoves(CurrentRow, CurrentColumn, Board, MoveCount) > 0 );
		
		cout << MoveCount << endl;

		int Average[] = { MoveCount };
		Average[MoveCount/100];
		cout << Average;
		
	}
		
}

There's another way you could do it. I don't know why I said use an array the first time. Forget the array.

Keep the for loop that cycles your program 100 times, and just keep adding movecount to a variable (probably something like int iTotalMoves ) and then when the for loop finishes, divide that variable by 100. Remember to declare iTotalMoves up by your other variables.

You'll probably want to change that IF statement to a WHILE statement, too.

The array way was too much work for a simple problem. *smacks head*

Edited 6 Years Ago by HealBrains: n/a

Edit: Hey mods, can we write structured pseudo code? Or is that too much of a handout?

Sure. Write it kind of general so the posters still have to think some. I do pseudo code a lot.

Edit: I'm a noob.

Why does everyone say this? Don't you think we can't tell? And why should we care? Do you deserve special treatment because of it?

Thanks, i figured it out and now it works good.

Thanks, i figured it out and now it works good.

Right on.

Why does everyone say this? Don't you think we can't tell? And why should we care? Do you deserve special treatment because of it?

It's chic to say it. And I'm a rad dude. That's why.

Edited 6 Years Ago by HealBrains: n/a

This article has been dead for over six months. Start a new discussion instead.