Tower of Hanoi

(Source: http://en.wikipedia.org/wiki/Tower_of_Hanoi)

The Tower of Hanoi (also called the Tower of Brahma or Lucas' Tower,^[1] and sometimes pluralised) is a mathematical game orpuzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following rules:

• Only one disk may be moved at a time.
• Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
• No disk may be placed on top of a smaller disk.

With three disks, the puzzle can be solved in seven moves

namespace TowerOfHanoi
{
    class Disk: IComparable<Disk>
    {
        public int Size { get; private set; }

        public Disk(int size)
        {
            this.Size = size;
        }

        public int CompareTo(Disk other)
        {
            return this.Size - other.Size;
        }
    }
}

namespace TowerOfHanoi
{
    class Tower
    {
        private Disk[] Peck;
        private int Pointer= -1;
        public int Height { get; private set; }
        public string name { get; private set; }

        public Tower(int Height, string name)
        {
            Peck = new Disk[Height];
            this.Height = Height;
            this.name = name;

        }

        public void Push(Disk d)
        {
            if (!this.isEmpty())
            {
                if (Peck[Pointer].CompareTo(d) > 0)
                {
                    Peck[++Pointer] = d;
                }
                else
                {
                    throw new NotSupportedException("Can't put large disk on small disk");
                }
            }
            else
            {
                Peck[++Pointer] = d;
            }
        }

        public Disk Pop()
        {
            if (!isEmpty())
            {
                return Peck[Pointer--];
            }
            else
            {
                throw new NotSupportedException("Peck is empty");
            }
        }

        public bool isEmpty()
        {
            return Pointer == -1 ? true : false;
        }

        public override string ToString()
        {
            string final = name + "\n";
            for (int i = Pointer; i >= 0; i--)
            {
                string s = "";
                int space = (Peck.Length- Peck[i].Size);

                for (int x = 0; x < space; x++)
                {
                    s += "  ";
                }

                for (int x = 1; x <= Peck[i].Size; x++)
                {
                    s+="____";
                }

                final += s;
                final += "\n";
            }

            return final;
        }
    }
}

namespace TowerOfHanoi
{
    class TowerOfHanoiSolver
    {
        public void Solve(Tower from, Tower to)
        {
            Tower temp = new Tower(from.Height, "TEMP");
            this.Solve(from, to, temp, from.Height);
        }

        private void Solve(Tower from, Tower to, Tower temp, int height)
        {
            if (height == 1)
            {
                to.Push(from.Pop());
            }
            else
            {
                Solve(from, temp, to, height - 1);
                to.Push(from.Pop());
                Solve(temp, to, from, height - 1);
            }
        }
    }
}

namespace TowerOfHanoi
{
    class Program
    {
        static void Main(string[] args)
        {
            Tower from = new Tower(4, "FROM");
            Tower to = new Tower(4 , "TO");


            TowerOfHanoiSolver solver = new TowerOfHanoiSolver();

            from.Push(new Disk(4));
            from.Push(new Disk(3));
            from.Push(new Disk(2));
            from.Push(new Disk(1));

            Console.WriteLine(from.ToString());
            Console.WriteLine("SOLVING..");
            solver.Solve(from, to);
            Console.WriteLine(to.ToString());
            Console.ReadLine();
        }
    }
}

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

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]++;
}
}
}
}
}
}
}
}

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