# Add Accessability Heuristic to Euler’s Knight’s Tour implementation as described below. (This code can make full tours of board now!!!)

```/*

Name:
Copyright: Deitel C How to Program
Author: StackOverflow1453
Date: 5/20/2013 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?

c) After attempting to write and run a Knight's Tour program, you have probably developed some valuable insights. We
will use these to develop a heuristic (or strategy) for moving the knight. Heuristics do not guarantee success, but a
carefully developed heuristic greatly improves the chance of success. You may have observed that the outer squares are
in some sense more troublesome than the squares nearer the center of the board. In fact, the most troublesome, or inaccessible,
squares are the four corners.
Intuition may suggest that you should attempt to move the knight to the most troublesome squares first and leave
open those that are easiest to get to so that when the board gets congested near the end of the tour there will be a greater
chance of success.
We may develop an “accessibility heuristic” by classifying each of the squares according to how accessible they
are and always moving the knight to the square (within the knight's L-shaped moves, of course) that is most inaccessible.
We label a double-subscripted array accessibility with numbers indicating from how many squares each particular
square is accessible. On a blank chessboard, the center squares are therefore rated as 8s, the corner squares are
rated as 2s, and the other squares have accessibility numbers of 3, 4, or 6 as follows:

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

Now write a version of the Knight's Tour program using the accessibility heuristic. At any time, the knight should move
to the square with the lowest accessibility number. In case of a tie, the knight may move to any of the tied squares.
Therefore, the tour may begin in any of the four corners. [Note: As the knight moves around the chessboard, your program
should reduce the accessibility numbers as more and more squares become occupied. In this way, at any given
time during the tour, each available square's accessibility number will remain equal to precisely the number of squares
from which that square may be reached.] Run this version of your program. Did you get a full tour? Now modify the
program to run 64 tours, one from each square of the chessboard. How many full tours did you get?

*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//prototypes
int randomiseMovement(void);
int printBoard(void);
void clearChessBoard(void);
void copyRecordArray(int c[][8]);
void printRecordArray(int b[][8]);
int validOrNot(int mn);
void moveKnight(int moveno);
void initialize(void);
int isThereEmptyLocationAround();
int determineLowestAccessNumberedMove(int p, int s);
//GLOBAL VARIABLES

//these are declared here for each function to reach!
//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];
int iteration=0;

//declare currrent position
int currentRow;
int currentColumn;

//Movement counter
int count=0;
//chessboard
int chessBoard[8][8]={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;

//access array must be declared globally so that everyfunction can access it!
int access[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 };

int main(void){

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));

currentRow=randomiseMovement();
currentColumn=randomiseMovement();

printf("____________________________________________________________________________\n");
while (biggestCoverage<64){
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

moveNumber=determineLowestAccessNumberedMove(currentRow, currentColumn);

if(validOrNot(moveNumber))
moveKnight(moveNumber);
else if (isThereEmptyLocationAround())
{
moveNumber=randomiseMovement();
}
else
{
flag=-1;
}
}
while (flag!=-1);

m=printBoard();
if(m>biggestCoverage){
biggestCoverage=m;
copyRecordArray(chessBoard);

}
printf("\n\nGINES REKORU: %d\n", biggestCoverage);
printRecordArray(recordHolder);
}

printf("\n");
getch();

return 0;
}

int randomiseMovement(void){

return rand()%8;

}

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 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){
printf("Subscript is %d\n",moveno);
currentRow+=vertical[moveno];
currentColumn+=horizontal[moveno];
printf("Knight has moved to chessBoard[%d][%d].\n",currentRow,currentColumn);
count++;
printf("Move count is %d.\n",count);
chessBoard[currentRow][currentColumn]=count;

}

int isThereEmptyLocationAround(){
int i;
for (i = 0; i < 8; i++)
{
if(validOrNot(i))
return 1;
}
return 0;
}

int printBoard(void){

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;

}

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");
}

//clears the board before each iteration
void clearChessBoard(void){

int i,j;

for (i = 0; i < 8; i++)
{
for (j = 0; j < 8; j++)
{
chessBoard[i][j]=0;
}
}

}

//resets the board
void initialize(void){

iteration++;
printf("%d th ITERATION",iteration);
flag=0;
clearChessBoard();
currentColumn=randomiseMovement();
currentRow=randomiseMovement();
chessBoard[currentRow][currentColumn]=1;
count=1,m=0;

}

int determineLowestAccessNumberedMove(int cRow, int cCol){

int i;
int smlAccessNo=moveNumber;
for (i = 1; i < 8; i++)
{
if(    validOrNot(i) && (access[cRow+vertical[i]][cCol+horizontal[i]])<(access[cRow+vertical[smlAccessNo]] [cCol+horizontal[smlAccessNo]]))
smlAccessNo=i;
}

return smlAccessNo;

}
```