depth first search

#include<iostream>
#include<stdio.h>
using namespace std;
void search(int,int);
int i,j,n,y,x;
int a[10][10],b[10],s[10];
struct queuenode
{
int info;
struct queuenode *next;
};
typedef struct queuenode *QUEUE;
QUEUE front,rear,q;
QUEUE getnode()
{
QUEUE p;
p=(QUEUE)malloc(sizeof(struct queuenode));
return p;
}
void insert(QUEUE q,int x);
int qdel(QUEUE q,int x);
void main()
{
int key;
front=rear=NULL;
printf("\nEnter the number of vertices:\n");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=0;i<n;i++)
           {
for(j=0;j<n;j++)
                {
cin>>a[i][j];
                }
cout<<"\n";
        }
cout<<"\nThe adjacency matrix is:\n";
for(i=0;i<n;i++)
           {
for(j=0;j<n;j++)
                      {
cout<<a[i][j]<<"\t";
                      }
cout<<"\n";
           }
for(i=0;i<n;i++)
            {
b[i] = 0;
s[i]=0;
             }
cout<<"\nEnter the key to be found::";
cin>>key;
cout<<"\nDFS Path is:\t";
search(0,key);
cout<<"\n";
system("pause");
}

void search(int k,int key)
{
if((b[k]==0)&&(s[k]==0))
  {
  if(k==key)
{
cout<<k<<"\t";
  cout<<"\nElement found\n";
  return;
  }
  else
  cout<<k<<"\t";

b[k]=1;
s[k]=1;

for(i=0;i<n;i++)
        {
if(a[k][i]==1)
            {
if(b[i]==0)
                        {
insert(q,i);
                     }
           }
        }
      }
if(front==NULL)
{
cout<<"\nElement not found!!\n";
return;
}
else
{
x=qdel(q,k);
search(x,key);
}
}
void insert(QUEUE q,int x)
{
QUEUE p;
p=getnode();
p->info=x;
if(front==NULL)
front = p;
else
rear->next=p;
rear=p;
}

int qdel(QUEUE q,int z)
{
q=front;
y=q->info;
if(front==rear)
            front=rear=NULL;
else
front=front->next;
free(q);
if(a[z][y]==1)
return(y);
else
             {
q=getnode();
q->info =y;
if(front == NULL)
front =q;
else
            rear->next=q;
rear=q;
for(i=z+1;i<n;i++)
{
if((a[z][i]==1)&&(s[i]==0))
{
return z;
}
}
for(i=0;i<n;i++)
{
if((a[z][i]==1)&&(b[i]==1))
return i;
}
return z;
        }
}

breadth first search

#include<iostream>
#include<stdio.h>
using namespace std;
void search(int,int);
int i,j,n,y,x;
int a[10][10],b[10];
struct queuenode
{
int info;
struct queuenode *next;
};
typedef struct queuenode *QUEUE;
QUEUE front,rear,q;
QUEUE getnode()
{
QUEUE p;
p=(QUEUE)malloc(sizeof(struct queuenode));
return p;
}
void insert(QUEUE q,int x);
int qdel(QUEUE q,int x);
void main()
{
int key;
front=rear=NULL;
printf("\nEnter the number of vertices:\n");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=0;i<n;i++)
           {
for(j=0;j<n;j++)
                      {
cin>>a[i][j];
              }
    cout<<"\n";
        }
cout<<"\nThe adjacency matrix is:\n";
for(i=0;i<n;i++)
           {
for(j=0;j<n;j++)
                      {
cout<<a[i][j]<<"\t";
                        }
cout<<"\n";
        }
for(i=0;i<n;i++)
           {
b[i] = 0;
           }
cout<<"\nEnter the key to be found::\n";
cin>>key;
cout<<"\n\nBFS Path is:\t";
search(0,key);
           cout<<"\n";
system("pause");
}

void search(int k, int key)
{
if(b[k]==0)
{
if(k==key)
{
cout<<k<<"\t";
cout<<"\nElement found!\n";
return;
}
else
{
cout<<k<<"\t";
           }
b[k]=1;
for(i=0;i<n;i++)
                       {
if(a[k][i]==1)
                                 {
if(b[i]==0)
                      {
insert(q,i);
                                             }
}
        }
   }
if(front==NULL)
{
cout<<"\nElement not present!";
return;
}
else
{
x=qdel(q,k);
      search(x,key);
}
}
void insert(QUEUE q,int x)
{
QUEUE p;
p=getnode();
p->info=x;
if(front==NULL)
front = p;
else
rear->next=p;
rear=p;
}
int qdel(QUEUE q,int z)
{
q=front;
y=q->info;
if(front==rear)
front=rear=NULL;
else
front=front->next;
free(q);
return y;

}

tower of hanoi using c++

#include<iostream>
usingnamespacestd;
#include<conio.h>
void move(int n,char *s,char *i,char *d)
// s stands for source tower
// d stands for destination tower
// i stands for intermediate tower
{
if(n>0)
{
  move(n-1,s,d,i);
// move n-1 disks from source to intermediate tower
cout<<" disk "<<n<<" is moved from "<<s<<" to "<<d<<endl;
// move the disk from to source to destination
move(n-1,i,s,d);
// move n-1 disks from intermediate to destination
  }
}

void main()
{

cout<<"Enter the no. of disks:";
int n;
cin>>n;
move(n,"sourcetower","intermediatetower","destination tower");
getch();
}

OUTPUT:
Enter the no. of disks :3
 disk 1 is moved from sourcetower to destination tower
 disk 2 is moved from sourcetower to intermediatetower
 disk 1 is moved from destination tower to intermediatetower
 disk 3 is moved from sourcetower to destination tower
 disk 1 is moved from intermediatetower to sourcetower
 disk 2 is moved from intermediatetower to destination tower
 disk 1 is moved from sourcetower to destination tower

tic tac toe

#include <iostream>
#include <string>

using namespace std;

enum players {X = 1, O = 2};                  //Values for each player    
const short strategy[] = {2,1,2,1,3,1,2,1,2};     //Constant array used for comp to decide the move to make

class TicTacToe{
short state[9];                                 //State is the current table position as moves are made
public:
TicTacToe()
{
for(int i = 0; i < 9; i++)               //Initialising blank state
state[i] = 0;
}

/**
* X = 1
* O = 2
*/
bool move(int player, int pos)               //Function to make a move
{
if(pos < 0 || pos > 8 || state[pos] != 0)    //Checking if the correct positions were entered
return false;

state[pos] = player;                         //Setting the state as per the move made and at which position
return true;
}

short possibleWin()
{
//Check possible win for each player
for (int p = 1; p < 3; ++p)          //p=1 is player 1 and p=2 is player 2
{
for(int i = 0; i < 9; i += 3)
{

//Check for win horizontally...and return the empty state which will make you win.
if(state[0+i] == p && state[1+i] == p && state[2+i] == 0)
return 2+i;
else if(state[1+i] == p && state[2+i] == p && state[0+i] == 0)
return 0+i;
else if(state[0+i] == p && state[2+i] == p && state[1+i] == 0)
return 1+i;

//Check for win vertically...and return the empty state which will make you win.
if(state[0+i/3] == p && state[3+i/3] == p && state[6+i/3] == 0)
return 6+i/3;
else if(state[0+i/3] == p && state[6+i/3] == p && state[3+i/3] == 0)
return 3+i/3;
else if(state[3+i/3] == p && state[6+i/3] == p && state[0+i/3] == 0)
return 0+i/3;
}

//Check for win diagonally....and return the empty state which will make you win.
if(state[0] == p && state[4] == p && state[8] == 0)
return 8;
else if(state[4] == p && state[8] == p && state[0] == 0)
return 0;
else if(state[2] == p && state[4] == p && state[6] == 0)
return 6;
else if(state[4] == p && state[6] == p && state[2] == 0)
return 2;
else if(((state[0] == p && state[8]) || (state[2] == p && state[6] == p)) && state[4] == 0)
return 4;
}

//Win not possible
return -1;
}

/**
* 1 = X wins
* 2 = O wins
* 3 = Nobody wins
* 0 = Game in progress
*/
short gameOver()
{
//For each player check if the horizontal or vertical lines have got a win situation
for (int p = 1; p < 3; ++p)
{
for(int i = 0; i < 9; i+=3){            
if(state[0+i] == p && state[1+i] == p && state[2+i] == p)
return p;
else if(state[0+i/3] == p && state[3+i/3] == p && state[6+i/3] == p)
return p;
}

if((state[0] == p && state[4] == p && state[8] == p) || (state[2] == p && state[4] == p && state[6] == p))
return p;
}

for (int i = 0; i < 9; ++i)
{
if(state[i] == 0)
return 0;
}

return 3;
}

void showBoard()      //Displaying the board
{
for (int i = 0; i < 9; ++i)
{
if(state[i] == 0)
cout<<i;
else if(state[i] == 1)
cout<<" X ";
else if(state[i] == 2)
cout<<" O ";

if((i+1)%3 == 0)
cout<<endl;
}
cout<<endl;
}

short getNextMove()
{
short highestPossibleMove = 0;
short highestPossiblePos = -1;
short possible;

if(gameOver())
return -1;
else{

if((possible = possibleWin()) != -1)     //If you get a value for a possible win which was return that as the next move
{
return possible;
}

for (int i = 0; i < 9; ++i){
if(state[i] == 0 && strategy[i] > highestPossibleMove)   //Check for The best move in an empty position
{
highestPossibleMove = strategy[i];
highestPossiblePos = i;
}
}

return highestPossiblePos;
}
}


};

int main(int argc, char** args)
{
TicTacToe lol;
int pos;
bool flag = false;
string name;

cout<<"Enter your name"<<endl;
cin>>name;

while(lol.gameOver() == 0)
{
while(!flag)
{
cout<<"Enter move: ";
cin>>pos;
flag = lol.move(X, pos-1);   //Players turn
if(!flag)
cout<<"Invalid move\n";
}
lol.showBoard();
lol.move(O, lol.getNextMove());   //Comp decides which move next
lol.showBoard();
flag = false;
}

if(lol.gameOver() == 1)
cout<<name<<" wins!\n";
else if(lol.gameOver() == 2)
cout<<name<<" loses\n";
else
cout<<"Nobody wins\n";

system("pause");

return 0;
}