Eular's Knight Tour in C++

                                                          Eular's Knight Tour

This is the start to understanding the board.There is not much to describe here unless you are new to array

#include <iostream>
#include <iomanip>
#include <time.h>
using namespace std;
int chessBoard1[8][8] = { 0 };
 
int counter = 0;
int main(void){
 chessBoard1[2][6] = 1;
 chessBoard1[2][2] = 2;
 for (int i = 0; i < 8; i++) 
 {
  for (int j = 0; j < 8; j++)
  {
   printf("%2d ",  chessBoard1[i][j]);
   
  }
 cout << "\n";
 }
 cin.get();
}

The out put is:
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  2  0  0  0  1  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0

As we understand the board array now we can proceed..

/*


Author: M Hasan
Date: 16/2/2015 11:51:08 AM
Description:
(Knight’s Tour) One of the more interesting puzzlers for chess buffs is the Knight's Tour problem, originally proposed by
the mathematician Euler. The question is this: Can the chess piece called the knight move around an empty chessboard and touch
each of the 64 squares once and only once? We study this intriguing problem in depth here.
The knight makes L-shaped moves (over two in one direction and then over one in a perpendicular direction). Thus, from a
square in the middle of an empty chessboard, the knight can make eight different moves (numbered 0 through 7) as shown in
Fig. 6.25.
a) Draw an 8-by-8 chessboard on a sheet of paper and attempt a Knight's Tour by hand. Put a 1 in the first square you
move to, a 2 in the second square, a 3 in the third, etc. Before starting the tour, estimate how far you think you will get,
remembering that a full tour consists of 64 moves. How far did you get? Were you close to the estimate?

b) Now let us develop a program that will move the knight around a chessboard. The board itself is represented by an 8-
by-8 double-subscripted array board. Each of the squares is initialized to zero. We describe each of the eight possible
moves in terms of both their horizontal and vertical components. For example, a move of type 0 as shown in Fig. 6.25
consists of moving two squares horizontally to the right and one square vertically upward. Move 2 consists of moving
one square horizontally to the left and two squares vertically upward. Horizontal moves to the left and vertical moves
upward are indicated with negative numbers. The eight moves may be described by two single-subscripted arrays, horizontal
and vertical, as follows:

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

Let the variables currentRow and currentColumn indicate the row and column of the knight's current position on
the board. To make a move of type moveNumber, where moveNumber is between 0 and 7, your program uses the
statements

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

Keep a counter that varies from 1 to 64. Record the latest count in each square the knight moves to. Remember to test
each potential move to see if the knight has already visited that square. And, of course, test every potential move to
make sure that the knight does not land off the chessboard. Now write a program to move the knight around the chessboard.
Run the program. How many moves did the knight make?
*/

//To make it simple we will end the run when Best move is over 55

/*****************header.h*****************************
****************************************************/

int totalGame = 0;
int counter = 0;
//the array which holds the biggest record
int recordHolder[8][8] = { 0 };
int flag = 0;
int moveNumber = 0;// moveNumberB1=0, moveNumberB2=0, moveNumberB3=0;
int m = 1;
//These two single subscript arrays will be used to move the knight as L shape according to array subscript
int horizontal[8];
int vertical[8];
//Knight's valid movement
 
//declare currrent position
int currentRow;
int currentColumn;
//8x8 Chessboard
int chessBoard[8][8] = { 0 };

/**********************************************************************/

/*****************************function.h**************************/

#include "header.h"
 
void clearChessBoard(void){
 
 int i, j;
 
 for (i = 0; i < 8; i++)
 {
  for (j = 0; j < 8; j++)
  {
   chessBoard[i][j] = 0;
  }
 }
 
}
 
void initialize(){
 
 flag = 0;
 clearChessBoard();
 currentColumn = rand() % 8;
 currentRow = rand() % 8;
 chessBoard[currentRow][currentColumn] = 1;
 counter = 1, m = 0;
 
}
 
int randomiseMovement(void){
 
 return rand() % 8;
 
}
int validOrNot(int mn){
 
 return (
  chessBoard[currentRow + vertical[mn]][currentColumn + horizontal[mn]] == 0
  &&
  (currentRow + vertical[mn]) >= 0
  &&
  (currentRow + vertical[mn])<8
  &&
  (currentColumn + horizontal[mn]) >= 0
  &&
  (currentColumn + horizontal[mn]) <8);
 
}
void moveKnight(int moveno){
 
 currentRow += vertical[moveno];
 currentColumn += horizontal[moveno];
 //printf("Knight has moved to chessBoard[%d][%d].\n", currentRow, currentColumn);
 counter++;
 //printf("Move count is %d.\n", counter);
 chessBoard[currentRow][currentColumn] = counter;
 
}
int isThereEmptyLocationAround(){
 int i;
 for (i = 0; i < 8; i++)
 {
  if (validOrNot(i))
   return 1;
 }
 return 0;
}
 
 
void printRecordArray(int b[][8]){
 
 int i, j;
 printf("\n BIGGEST RECORDED ARRAY IS: \n");
 printf("\n");
 for (i = 0; i < 8; i++)
 {
  printf("\n");
  for (j = 0; j < 8; j++)
  {
   printf("%2d ", b[i][j]);
 
  }
 }
 
 printf("\n");
}
 
void copyRecordArray(int b[][8]){
 
 int i, j;
 
 for (i = 0; i < 8; i++)
 {
  for (j = 0; j < 8; j++)
  {
   recordHolder[i][j] = b[i][j];
  }
 }
 
}
int printBoard(void){
 totalGame++;
 int i, j, onesCount = 0;
 printf("\n");
 for (i = 0; i < 8; i++)
 {
  printf("\n");
  for (j = 0; j < 8; j++)
  {
   printf("%2d ", chessBoard[i][j]);
   if (chessBoard[i][j]>0)
    onesCount++;
  }
 }
 return onesCount;
 
}
/**************************main.cpp**********************************/
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <time.h>
#include "function.h";
using namespace std;
 
 
int main(void){
 initialize();
 int biggestCoverage = 0;
 
 //initialize horizontal move of knight
 horizontal[0] = 2;
 horizontal[1] = 1;
 horizontal[2] = -1;
 horizontal[3] = -2;
 horizontal[4] = -2;
 horizontal[5] = -1;
 horizontal[6] = 1;
 horizontal[7] = 2;
 
 //intialize vertical move of the knight
 vertical[0] = -1;
 vertical[1] = -2;
 vertical[2] = -2;
 vertical[3] = -1;
 vertical[4] = 1;
 vertical[5] = 2;
 vertical[6] = 2;
 vertical[7] = 1;
 
 srand(time(NULL));
 
 printf("================================================================================\n");
 
 
 while (biggestCoverage <= 55)
 {
 
  initialize();
 
  moveNumber = randomiseMovement();
  printf("Move randomised to: %d\n", moveNumber);
 
  printf("============================================================================\n");
  printf("STARTING POS IS: [%d][%d]\n", currentRow, currentColumn);
 
  do {
 
   //First check if moveNumber position is available 
   //Then move the knight accordingly
   if (validOrNot(moveNumber))
    moveKnight(moveNumber);
   else if (isThereEmptyLocationAround())
   {
    moveNumber = randomiseMovement();
   }
   else
   {
    flag = -1;
   }
  } while (flag != -1);
 
  m = printBoard();
  printf("\n\nTotal move = %d",m);
  printf("\n\nTotal Game Board = %d", totalGame);
  if (m>biggestCoverage){
   biggestCoverage = m;
   copyRecordArray(chessBoard);
 
  }
  printf("\n\nBest Move: %d\n", biggestCoverage);
  printRecordArray(recordHolder);
  
 }
 
 printf("\n");
  cin.get();
 
}

/*****************************output***********************************/

......................

......................

0  0  0 19  8  0  0 37

Total move = 37

Total Game Board = 10

Best Move: 46

 BIGGEST RECORDED ARRAY IS:


 0 29 34  0 26 31  0  0
 0  4 27 30 33  0 25 12
28 35  0  3 38 13 32  0
 5  0 37 14  0  2 11 24
36 15  6 39 18 23  0  1
 0 42 17 22  7 10 45  0
16 21 40  0 44 19  8  0
41  0 43 20  9  0  0 46
Move randomised to: 3
============================================================================
STARTING POS IS: [5][3]


 0  0 43 26 47  6 21  0
44 25 46  0  0 27 48  7
 0 42  0 24  5 20  0 22
14 45  0  0 28 23  8 33
41  2 13  4 19 34 29  0
 0 15 18  1 12  9 32 37
17 40  3  0 35 38 11 30
 0  0 16 39 10 31 36  0

Total move = 48

Total Game Board = 11

Best Move: 48

 BIGGEST RECORDED ARRAY IS:


 0  0 43 26 47  6 21  0
44 25 46  0  0 27 48  7
 0 42  0 24  5 20  0 22
14 45  0  0 28 23  8 33
41  2 13  4 19 34 29  0
 0 15 18  1 12  9 32 37
17 40  3  0 35 38 11 30
 0  0 16 39 10 31 36  0
Move randomised to: 3
============================================================================
STARTING POS IS: [0][6]


 0  0  0 10  0  0  1 32
 0 11  0  0  2 29  0  0
 0  0  3 12  9  0 31  0
 4  0 22  0 30 13 28  0
23  0  5  0  0  8  0 14
18  0 24 21  6 15  0 27
 0  0 19 16 25  0  7  0
 0 17  0  0 20  0 26  0

Total move = 32

Total Game Board = 12

Best Move: 48

 BIGGEST RECORDED ARRAY IS:


 0  0 43 26 47  6 21  0
44 25 46  0  0 27 48  7
 0 42  0 24  5 20  0 22
14 45  0  0 28 23  8 33
41  2 13  4 19 34 29  0
 0 15 18  1 12  9 32 37
17 40  3  0 35 38 11 30
 0  0 16 39 10 31 36  0
Move randomised to: 2
============================================================================
STARTING POS IS: [4][1]


 0  0 12  0  4  0  0  0
11  0  3  0  0 20 23  0
 2 13  0 31  0  5  0 21
 0 10  0  0  0 22 19 24
14  1 32  9 30 25  6  0
33  0 15 26  0  8 37 18
 0 27  0 35 16 29  0  7
 0 34  0 28  0 36 17 38

Total move = 38

Total Game Board = 13

Best Move: 48

 BIGGEST RECORDED ARRAY IS:


 0  0 43 26 47  6 21  0
44 25 46  0  0 27 48  7
 0 42  0 24  5 20  0 22
14 45  0  0 28 23  8 33
41  2 13  4 19 34 29  0
 0 15 18  1 12  9 32 37
17 40  3  0 35 38 11 30
 0  0 16 39 10 31 36  0
Move randomised to: 5
============================================================================
STARTING POS IS: [0][5]


 0 15  0  0  0  1 12  0
 0  0  0 14 11  0  0  0
 6  0 16  0  2 13  0  0
 0  0  7  0 17 10  0  0
 0  5  0  3  8  0 18  0
 0  0  0  0  0  0  9  0
 0  0  4  0  0 19  0  0
 0  0  0  0  0  0  0 20

Total move = 20

Total Game Board = 14

Best Move: 48

 BIGGEST RECORDED ARRAY IS:


 0  0 43 26 47  6 21  0
44 25 46  0  0 27 48  7
 0 42  0 24  5 20  0 22
14 45  0  0 28 23  8 33
41  2 13  4 19 34 29  0
 0 15 18  1 12  9 32 37
17 40  3  0 35 38 11 30
 0  0 16 39 10 31 36  0
Move randomised to: 0
============================================================================
STARTING POS IS: [5][3]


 0  6 15  0  0  0  0 32
 0  0  0  5 14 31 22  0
 7  0  0 16 23  4 13  0
 0  0 24  0 12 21 30  3
25  8 11  0 17  2  0  0
10  0 26  1  0  0 20 29
 0  0  9  0 27 18  0  0
 0  0  0  0  0  0 28 19

Total move = 32

Total Game Board = 15

Best Move: 48

 BIGGEST RECORDED ARRAY IS:


 0  0 43 26 47  6 21  0
44 25 46  0  0 27 48  7
 0 42  0 24  5 20  0 22
14 45  0  0 28 23  8 33
41  2 13  4 19 34 29  0
 0 15 18  1 12  9 32 37
17 40  3  0 35 38 11 30
 0  0 16 39 10 31 36  0
Move randomised to: 2
============================================================================
STARTING POS IS: [4][7]


42  0  0  0  0  3 32  0
 0  0 41  4 33  0  9 18
 0  5 34  0  8 17  2 31
35  0  7 40  0 10 19 16
 6 39  0  0 26 15 30  1
23 36  0 14 11 20 27  0
38 13 22 25  0  0  0 29
 0 24 37 12 21 28  0  0

Total move = 42

Total Game Board = 16

Best Move: 48

 BIGGEST RECORDED ARRAY IS:


 0  0 43 26 47  6 21  0
44 25 46  0  0 27 48  7
 0 42  0 24  5 20  0 22
14 45  0  0 28 23  8 33
41  2 13  4 19 34 29  0
 0 15 18  1 12  9 32 37
17 40  3  0 35 38 11 30
 0  0 16 39 10 31 36  0
Move randomised to: 3
============================================================================
STARTING POS IS: [4][7]


 0  0 14  0 24 11  0  0
15  4 25 12  0  0  0 10
26 13 16  3 32 23  0  0
37  0  5  0 17  2  9 22
 0 27 36 31  0 33 18  1
 0 30  0  6 35  8 21  0
 0  0 28  0  0  0 34 19
29  0  0  0  7 20  0  0

Total move = 37

Total Game Board = 17

Best Move: 48

 BIGGEST RECORDED ARRAY IS:


 0  0 43 26 47  6 21  0
44 25 46  0  0 27 48  7
 0 42  0 24  5 20  0 22
14 45  0  0 28 23  8 33
41  2 13  4 19 34 29  0
 0 15 18  1 12  9 32 37
17 40  3  0 35 38 11 30
 0  0 16 39 10 31 36  0
Move randomised to: 2
============================================================================
STARTING POS IS: [5][0]


 0  0  0  0  0 19  0  0
 0  0  3 18  0  0  0  0
 4  0  0  0 20  0  0  0
 0  2  5  0 17  0  0  8
12  0  0 21  6  9 24  0
 1 28 13 10 23 16  7  0
 0 11 22 27 14  0  0 25
29  0  0  0  0 26 15  0

Total move = 29

Total Game Board = 18

Best Move: 48

 BIGGEST RECORDED ARRAY IS:


 0  0 43 26 47  6 21  0
44 25 46  0  0 27 48  7
 0 42  0 24  5 20  0 22
14 45  0  0 28 23  8 33
41  2 13  4 19 34 29  0
 0 15 18  1 12  9 32 37
17 40  3  0 35 38 11 30
 0  0 16 39 10 31 36  0
Move randomised to: 0
============================================================================
STARTING POS IS: [3][0]


36 33  0  0 14 55  4  0
 0  0 35 32  3 24 15 56
34 37  2 25 16 13 54  5
 1 26 17 50 31  6 23 44
18 49 38  7 42 45 12 53
27  8 19 46 51 30 43 22
48 39 28  9 20 41 52 11
 0  0 47 40 29 10 21  0

Total move = 56

Total Game Board = 19

Best Move: 56

 BIGGEST RECORDED ARRAY IS:


36 33  0  0 14 55  4  0
 0  0 35 32  3 24 15 56
34 37  2 25 16 13 54  5
 1 26 17 50 31  6 23 44
18 49 38  7 42 45 12 53
27  8 19 46 51 30 43 22
48 39 28  9 20 41 52 11
 0  0 47 40 29 10 21  0