Knights tour

edited.cpp

//=========================================================
//File: knightsTour.cpp
//Author: Davis Giang
//Description: Knights tour solver
//Date: 4/6/2016
//=========================================================

#include <iostream>
#include <iomanip>

const int BOARD_SIZE=5; 

class Board {
public: 
	Board(); 
	int knightsBoard[BOARD_SIZE][BOARD_SIZE];
	void getBoard(int boardOut[][BOARD_SIZE]); 
	void printBoard(int board[][BOARD_SIZE]);
};

int solveKnightsTour(Board board, int row, int col, int currentMoveNum, int &solutions); 

//=========================================================
//Function:Board
//Description: Initializes knights board to 0
//=========================================================
Board::Board() {
	for(int row=0; row<BOARD_SIZE; row++)
		for(int col=0; col<BOARD_SIZE; col++) 
			knightsBoard[row][col]=0; 
};

//================================================================
// Description:  
//	Recursively solves the knights tour using brute force.  
//	Prints any solutions if finds.
// Args:
//   board (I/O) - the board we’re working with 
//		(board with previous moves and size)
//   row (I) - the row we’re going to attempt to place the knight on this move.
//   col (I) - the column we’re going to attempt place the knight on this move.
//   currentMoveNumber (I) - the move we’re making 
//	 (1=first placement, 16=last placement on 4x4 board)
//     Note: row and col may be invalid (<0 or >=boardsize) 
//		or already taken (<currentMoveNum)
//  Returns: 
//	The number of solutions the given board and move leads to
//===============================================================
int solveKnightsTour(Board board, int row, int col, int currentMoveNum, int &solutions) {
	Board currentBoard;
	board.getBoard(currentBoard.knightsBoard); 

	if(currentBoard.knightsBoard[row][col]!=0 || currentBoard.knightsBoard[row][col]<0)
		return 0; 

	if(currentMoveNum==BOARD_SIZE*BOARD_SIZE) {
		solutions++; 
		std::cout << "A solution has been found" << std::endl;
		board.printBoard(board.knightsBoard);
		return 1;
	}

	if(currentBoard.knightsBoard[row][col]==0 && row>=0 && row<BOARD_SIZE && col>=0 && col<BOARD_SIZE) {
		currentBoard.knightsBoard[row][col]=currentMoveNum;
		currentMoveNum++;
		solveKnightsTour(currentBoard, row-2, col-1, currentMoveNum, solutions); 
		solveKnightsTour(currentBoard, row-2, col+1, currentMoveNum, solutions); 
		solveKnightsTour(currentBoard, row+2, col-1, currentMoveNum, solutions); 
		solveKnightsTour(currentBoard, row+2, col+1, currentMoveNum, solutions); 
		solveKnightsTour(currentBoard, row+1, col+2, currentMoveNum, solutions); 
		solveKnightsTour(currentBoard, row+1, col-2, currentMoveNum, solutions); 
		solveKnightsTour(currentBoard, row-1, col+2, currentMoveNum, solutions); 
		solveKnightsTour(currentBoard, row-1, col-2, currentMoveNum, solutions); 
	}

	return 0;
}
//=========================================================
//Function:printBoard
//Description: prints out the board
//=========================================================
void Board::printBoard(int board[][BOARD_SIZE]) {
	for(int row=0; row<BOARD_SIZE; row++) {
		for(int col=0; col<BOARD_SIZE; col++) {
			std::cout << std::setw(4) << board[row][col];
		}
		std::cout << std::endl;
	}
	std:: cout << std::endl;
}

//=========================================================
//Function:getBoard
//Description: gets a copy of the board to date
//=========================================================
void Board::getBoard(int boardOut[][BOARD_SIZE]) {
	for(int row=0; row<BOARD_SIZE; row++) 
		for(int col=0; col<BOARD_SIZE; col++) {
			boardOut[row][col]=knightsBoard[row][col];
		}
}

//=========================================================
//Function:main
//Description: 
//=========================================================
void main() {
	int row; 
	int col; 
	char ch;  
	Board knightsT; 
	int solutions=0; 

	std::cout << "Welcome to the knights tour!" << std::endl;
	std::cout << "The board size is: " << BOARD_SIZE << std::endl;

	do {
		std::cout << "Starting position(row, col): "; 
		std::cin >> row >> ch >> col; 
	} while(row<0 || row>BOARD_SIZE || col<0 || col>BOARD_SIZE);

	if(row>0) 
		row=row-1;
	if(col>0)
		col=col-1;

	solveKnightsTour(knightsT, row, col, 1, solutions); 

	std::cout << "Total solutions:" << solutions << std::endl; 
}

knightstour.cpp

//=========================================================
//File: knightsTour.cpp
//Author: Davis Giang
//Description: Knights tour solver
//Date: 4/6/2016
//=========================================================

#include <iostream>
#include <iomanip>

const int BOARD_SIZE=4;

class Board {
public: 
	Board(); 
	int knightsBoard[BOARD_SIZE][BOARD_SIZE];
	void getBoard(int boardOut[][BOARD_SIZE]); 
	void printBoard(int board[][BOARD_SIZE]);
};

int solveKnightsTour(Board board, int row, int col, int currentMoveNum, int &solutions); 

//=========================================================
//Function:Board
//Description: Initializes knights board to 0
//=========================================================
Board::Board() {
	for(int row=0; row<BOARD_SIZE; row++)
		for(int col=0; col<BOARD_SIZE; col++) 
			knightsBoard[row][col]=0; 
};

//================================================================
// Description:  
//	Recursively solves the knights tour using brute force.  
//	Prints any solutions if finds.
// Args:
//   board (I/O) - the board we’re working with 
//		(board with previous moves and size)
//   row (I) - the row we’re going to attempt to place the knight on this move.
//   col (I) - the column we’re going to attempt place the knight on this move.
//   currentMoveNumber (I) - the move we’re making 
//	 (1=first placement, 16=last placement on 4x4 board)
//     Note: row and col may be invalid (<0 or >=boardsize) 
//		or already taken (<currentMoveNum)
//  Returns: 
//	The number of solutions the given board and move leads to
//===============================================================
int solveKnightsTour(Board board, int row, int col, int currentMoveNum, int &solutions) {
	Board currentBoard;
	board.getBoard(currentBoard.knightsBoard); 
	
	if(currentMoveNum>BOARD_SIZE*BOARD_SIZE) {
		solutions++; 
		std::cout << "A solution has been found" << std::endl;
		board.printBoard(currentBoard.knightsBoard);
		return 1;
	}


	else if(board.knightsBoard[row][col]!=0 || board.knightsBoard[row][col]<0 || board.knightsBoard[row][col]>=BOARD_SIZE) 
		return 0; 
	

	else if(currentBoard.knightsBoard[row][col]==0 && row>=0 && row<BOARD_SIZE && col>=0 && col<BOARD_SIZE) {
		currentBoard.knightsBoard[row][col]=currentMoveNum;
		currentMoveNum++;
		solveKnightsTour(currentBoard, row-2, col-1, currentMoveNum, solutions); 
		solveKnightsTour(currentBoard, row-2, col+1, currentMoveNum, solutions); 
		solveKnightsTour(currentBoard, row+2, col-1, currentMoveNum, solutions); 
		solveKnightsTour(currentBoard, row+2, col+1, currentMoveNum, solutions); 
		solveKnightsTour(currentBoard, row+1, col+2, currentMoveNum, solutions); 
		solveKnightsTour(currentBoard, row+1, col-2, currentMoveNum, solutions); 
		solveKnightsTour(currentBoard, row-1, col+2, currentMoveNum, solutions); 
		solveKnightsTour(currentBoard, row-1, col-2, currentMoveNum, solutions); 
	}
}
//=========================================================
//Function:printBoard
//Description: prints out the board
//=========================================================
void Board::printBoard(int board[][BOARD_SIZE]) {
	for(int row=0; row<BOARD_SIZE; row++) {
		for(int col=0; col<BOARD_SIZE; col++) {
			std::cout << std::setw(4) << board[row][col];
		}
		std::cout << std::endl;
	}
	std:: cout << std::endl;
}

//=========================================================
//Function:getBoard
//Description: gets a copy of the board to date
//=========================================================
void Board::getBoard(int boardOut[][BOARD_SIZE]) {
	for(int row=0; row<BOARD_SIZE; row++) 
		for(int col=0; col<BOARD_SIZE; col++) {
			boardOut[row][col]=knightsBoard[row][col];
		}
}

//=========================================================
//Function:main
//Description: 
//=========================================================
void main() {
	int boardSize; 
	int row; 
	int col; 
	char ch;  
	Board knightsT; 
	int solutions=0; 

	std::cout << "Welcome to the knights tour!" << std::endl;
	do {
		std::cout << "Board Size(4-7): ";
		std::cin >> boardSize;
	} while(boardSize<4 || boardSize>7); 

	do {
		std::cout << "Starting position(row, col): "; 
		std::cin >> row >> ch >> col; 
	} while(row<0 || row>boardSize || col<0 || col>boardSize);

	if(row>0) 
		row=row-1;
	if(col>0)
		col=col-1;

	solveKnightsTour(knightsT, row, col, 1, solutions); 

	std::cout << "Total solutions:" << solutions << std::endl; 
}