knightsTour.cpp

// knight's tour problem using a one dimensional array
// https://support.sas.com/resources/papers/proceedings15/3060-2015.pdf 

#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
#include <fstream>

using namespace std;

// const global variables and arrays

int const boardSize = 64;
int const knightMoves = 8;
const array<int, knightMoves> validJumps = { 21,19,12,8,-8,-12,-19,-21 }; // knights' moves along a 1d array; valid knight moves on octal board (these numbers are decimal distances)	

// ================================================================================================================================= //

// Functions

// function converts decimal to octal
int decimalToOctal(int decimalNumber)
{
	int rem, i = 1, octalNumber = 0;
	while (decimalNumber != 0)
	{
		rem = decimalNumber % 8;
		decimalNumber /= 8;
		octalNumber += rem * i;
		i *= 10;
	}
	return octalNumber;
}

// function converts octal to decimal  
int octalToDecimal(int octalNumber)
{
	int rem, i = 1, decimalNumber = 0;
	while (octalNumber != 0)
	{
		rem = octalNumber % 10;
		octalNumber /= 10;
		decimalNumber += rem * i;
		i *= 8;
	}
	return decimalNumber;
}

// function that checks if move lands on the chessboard and on an empty square (board == 0)
bool isValidSquare(const array<int, boardSize>& board, int sq)
{
	return (sq >= 0 && sq <= 77 && abs(sq) % 10 < 8 && board[octalToDecimal(sq)] == 0);
}

// function that fills vector with available squares
void fillNextSquareVector(vector<int>& nextSquaresVector, array<int, boardSize>& accessIndices, const array<int, boardSize>& board, int& squareRef)
{
	int nextSquare;
	for (auto n : validJumps) // loop through all knight moves
	{
		nextSquare = decimalToOctal(squareRef) + n; // = square + 21 , square + 19 , square + 12, ... possible next move on the octal board
		// check if move is on the octal board and board square is available
		if (isValidSquare(board, nextSquare))
		{
			// reduce accessibility numbers by 1 each time a square is visited
			accessIndices[octalToDecimal(nextSquare)] = accessIndices[octalToDecimal(nextSquare)] - 1;
			// convert back to decimal and populate vector; combine the accessibility number with a valid next move into a 3 digit number
			nextSquaresVector.push_back(100 * accessIndices[octalToDecimal(nextSquare)] + octalToDecimal(nextSquare));
		}
	}
}

// boolean function that returns true when 2 squares are tied.
bool isTied(vector<int>& nextSquaresVector)
{
	return (nextSquaresVector.size() > 1 && (nextSquaresVector[0] / 100 == nextSquaresVector[1] / 100)); // divide by 100 to get the integer part (the access number)
}

// tie breaker function; moves ahead one move for each tied square and checks lowest access number available
void tieBreaker(vector<int>& nextSquaresVector, const array<int, boardSize>& accessIndices, const array<int, boardSize>& board, int& squareRef)
{
	vector<int> firstTieBreakerVector; // holds access numbers of tied squares of nextSquaresVector[0]
	vector<int> secondTieBreakerVector; // holds access numbers of tied squares of nextSquaresVector[1]	

	int firstTiedSquare = decimalToOctal(nextSquaresVector[0] % 100); // tied square (same access number) at location 0 (first location)
	int secondTiedSquare = decimalToOctal(nextSquaresVector[1] % 100); // tied square at location 1 (second location)

	int nextSquare;
	// int squareRef is an alias for square 
	for (auto n : validJumps) // loop through valid jumps
	{
		nextSquare = firstTiedSquare + n;
		if (isValidSquare(board, nextSquare))
			firstTieBreakerVector.push_back(accessIndices[octalToDecimal(nextSquare)]);

		nextSquare = secondTiedSquare + n;
		if (isValidSquare(board, nextSquare))
			secondTieBreakerVector.push_back(accessIndices[octalToDecimal(nextSquare)]);
	}
	sort(firstTieBreakerVector.begin(), firstTieBreakerVector.end());
	sort(secondTieBreakerVector.begin(), secondTieBreakerVector.end());

	if (secondTieBreakerVector[0] <= firstTieBreakerVector[0]) // less than or equal to is crucial here
		squareRef = nextSquaresVector[1] % 100; // set the square location if conditions are met

	firstTieBreakerVector.clear();
	secondTieBreakerVector.clear();
}

// re: file output https://www.cs.drexel.edu/~jsalvage/2005/CS132/lectures/07.1_pass_by_reference/streams.html?CurrentSlide=4 
void printHeaders(int myCount, int myTour, ofstream& file, int sq) // stream parameters must be passed by reference
{
	cout << "count" << "\t" << "start" << "\t" << "end" << "\t" << "delta" << "\n";
	cout << myCount - 1 << "\t" << myTour << "\t" << sq << "\t" << abs(sq - myTour) << "\n";

	// write to a text file
	file << "count" << "\t" << "start" << "\t" << "end" << "\t" << "delta" << "\n";
	file << myCount - 1 << "\t" << myTour << "\t" << sq << "\t" << abs(sq - myTour) << "\n";

	// check if tour is full, closed or partial
	if (myCount - 1 == boardSize && (abs(sq - myTour) != 17 || abs(sq - myTour) != 15 || abs(sq - myTour) != 10 || abs(sq - myTour) != 6))
	{
		cout << "full tour";
		file << "full tour";
	}
	if (myCount - 1 == boardSize && (abs(sq - myTour) == 17 || abs(sq - myTour) == 15 || abs(sq - myTour) == 10 || abs(sq - myTour) == 6))
	{
		cout << " and a closed tour";
		file << " and a closed tour";
	}
	if (myCount - 1 != boardSize)
	{
		cout << "partial tour";
		file << "partial tour";
	}
}

void printChessBoard(const array<int, boardSize>& board, ofstream& file)
{
	for (size_t i = 0; i < board.size(); ++i)
	{
		if (0 == i % 8)
			cout << endl;
		cout << board[i] << "\t";

		if (0 == i % 8)
			file << endl;
		file << board[i] << "\t";
	}
}

// ================================================================================================================================= //

// Driver Code
int main()
{
	array <int, boardSize> board; // chessboard
	array <int, boardSize> accessIndices; // accessibility matrix
	vector<int> nextSquaresVector; // holds available next moves; varies in size
	
	int counter = 0; // tracks number of moves on the board	
	int square = 0; // location on the chessboard
	int totalFullTours = 0; // used to count full tours	
	int closedTours = 0;

	ofstream myfile;
	myfile.open("knightsTourTieBreaker.txt");

	for (int tours = 0; tours < boardSize; tours++) // this outer loop completes boardSize tours starting the inner loop from each square of the chessboard; 
	{
		// initialize and reset board array to 0 when starting every tour
		for (size_t i = 0; i < board.size(); ++i)
			board[i] = 0;

		// initialize and reset access array for every tour
		accessIndices =
		{ 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 };

		square = tours; // start at this square and visit all squares on the board (0 to 63) for each tour
		counter = 1; // start counter at 1 for each tour
		board[square] = counter; // assign 1 to the start square on  decimal board for each tour

		// ================================================================================================================================= //

		for (int i = 1; i <= boardSize; i++) // this inner loop travels the board
		{
			++counter;

			fillNextSquareVector(nextSquaresVector, accessIndices, board, square); // square and nextSquare pass by reference; see function

			// end loop if no moves are available
			if (nextSquaresVector.empty()) // check if vector is empty (no more available moves on the chessboard) if so, break and exit the loop
				break;

			// sort numbers from lowest to highest within the vector
			sort(nextSquaresVector.begin(), nextSquaresVector.end());

			square = nextSquaresVector[0] % 100; // set square to the value of 1st element (the remainder of the 1st number) in this vector

			// check if tied and if so, assign the next 2nd tied square if access squares one move ahead are smaller; this compares the access numbers
			if (isTied(nextSquaresVector))
			{
				// use tiebreaker function to determine the optimum next square;
				tieBreaker(nextSquaresVector, accessIndices, board, square);
			}

			board[(square)] = counter; // set the board square as visited with a counter

			// reset vectors
			nextSquaresVector.clear();
		}

		// print headers for counter,starting and ending squares for each tour
		printHeaders(counter, tours, myfile, square);

		cout << endl;

		// print chessboard to screen and a file
		printChessBoard(board, myfile);

		cout << endl << endl;
		myfile << endl << endl;

		// count full tours
		if (counter - 1 == boardSize)
			++totalFullTours;
				
		// count closed tours
		if (counter - 1 == 64 && (abs(square - tours) == 17 || abs(square - tours) == 15 || abs(square - tours) == 10 || abs(square - tours) == 6))
			++closedTours;		
	}

	// header for full tours
	cout << "Total full tours = " << totalFullTours << endl;
	cout << "Total closed tours = " << closedTours << endl << endl;
	myfile << "Total full tours = " << totalFullTours << endl ;
	myfile << "Total closed tours = " << closedTours << endl << endl;

	// close file
	myfile.close();
}