Advertisement

knight's tour heuristic

Started by May 14, 2020 08:59 PM
1 comment, last by Alberth 4 years, 6 months ago

I am working on the knight's tour problem out of the dietel and dietel text book on c++. In the third part of the problem it wants me to implement a heuristic using the accessibility array.I was thinking about using the warnsdorff algorithm. I have googled this problem to death but I am still unsure of how to proceed further. here is my code so far.

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

using namespace std;

int board[8][8] = { 0 };
int num = 0;
int horizontal[8] = { 0 };
int vertical[8] = { 0 };
int currentRow = 0; // 0 to 7
int currentCol = 0; // 0 to 7
int moveNumber = 0; // 0 to 7
int previousRow = 0;
int previousCol = 0;

int main()
{
	srand(time(NULL));

	int count = 1;

	horizontal[0] = 2;
	horizontal[1] = 1;
	horizontal[2] = -1;
	horizontal[3] = -2;
	horizontal[4] = -2;
	horizontal[5] = -1;
	horizontal[6] = 1;
	horizontal[7] = 2;

	vertical[0] = -1;
	vertical[1] = -2;
	vertical[2] = -2;
	vertical[3] = -1;
	vertical[4] = 1;
	vertical[5] = 2;
	vertical[6] = 2;
	vertical[7] = 1;

	int accessibility[8][8] = { 2,3,4,4,4,4,3,2,
					   3,4,6,6,6,6,4,3,
					   4,6,8,8,8,8,6,4,
					   4,6,8,8,8,8,6,4,
					   4,6,8,8,8,8,6,4,
					   4,6,8,8,8,8,6,4,
					   3,4,6,6,6,6,4,3,
					   2,3,4,4,4,4,3,2, };

	while (count <= 64)
	{
		moveNumber = 0 + rand() % 7;

		cout << moveNumber << endl;

		previousRow = currentRow;
		previousCol = currentCol;

		currentRow += vertical[moveNumber];
		currentCol += horizontal[moveNumber];

		if (currentCol > 3 || currentRow > 3 || currentCol < -4 || currentRow < -4)
		{
			currentRow = previousRow;
			currentCol = previousCol;
			count--;
		}

		if (currentRow == previousRow && currentCol == previousCol)
		{
			currentRow = previousRow;
			currentCol = previousCol;
			count--;
		}

		cout << "Previous Row " << previousRow << endl;
		cout << "Previous Col " << previousCol << endl;

		cout << "Row " << currentRow << endl;
		cout << "Col " << currentCol << endl;

		count++;
	}

	system("pause");
	return 0;
} 

Nice home work, I never had that one.

This topic is closed to new replies.

Advertisement