Knight's Tour

One of the more interesting puzzlers for chess buffs is the Knight's Tour Problem, originally proposed by 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?

Knight's tour

You can learn some algorithms to solve the problem here
Here I include the source code for a small Game using number keys(1,2,3,4,5,6,7,8) to move knights to eight positions around it.
1 :   Up 2  and Right 1
2:    Up 2 and  Left   1
3:   Left 2 and  Up   1
and so on..
8 : hint
In the hint i used "Warnsdorff's algorithm" to solve the problem. according to the algorithm you have to move knight to a legal square with minimum value specified in the table.
##############################################################################
#include <stdio.h>
void placeKnight(int position[],int board[][8][3]);
int moveKinght(int moveTo,int currentPosition[],int board[][8][3]);
void printBoard(int board[][8][3],int selection);
void heuristic(int board[][8][3]);
int isLegal(int moveTo,int currentPosition[],int board[][8][3]);
int main(){
int board[8][8][3]={0};
int currentPosition[2]={0,0};
heuristic(board);
placeKnight(currentPosition,board);
printBoard(board,0);
int input=0;
while(input>=0){
scanf("%d",&input);
if(input>=0&&input<8){
moveKnight(input,currentPosition,board);
heuristic(board);
printBoard(board,1);
}else if(input==8){
int selection=0;
printf("enter the selection :\n 0---> find legal moves\n 1---> find path you traveled\n 2--> hint\n");
scanf("%d",&selection);
if(selection>=0&&selection<=2){
printBoard(board,selection);
}else{
printf("invalied selection\n");
}
}
}
return 0;
}
void heuristic(int board[][8][3]){
int i;
int j;
int count=0;
int tempPosition[2];
for(i=0;i<8;i++){
for(j=0;j<8;j++){
tempPosition[0]=j;
tempPosition[1]=i;
int move;
for(move=0;move<8;move++){
count+=isLegal(move,tempPosition,board);
if(isLegal(move,tempPosition,board)==0){
//printf("%d , %d , moveto : %d\n",tempPosition[1],tempPosition[0],move);
}
}
board[i][j][2]=count;
count=0;
}
}
}
void printBoard(int board[][8][3],int selection){
int i;
int j;
for(i=0;i<8;i++){
for(j=0;j<8;j++){
printf(" %2d",board[i][j][selection]);
}
printf("\n");
}
}
void placeKnight(int position[],int board[][8][3]){
int i;
int j;
for(i=0;i<8;i++){
for(j=0;j<8;j++){
board[i][j][0]=0;
board[i][j][1]=0;
}
}
board[position[1]][position[0]][0]=1;
board[position[1]][position[0]][1]=1;
printf("The knight is initialized at ROW=%d   COLUMN=%d\n",position[1],position[0]);
}
int isLegal(int moveTo,int currentPosition[],int board[][8][3]){
int i;
int horizontal[8]={2,1,-1,-2,-2,-1,1,2};
int vertical[8]={-1,-2,-2,-1,1,2,2,1};
int count=board[currentPosition[1]][currentPosition[0]][1];
if((currentPosition[0]+horizontal[moveTo])<8&&
(currentPosition[0]+horizontal[moveTo])>=0&&
(currentPosition[1]+vertical[moveTo])<8&&
(currentPosition[1]+vertical[moveTo])>=0&&
board[currentPosition[1]+vertical[moveTo]][currentPosition[0]+horizontal[moveTo]][0]==0){
return 1;
}
else {
return 0;
}
}
int moveKnight(int moveTo,int currentPosition[],int board[][8][3]){
int i;
int horizontal[8]={2,1,-1,-2,-2,-1,1,2};
int vertical[8]={-1,-2,-2,-1,1,2,2,1};
int count=board[currentPosition[1]][currentPosition[0]][1];
if(isLegal(moveTo,currentPosition,board)){
currentPosition[0]+=horizontal[moveTo];
currentPosition[1]+=vertical[moveTo];
board[currentPosition[1]][currentPosition[0]][0]++;
board[currentPosition[1]][currentPosition[0]][1]=count+1;
}
else {
printf("the move is illegal\n");
}
}

Bubble Sort

It is the simplest sorting technique with low memory consumption and low performance compared to other sorting techniques.


here we just compare adjacent elements and swap if there not in order.
after first iteration the last element is correctly placed. iterate the same until everything sorted.

####################################################

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

#define SIZE 10


void bubbleSort(int * const data);

int main(int argc, char** argv) {

    int data[SIZE];

    int i;
    srand(time(NULL));

    for(i=0;i<SIZE;i++){
        data[i]=rand()%100+1;
        printf("%d\n",data[i]);
    }

    bubbleSort(data);

    printf("\n\n\n");
    for(i=0;i<SIZE;i++){
        printf("%d\n",data[i]);
    }
    return (EXIT_SUCCESS);
}


void bubbleSort(int * const data){

    void swap(int * const swap1,int * const swap2);

    int i;
    for(i=0;i<SIZE;i++){
        int j;
        for(j=0;j<SIZE-i-1;j++){
            if(data[j]>data[j+1]){
                swap(&data[j],&data[j+1]);
            }
        }
    }
}


void swap(int * const swap1,  int * const swap2){
    int  tmp=*swap1;
    *swap1=*swap2;
    *swap2=tmp;
}

Selection Sort

SELECTION SORT.  (Recursive)
1.Selection Sort search array and looking for the smallest element in the array and swap it with the first element.
2.Again Search balance array without using the first element. (recursive part)


######################################################################
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 20
void printArray(int data[]){
int i;
printf("\n\n");
for(i=0;i<SIZE;i++){
printf("%d \n",data[i]);
}
}
void selectionSort(int data[],int start);
int main(int argc, char** argv) {
int data[SIZE];
//fill the array with random data
srand(time(NULL));
int i;
for(i=0;i<SIZE;i++){
data[i]=rand()%(1000);
}
printf("before Sort");
printArray(data);
//sort Array
selectionSort(data,0);
printf("after Sort");
printArray(data);
return (EXIT_SUCCESS);
}
void selectionSort(int data[],int start){
int i;
int temp=start;
for(i=start;i<SIZE;i++){
if(data[temp]>data[i]){
temp=i;
}
}
int value=data[temp];
data[temp]=data[start];
data[start]=value;
//recursive
if(start<=SIZE){
selectionSort(data,(start+1));
}
}