Maze Traversal

A common problem in AI(Artificial Intelligent) is solving a Maze. There are number of algorithms to solve different type of mazes and number of Algorithms to create a random maze of a particular type.

there are number of types of mazes. They are classified according to Dimension, Hyper dimension, Topology, Tessellation, Routing, Texture, and Focus. Each have its own properties.

For more Details on Algorithms to Solve Maze go Here
for types of Mazes and maze generation and solution algorithms click here

Below I generate a random maze with Recursive backtracking and Solve it almost same algorithm call wall follower.
The basic idea of the solution is You just place your Right hand on the right side wall and just go until find the exit point. This will eventually guide you to the exit point. this method will suitable for any type of 2D Mazes but it is a little bit slow compared to other methods.

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


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

#define WALL 1
#define BORDER 2
#define PATH 3

#define TEMPSOL 4
#define SOL 5

#define START 0
#define END 6

#define SIZE 30

void printMaze(int floor[][SIZE]);
void generateMaze(int floor[][SIZE],int start[]);
void solveMaze(int floor[][SIZE],int start[]);

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

    int floor[SIZE][SIZE];

    int start[2]={1,1};
    generateMaze(floor,start);
    printMaze(floor);
   
    solveMaze(floor,start);
    printMaze(floor);

    return (EXIT_SUCCESS);
}


void printMaze(int floor[][SIZE]){
    printf("\n");
    int i;
    int j;
    for(j=SIZE-1;j>=0;j--){
        for(i=0;i<SIZE;i++){
            switch(floor[i][j]){
                case BORDER:
                    printf("##");
                    break;
                case WALL:
                    printf("WW");
                    break;
                case PATH:
                    printf("  ");
                    break;
                case START:
                case TEMPSOL:
                    printf("ST");
                    break;
                case END:
                    printf("EX");
                    break;
                case SOL:
                    printf("* ");
                    break;
            }
        }
        printf("\n");
    }
}

void solveMaze(int floor[][SIZE], int start[]){
    int recursiveSolve(int floor[][SIZE],int position[]);
    recursiveSolve(floor,start);
    floor[start[0]][start[1]]=START;

}

void generateMaze(int floor[][SIZE],int startPosition[]){
    void recursiveBackTrack(int floor[][SIZE],int position[]);

    //initialize Maze Arena
    int i;
    int j;
    for(i=0;i<SIZE;i++){
        for(j=0;j<SIZE;j++){
            floor[i][j]=BORDER;
        }
    }
    for(i=1;i<SIZE-1;i++){
        for(j=1;j<SIZE-1;j++){
            floor[i][j]=WALL;
        }
    }

    //set the StartPosition
    srand(time(NULL));
    recursiveBackTrack(floor,startPosition);
    floor[startPosition[0]][startPosition[1]]=START;
    //set the EndPosition
    int endPosition[2]={SIZE-2,SIZE-2};
    floor[endPosition[0]][endPosition[1]]=END;
}

int  recursiveSolve(int floor[][SIZE],int currentPosition[]){
    int neighbour[4][3]={{floor[currentPosition[0]+1][currentPosition[1]],currentPosition[0]+1,currentPosition[1]},       //right
                             {floor[currentPosition[0]][currentPosition[1]+1],currentPosition[0],currentPosition[1]+1},       //up
                             {floor[currentPosition[0]-1][currentPosition[1]],currentPosition[0]-1,currentPosition[1]},       //left
                             {floor[currentPosition[0]][currentPosition[1]-1],currentPosition[0],currentPosition[1]-1}};      //down
   
    int i;
    if(floor[currentPosition[0]][currentPosition[1]]==END){
        return 1;
    }else{
        for(i=0;i<4;i++){
            if(neighbour[i][0]==PATH||neighbour[i][0]==END){
                 int t[2]={neighbour[i][1],neighbour[i][2]};
                floor[currentPosition[0]][currentPosition[1]]=TEMPSOL;
                if(recursiveSolve(floor,t)==1){
                    floor[currentPosition[0]][currentPosition[1]]=SOL;
                    return 1;
                }
            }
        }
        floor[currentPosition[0]][currentPosition[1]]=PATH;
        return 0;
    }

}

void recursiveBackTrack(int floor[][SIZE],int currentPosition[]){
    int checkPositions(int floor[][SIZE],int position[],int comingFrom);
    floor[currentPosition[0]][currentPosition[1]]=PATH;

   
    int eachDirection[4][2]={{currentPosition[0]+1,currentPosition[1]},       //right
                             {currentPosition[0],currentPosition[1]+1},       //up
                             {currentPosition[0],currentPosition[1]-1},      //down
                             {currentPosition[0]-1,currentPosition[1]}};       //left
                            

   
    int directions[4]={0,1,2,3};
    int i;
   
    for(i=4;i>0;i--){
        int randomDirection=rand()%i;
        int tempDirection=directions[randomDirection];
        directions[randomDirection]=directions[i-1];
        if(checkPositions(floor,eachDirection[tempDirection],(3-tempDirection))==1){
            recursiveBackTrack(floor,eachDirection[tempDirection]);
        }
    }

}

int checkPositions(int floor[][SIZE],int position[],int comingFrom){
    int eachDirection[4][2]={{position[0]+1,position[1]},       //right
                             {position[0],position[1]+1},       //up
                             {position[0],position[1]-1},      //down
                             {position[0]-1,position[1]}};       //left
   
    if(floor[position[0]][position[1]]==WALL){                     //check weather the cell is unused
        int i;
        for(i=0;i<4;i++){
            if(i!=comingFrom && floor[eachDirection[i][0]][eachDirection[i][1]]==PATH){      //skip the previous cell &&
                    return 0;
            }
        }     
        return 1;
    }else{
        return 0;
    }
}

Find Palindrome

A palindrome is a word, phrase number or other sequence of units that can be read the same way in either direction
Eg:
Was it a rat I saw.     A nut for a jar of tuna.     Doc note I dissent A fast never prevents a fatness I diet on cod.    A man a plan, a canal Panama
here i try a recursive solution to find weather a sentence is a palindrome.
my solution is case sensitive and exclude spaces.
########################################################################
#include <stdio.h>
#include <stdlib.h>

int testPalindrome(char data[],int start,int end);
int main(int argc, char** argv) {
char string[]="a man a plan a canal panama";
//was it a rat I saw
//a nut for a jar of tuna
//dammit I m mad
//doc note i dissent a fast never prevents a fatness I diet on cod
int size=0;
char c;
while(c!=''){
c=string[size];
printf("%c",c);
size++;
}
printf("\n\n");
if(testPalindrome(string,0,size-2)==1){
printf("this is a Palindrome\n");
}else{
printf("this is not a Palindrome\n");
}
return (EXIT_SUCCESS);
}
int testPalindrome(char data[],int start,int end){
int i=1;
if(start>=end){
return 1;
}else if(data[start]==' '){
start++;
i=testPalindrome(data,start,end);
}else if(data[end]==' '){
end--;
i=testPalindrome(data,start,end);
}else if(data[start]==data[end]){
i=testPalindrome(data,(start+1),(end-1));
}else{
return 0;
}
return i;
}

Bucket Sort

A bucket sort begins with single subscripted array of positive integers to be sorted and a double subscripted array of integers with rows subscripted from 0 to 9 and columns subscripted from 0 to n-1 where n is the number of values in the array to be sorted.
Algorithm
1. Loop through the single subscripted array and place each of its values in a row of the bucket array based on its ones dight.
2.loop through bucket array. copy each element and past it in data array.
3.Repeat the process for each subsequent positions (tens, hundreds,thousands)
Note:
double subscripted array (bucket ) is 10 times larger than data array. which consume a considerable amount of memory. but its performance is high compared to bubble sort.
##############################################################
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#define SIZE 20
#define MAXLENGTH  3        //MAXLENGTH means the number of numbers in a value
//eg. max value in data 9999 then  MAXLENGTH 4
void printArray(int data[]){
int i;
int j;
printf("\n\n");
for(i=0;i<SIZE;i++){
printf("%d \n",data[i]);
}
}
int main(int argc, char** argv) {
int data[SIZE];
int tmpArray[SIZE][10];
int tmpData[10]={0};
//Array initialization
srand(time(NULL));
int i;
for(i=0;i<SIZE;i++){
data[i]=rand()%((int)pow(10,MAXLENGTH));
printf("%d \n",data[i]);
}
//sorting
int power;
for(power=10;power<=(int)pow(10,MAXLENGTH);power*=10){
int j;
for(j=0;j<SIZE;j++){
int bal=data[j]%power;
bal=(int)(((10*bal)/power));
tmpArray[tmpData[bal]][bal]=data[j];
tmpData[bal]++;
}
int l;
for(j=0,l=0;j<10;j++){
int k;
for(k=0;k<tmpData[j];k++,l++){
data[l]=tmpArray[k][j];
}
tmpData[j]=0;
}
}
printArray(data);
return (EXIT_SUCCESS);
}

Eight Queens

Is it Possible to place eight queens on an empty chessboard so that no queen is "attacking" any other?
Here i Try to solve/ design a simple puzzle game.
you can enter position of the queen like 1,1 or 3,5 or 8,8
it will place the queen on the board if it is legal and a table will show with numbers to each square of the chessboard indicating how many squares of an empty chessboard are 'eleminated' once a queen is placed in that square.
The appropriate heuristic might be: Place the next queen in the square with the smallest elemination number.
######################################################################

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

void placeQueen(int board[][8][3],int position[]);
int  isLegal(int board[][8][3],int position[]);
void printBoard(int board[][8][3],int layer);
void calcBestPlace(int board[][8][3]);

int main(int argc, char** argv) {
int board[8][8][3]={};
//board
//first layer:  places of queen
//second layer: attacking positions
//thrid layer:  hint with minimum attacking positions
int x;
int y;
int i;
calcBestPlace(board);
printBoard(board,2);
for(i=0;i<8;i++){
scanf("%d,%d",&x,&y);
int a[]= {x-1,y-1};
if(isLegal(board,a)==1){
printf("is legal\n");
placeQueen(board,a);
calcBestPlace(board);
printBoard(board,0);
printBoard(board,2);
}else{
printf("Illegal Place for Queen\n");
printBoard(board,1);
i--;
}
}
return (EXIT_SUCCESS);
}
void placeQueen(int board[][8][3],int position[]){
board[position[0]][position[1]][0]=1;
int i;
int j;
int k;
//fill attacking positions
for(i=0;i<8;i++){
for(j=0;j<8;j++){
if(((position[0]-i)==(position[1]-j))||position[0]==i||position[1]==j||(position[0]-i)==(j-position[1])){
//printf("position=%d,%d and i=%d,j=%d\n",position[0],position[1],i,j);
board[i][j][1]=1;
}
}
}
}
int isLegal(int board[][8][3],int position[]){
if(board[position[0]][position[1]][1]==1){
return 0;
}else{
return 1;
}
}
void printBoard(int board[][8][3],int layer){
int i;
int j;
switch(layer){
case 0:
case 1:
for(j=7;j>=0;j--){
for(i=0;i<8;i++){
if(board[i][j][layer]==1){
printf("Q   ");
}else{
printf("+   ");
}
}
printf("\n\n");
}
break;
case 2:
for(j=7;j>=0;j--){
for(i=0;i<8;i++){
printf("%2d ",board[i][j][2]);
}
printf("\n");
}
}
}
void calcBestPlace(int board[][8][3]){
int i;
int j;
int x;
int y;
for(i=0;i<8;i++){
for(j=0;j<8;j++){
board[i][j][2]=0;
if(board[i][j][1]==1){
continue;
}else{
for(x=0;x<8;x++){
for(y=0;y<8;y++){
if(((x-i)==(y-j))||x==i||y==j||((x-i)==(j-y))){
if(board[x][y][1]!=1){
board[i][j][2]++;
}
}
}
}
}
}
}
}