BiLTeC

/*



  This program simulates a knights tour.

  It uses Brute-Force method to try moves.

  Also it uses accessibility heuristic to get better results.

  It counts the number of tries.



  Written by Omer CELIK-200222003

  Department of Mathematics and Computer Sciences



*/



// include header files

#include <iostream>
#include <iomanip>
#include <conio.h>
#include <cstdlib>

#include <ctime>


using namespace std;

// prototype of tryTour function

bool tryTour(int[8][8],int&);



// begin main function

void main()
{


// give time as random seed
srand(time(0));


// create chess board
int chessBoard[8][8]={0};


// declare trycounter
int trycount=0;

bool check;


// loop while get a full tour
do
{
check=tryTour(chessBoard,trycount);

}
while(check!=true);

cout<<\"Full tour found in \"<<trycount<<\". try.\nHere is the full tour.\"<<endl<<endl;


// print full tour
for(int i=0;i<8;i++){
for(int j=0;j<8;j++)
cout<<setw(5)<<chessBoard[i][j];
cout<<endl<<endl;
}

}

// end of main function



// begin tryTour function
bool tryTour(int chessBoard[8][8],int &counter)
{


// increase counter by one
counter++;


// declare loop variables
int i,j,m,a;


// set chessboard values to zero for new try
for(i=0;i<8;i++)
for(j=0;j<8;j++)
chessBoard[i][j]=0;



// declare an accesibility array (given)
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}};


// declare random starting row
int currentRow=rand()%8;


// declare random starting column
int currentColumn=rand()%8;


// go to that row and column
chessBoard[currentRow][currentColumn]=1;


// declare horizontal moves array
int horizontal[8];

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


// declare vertical moves array
int vertical[8];

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


// declare move number
int moveNumber;


// declare avaible move counter

int avaibleCount[8];



// loop 63 times for all moves
for (a=2;a<=64;a++){



// set avaible move counters values to 0

for (i=0;i<8;i++)

avaibleCount[i]=10;


// declare nextRow and nextColumn

int nextRow;
int nextColumn;



// loop 8 times (try 8 moves to find avaibles)

for(moveNumber=0;moveNumber<8;moveNumber++)

{

// set next row and column

// to check whether it is avaible or not

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



// if next row and column is between 0 and 8

// (in chess board) and if it is value is 0

// (if its avaible), increase avaible counter

// by accesibility number of that row and column
if (nextRow>=0 &&

nextRow<8 &&

nextColumn>=0 &&

nextColumn<8 &&

chessBoard[nextRow][nextColumn]==0)


avaibleCount[moveNumber]=accessibility[nextRow][nextColumn];


}


// check whether are there any change in avaibleCount

// if there is no change (if there is no way)

// break the loop.
if(avaibleCount[0]>=10&&avaibleCount[1]>=10&&

avaibleCount[2]>=10&&avaibleCount[3]>=10&&

avaibleCount[4]>=10&&avaibleCount[5]>=10&&

avaibleCount[6]>=10&&avaibleCount[7]>=10)
break;


// set min to 10 (greater that 8)
int min=10;


// find the minimum move number from avaibleCount and

// assign its subscript as moveNumber
for (m=0;m<8;m++){
if (avaibleCount[m]<=min){
min=avaibleCount[m];
moveNumber=m;
}
}



// change current row and column

// with new move numbers

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



// go to that row and column
chessBoard[currentRow][currentColumn]=a;
}


// check whether the tour is completed or not

// if tour is completed, return true
for (i=0;i<8;i++){
for (j=0;j<8;j++)
if(chessBoard[i][j]==64)
return true;
}


// if tour is not completed return false
return false;

}