Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
40 kB
1
Indexable
Never
Practical 2::::::

#include<bits/stdc++.h>
using namespace std;

int current_matrix[3][3],upward_matrix[3][3],downward_matrix[3][3],right_matrix[3][3],left_matrix[3][3];
int goal_matrix[3][3]={1,2,3,4,5,6,7,8,999};
int a,b;
int h_up=0,h_down=0,h_right=0,h_left=0,main_h=0;

void choose_mat(int h_left,int h_right,int h_down,int h_up,int max_heuristic_value);

void print(int mat[3][3])
{
    for(a=0;a<=2;a++)
    {
        for(b=0;b<=2;b++)
        {

            printf("%d\t",mat[a][b]);
        }
        printf("\n");
    }
    cout<<"\n";
}


int calculate_heuristic (int mat[3][3])
{
    int h_value=0;
    for(a=0;a<=2;a++)
    {
       for(b=0;b<=2;b++)
        {
            if(goal_matrix[a][b]==mat[a][b])
            {
                h_value++;
            }
        }
     }
    return h_value;
}

void replace_mat(int mat[3][3])
{
    for(a=0;a<=2;a++)
    {
       for(b=0;b<=2;b++)
        {
            current_matrix[a][b]=mat[a][b];
        }
    }
}

int find_up(int mat[3][3])
{
    int u,temp1;
    for(a=0;a<=2;a++)
    {
        for(b=0;b<=2;b++)
        {
            if(mat[a][b]==999)
            {
                temp1=mat[a-1][b];
                upward_matrix[a-1][b]=mat[a][b];
                upward_matrix[a][b]=temp1;
            }
            else
            {
                upward_matrix[a][b]=mat[a][b];
            }
        }
    }
    u=calculate_heuristic(upward_matrix);
    return u;
}
int find_down(int mat[3][3])
{


    int d,temp2;
    for(a=0;a<=2;a++)
    {
        for(b=0;b<=2;b++)
        {
            downward_matrix[a][b]=mat[a][b];
        }
    }
    for(a=0;a<=2;a++)
    {
        for(b=0;b<=2;b++)
        {

            if(mat[a][b]==999)
            {
                downward_matrix[a+1][b]=999;
                temp2=mat[a+1][b];

                downward_matrix[a][b]=temp2;

            }
        }
    }
    d=calculate_heuristic(downward_matrix);
    return d;
}
int find_right(int mat[3][3])
{
    for(a=0;a<=2;a++)
    {
        for(b=0;b<=2;b++)
        {
            right_matrix[a][b]=mat[a][b];
        }
    }
    int r,temp3,i,j;
    for(i=0;i<=2;i++)
    {
      for(j=0;j<=2;j++)
        {
            if(mat[i][j]==999)
            {
                temp3=mat[i][j+1];
                right_matrix[i][j+1]=mat[i][j];
                right_matrix[i][j]=temp3;
            }
        }
    }
    r=calculate_heuristic(right_matrix);
    return r;
}
int find_left(int mat[3][3])
{
    int l,temp4;
    for(a=0;a<=2;a++)
    {
        for(b=0;b<=2;b++)
        {
            left_matrix[a][b]=mat[a][b];
        }
    }
    for(a=0;a<=2;a++)
    {
        for(b=0;b<=2;b++)
        {
            if(mat[a][b]==999)
            {
                temp4=mat[a][b-1];
                left_matrix[a][b-1]=mat[a][b];
                left_matrix[a][b]=temp4;
            }
        }
    }
    l=calculate_heuristic(left_matrix);
    return l;
}

int find_max(int a,int b,int c,int d)
{
    int largest;
    largest= (a>b)?(a>c)?(a>d)?a:d:(c>d)?c:d:(b>c)?(b>d)?b:d:(c>d)?c:d;
    return largest;
}



void find_final_state(int mat[3][3])
{
    int max_heuristic_value;
    for(a=0;a<=2;a++)
    {
        for(b=0;b<=2;b++)
        {
            if(current_matrix[a][b]==999 && a==0 && b==0)
            {
    h_down=find_down(current_matrix);
    h_right=find_right(current_matrix);
    max_heuristic_value=find_max(h_left,h_right,h_down,h_up);
    cout<<"Possible states"<<endl;
    cout<<"downward h="<<h_up<<endl;
    print(downward_matrix);
    cout<<"right h="<<h_right<<endl;
    print(right_matrix);
    choose_mat(h_left,h_right,h_down,h_up,max_heuristic_value);
    break;
            }
            else if(current_matrix[a][b]==999 && a==0 && b==0)
            {
               h_down=find_down(current_matrix);
    h_right=find_right(current_matrix);
    max_heuristic_value=find_max(h_left,h_right,h_down,h_up);
    cout<<"Possible states"<<endl;
    cout<<"downward h="<<h_up<<endl;
    print(downward_matrix);
    cout<<"right h="<<h_right<<endl;
    print(right_matrix);
    cout<<"left h="<<h_left<<endl;
    print(left_matrix);
    choose_mat(h_left,h_right,h_down,h_up,max_heuristic_value);
    break;
            }


else if(current_matrix[a][b]==999 &&a==0 && b==2)
{
    h_down=find_down(current_matrix);
    h_left=find_left(current_matrix);
    max_heuristic_value=find_max(h_left,h_right,h_down,h_up);
    cout<<"Possible states"<<endl;
    cout<<"downward h="<<h_down<<endl;
    print(downward_matrix);
    cout<<"left h="<<h_left<<endl;
    print(left_matrix);
    choose_mat(h_left,h_right,h_down,h_up,max_heuristic_value);
    break;
}

else if(current_matrix[a][b]==999 &&a==1 && b==0)
{
    h_up=find_up(current_matrix);
    h_down=find_down(current_matrix);
    h_right=find_right(current_matrix);
    max_heuristic_value=find_max(h_left,h_right,h_down,h_up);
    cout<<"Possible states"<<endl;
    cout<<"upward h="<<h_up<<endl;
    print(upward_matrix);
      cout<<"downward h="<<h_down<<endl;
    print(downward_matrix);
    cout<<"right h="<<h_right<<endl;
    print(right_matrix);
    choose_mat(h_left,h_right,h_down,h_up,max_heuristic_value);
    break;
}

else if(current_matrix[a][b]==999 &&a==1 && b==1)
{
    h_up=find_up(current_matrix);
    h_down=find_down(current_matrix);
    h_right=find_right(current_matrix);
    h_left=find_left(current_matrix);
    max_heuristic_value=find_max(h_left,h_right,h_down,h_up);
    cout<<"Possible states"<<endl;
    cout<<"upward h="<<h_up<<endl;
    print(upward_matrix);
      cout<<"downward h="<<h_down<<endl;
    print(downward_matrix);
    cout<<"right h="<<h_right<<endl;
    print(right_matrix);
    cout<<"left h="<<h_left<<endl;
    print(left_matrix);
    choose_mat(h_left,h_right,h_down,h_up,max_heuristic_value);
    break;
}

else if(current_matrix[a][b]==999 &&a==1 && b==2)
{
    h_up=find_up(current_matrix);
    h_down=find_down(current_matrix);
    h_left=find_left(current_matrix);
    max_heuristic_value=find_max(h_left,h_right,h_down,h_up);
    cout<<"Possible states"<<endl;
    cout<<"upward h="<<h_up<<endl;
    print(upward_matrix);
      cout<<"downward h="<<h_down<<endl;
    print(downward_matrix);
    cout<<"left h="<<h_left<<endl;
    print(left_matrix);
    choose_mat(h_left,h_right,h_down,h_up,max_heuristic_value);
    break;
}

else if(current_matrix[a][b]==999 &&a==2 && b==0)
{
    h_up=find_up(current_matrix);
    h_right=find_right(current_matrix);
    max_heuristic_value=find_max(h_left,h_right,h_down,h_up);
    cout<<"Possible states"<<endl;
    cout<<"upward h="<<h_up<<endl;
    print(upward_matrix);
    cout<<"right h="<<h_right<<endl;
    print(right_matrix);
    choose_mat(h_left,h_right,h_down,h_up,max_heuristic_value);
    break;
}

else if(current_matrix[a][b]==999 &&a==2 && b==1)
{
    h_up=find_up(current_matrix);
    h_right=find_right(current_matrix);
    h_left=find_left(current_matrix);
    max_heuristic_value=find_max(h_left,h_right,h_down,h_up);
    cout<<"Possible states"<<endl;
    cout<<"upward h="<<h_up<<endl;
    print(upward_matrix);
    cout<<"right h="<<h_right<<endl;
    print(right_matrix);
    cout<<"left h="<<h_left<<endl;
    print(left_matrix);
    choose_mat(h_left,h_right,h_down,h_up,max_heuristic_value);
    break;
}
else if(current_matrix[a][b]==999 &&a==2&& b==2)
{
    h_up=find_up(current_matrix);
    h_left=find_left(current_matrix);
    max_heuristic_value=find_max(h_left,h_right,h_down,h_up);
    cout<<"possible states"<<endl;
    cout<<"upward h="<<h_up<<endl;
    print(upward_matrix);
    cout<<"left h="<<h_left<<endl;

    print(left_matrix);
    choose_mat(h_left,h_right,h_down,h_up,max_heuristic_value);
    break;
}
}
}
}
void func(int mat[3][3],int m)
{
    replace_mat(mat);
    print(current_matrix);
    main_h=m;
    if(main_h==9)
    {
        return;
    }
    else{
        find_final_state(current_matrix);
    }
}
void choose_mat(int h_left, int h_right,int h_down,int h_up,int max_heuristic_value)
{

    cout<<"selected matrix is with heuristic value="<<max_heuristic_value<<endl;
    if(max_heuristic_value==h_right)
    {
        func(right_matrix,max_heuristic_value);
    }
    if(max_heuristic_value==h_down)
    {
        func(downward_matrix,max_heuristic_value);
    }
     if(max_heuristic_value==h_up)
     {
         func(upward_matrix,max_heuristic_value);
     }
     if(max_heuristic_value==h_left)
        {
            func(left_matrix,max_heuristic_value);
        }
}
int main()
{
    int h;
    int initial_matrix[3][3]={1,2,3,999,4,6,7,5,8};
    cout<<"initial Matrix:"<<endl;
    print(initial_matrix);
    cout<<(goal_matrix);
    for(a=0;a<=2;a++)
    {
        for(b=0;b<=2;b++)
        {
            current_matrix[a][b]=initial_matrix[a][b];
        }
    }
    cout<<"current_matrix"<<endl;
    print(current_matrix);
    h=calculate_heuristic(current_matrix);
    cout<<"h="<<h<<endl;
    find_final_state(current_matrix);


}


Practical 3::::::

#include <cstdio>
#include <stack>
#include <map>
#include <algorithm>
using namespace std;

// Representation of a state (x, y)
// x and y are the amounts of water in litres in the two jugs respectively
struct state {
    int x, y;

    // Used by map to efficiently implement lookup of seen states
    bool operator < (const state& that) const {
        if (x != that.x) return x < that.x;
        return y < that.y;
    }
};

// Capacities of the two jugs respectively and the target amount
int capacity_x, capacity_y, target;

void dfs(state start, stack <pair <state, int> >& path)   {
    stack <state> s;
    state goal = (state) {-1, -1};

    // Stores seen states so that they are not revisited and
    // maintains their parent states for finding a path through
    // the state space
    // Mapping from a state to its parent state and rule no. that
    // led to this state
    map <state, pair <state, int> > parentOf;

    s.push(start);
    parentOf[start] = make_pair(start, 0);

    while (!s.empty())    {
        // Get the state at the front of the stack
        state top = s.top();
        s.pop();

        // If the target state has been found, break
        if (top.x == target || top.y == target) {
            goal = top;
            break;
        }

        // Find the successors of this state
        // This step uses production rules to produce successors of the current state
        // while pruning away branches which have been seen before

        // Rule 1: (x, y) -> (capacity_x, y) if x < capacity_x
        // Fill the first jug
        if (top.x < capacity_x)  {
            state child = (state) {capacity_x, top.y};
            // Consider this state for visiting only if it has not been visited before
            if (parentOf.find(child) == parentOf.end()) {
                s.push(child);
                parentOf[child] = make_pair(top, 1);
            }
        }

        // Rule 2: (x, y) -> (x, capacity_y) if y < capacity_y
        // Fill the second jug
        if (top.y < capacity_y)  {
            state child = (state) {top.x, capacity_y};
            if (parentOf.find(child) == parentOf.end()) {
                s.push(child);
                parentOf[child] = make_pair(top, 2);
            }
        }

        // Rule 3: (x, y) -> (0, y) if x > 0
        // Empty the first jug
        if (top.x > 0)  {
            state child = (state) {0, top.y};
            if (parentOf.find(child) == parentOf.end()) {
                s.push(child);
                parentOf[child] = make_pair(top, 3);
            }
        }

        // Rule 4: (x, y) -> (x, 0) if y > 0
        // Empty the second jug
        if (top.y > 0)  {
            state child = (state) {top.x, 0};
            if (parentOf.find(child) == parentOf.end()) {
                s.push(child);
                parentOf[child] = make_pair(top, 4);
            }
        }

        // Rule 5: (x, y) -> (min(x + y, capacity_x), max(0, x + y - capacity_x)) if y > 0
        // Pour water from the second jug into the first jug until the first jug is full
        // or the second jug is empty
        if (top.y > 0)  {
            state child = (state) {min(top.x + top.y, capacity_x), max(0, top.x + top.y - capacity_x)};
            if (parentOf.find(child) == parentOf.end()) {
                s.push(child);
                parentOf[child] = make_pair(top, 5);
            }
        }

        // Rule 6: (x, y) -> (max(0, x + y - capacity_y), min(x + y, capacity_y)) if x > 0
        // Pour water from the first jug into the second jug until the second jug is full
        // or the first jug is empty
        if (top.x > 0)  {
            state child = (state) {max(0, top.x + top.y - capacity_y), min(top.x + top.y, capacity_y)};
            if (parentOf.find(child) == parentOf.end()) {
                s.push(child);
                parentOf[child] = make_pair(top, 6);
            }
        }
    }

    // Target state was not found
    if (goal.x == -1 || goal.y == -1)
        return;

    // backtrack to generate the path through the state space
    path.push(make_pair(goal, 0));
    // remember parentOf[start] = (start, 0)
    while (parentOf[path.top().first].second != 0)
        path.push(parentOf[path.top().first]);
}

int main()  {
    stack <pair <state, int> > path;

    printf("Enter the capacities of the two jugs : ");
    scanf("%d %d", &capacity_x, &capacity_y);
    printf("Enter the target amount : ");
    scanf("%d", &target);

    dfs((state) {0, 0}, path);
    if (path.empty())
        printf("\nTarget cannot be reached.\n");
    else    {
        printf("\nNumber of moves to reach the target : %d\nOne path to the target is as follows :\n", path.size() - 1);
        while (!path.empty())   {
            state top = path.top().first;
            int rule = path.top().second;
            path.pop();

            switch (rule)   {
                case 0: printf("State : (%d, %d)\n#\n", top.x, top.y);
                        break;
                case 1: printf("State : (%d, %d)\nAction : Fill the first jug\n", top.x, top.y);
                        break;
                case 2: printf("State : (%d, %d)\nAction : Fill the second jug\n", top.x, top.y);
                        break;
                case 3: printf("State : (%d, %d)\nAction : Empty the first jug\n", top.x, top.y);
                        break;
                case 4: printf("State : (%d, %d)\nAction : Empty the second jug\n", top.x, top.y);
                        break;
                case 5: printf("State : (%d, %d)\nAction : Pour from second jug into first jug\n", top.x, top.y);
                        break;
                case 6: printf("State : (%d, %d)\nAction : Pour from first jug into second jug\n", top.x, top.y);
                        break;
            }
        }
    }

    return 0;
}


Practical 4:::::::

// Solving 8-Puzzle Using Steepest Ascent Hill Climbing Algorithm
#include <bits/stdc++.h>

using namespace std;

const char UP ='1';
const char DOWN= '2';
const char LEFT= '3';
const char RIGHT= '4';


void printArray(int** array)
{
    for(int a=0;a<3;a++)
    {
        for(int b=0;b<3;b++)
        {
              cout<< setw(8) << array[a][b];
        }
        cout<<endl;
    }
    cout<<endl;
}

// Calculate Manhattan distance
int manhattan_distance(int** start_state,int** goal_state)
{
    int manhattan_distance=0;
    for(int i=0;i<3;i++)
        {
            for(int j=0;j<3;j++)
            {
                if(start_state[i][j] > 0)
                {
                    for(int k=0;k<3;k++)
                    {
                        for(int l=0;l<3;l++)
                        {
                            if (goal_state[k][l] == start_state[i][j])
                            {
                                manhattan_distance=manhattan_distance + (abs(i-k)+abs(j-l));

                            }
                        }
                    }
                }
            }
        }
return manhattan_distance;

}

void makeMove(int** temp,int move)
{
    int flag=0;
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            if(temp[i][j] == 0)
            {


                if(move==1)
                {
                    temp[i][j] = temp[i-1][j];
                    temp[i-1][j] = 0;
                    flag=1;
                    break;
                }
                else if(move==2)
                {
                    temp[i][j] = temp[i+1][j];
                    temp[i+1][j] = 0;
                    flag=1;
                    break;
                }
                else if(move==3)

                {
                    temp[i][j] = temp[i][j-1];
                    temp[i][j-1] = 0;
                    flag=1;
                    break;
                }
                else
                {
                    temp[i][j] = temp[i][j+1];
                    temp[i][j+1] = 0;
                    flag=1;
                    break;
                }
            }
        }
        if(flag==1){break;}
    }
}

//-----------------------------------------------------------------------------------------------------------
int tile_Ordering(int** current_state,int** goal_state,int move)
{
    int** temp = new int*[3]; // allocate an array of 3 int pointers - these represents rows
    for(int i=0;i<3;i++)
    {
        temp[i]=new int[3]; // these represents columns
        for(int j=0;j<3;j++)
        {
            temp[i][j] = current_state[i][j];
        }
    }
    makeMove(temp,move);
    printArray(temp);
    int manhattan=manhattan_distance(temp,goal_state);
    cout<<"Current Manhattan number :"<<manhattan<<endl<<endl<<endl;
    for(int i=0;i<3;i++)
    {
        delete temp[i];
    }
    delete temp;
    return manhattan;
}

//----------------------------------------------------------------------------------------------------------
void steepestAscentHillClimbing( int** start_state, int** goal_state,int former_move)
{
    int arr[4] = {100,100,100,100};
    cout<<"--------------------------------------------------------------------------------"<<endl;
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            if (start_state[i][j] == 0)
            {
                if(i>0 && former_move!=2)
                {
                    cout<<"Checking child (moving 0 up) "<<endl;
                    arr[0]=tile_Ordering(start_state,goal_state,1);
                }
                if(i<2 && former_move!=1)
                {
                    cout<<"Checking child (moving 0 down) "<<endl;
                    arr[1]=tile_Ordering(start_state,goal_state,2);
                }
                if(j>0 && former_move!=4)
                {
                    cout<<"Checking child (moving 0 left) "<<endl;
                    arr[2]=tile_Ordering(start_state,goal_state,3);
                }
                if(j<2 && former_move!=3)
                {
                    cout<<"Checking child (moving 0 right) "<<endl;
                    arr[3]=tile_Ordering(start_state,goal_state,4);
                }
            }
        }
        cout<<endl;
    }
    int localOptimum=99;
    int index=0;
    for(int i=0;i<4;i++)
    {
        if(arr[i]<localOptimum)
        {
            localOptimum=arr[i];
            index=i+1;
        }
    }
    makeMove(start_state,index);
    cout<<"Next state = minimum Manhattan number :"<<endl;
    printArray(start_state);
    if(localOptimum==0)
    {
        cout<<"goal state reached"<<endl;

        return;
    }
    else
    steepestAscentHillClimbing(start_state,goal_state,index);
}

int main()
{
    int** initial = new int*[3]; // allocate an array of 3 int pointers - these represents rows
    for(int i=0;i<3;i++)
    {
        initial[i]=new int[3]; // these represents columns
    }

    int** final = new int*[3]; // allocate an array of 3 int pointers - these represents rows
    for(int i=0;i<3;i++)
    {
        final[i]=new int[3]; // these represents columns
    }

    int player_Input;
    cout << "Enter initial board configuration - 0 denotes empty position" << endl;
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            cout<<"Enter input A["<<i<<"]["<<j<<"]"<<endl;
            cin>>player_Input;
            initial[i][j]=player_Input;
        }
    }

    cout<<"--------------------------------------------------------------------------------"<<endl;
    cout << "Enter final board configuration - 0 denotes empty position" << endl;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
        {
            cout<<"Enter input A["<<i<<"]["<<j<<"]"<<endl;
            cin>>player_Input;
            final[i][j]=player_Input;
        }

    cout<<"\n---------------------------Your initial matrix is-------------------------------\n"<<endl;


    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            cout << setw(8) << initial[i][j];
        }
        cout<<endl;
    }

    cout<<"\n---------------------------Your final matrix is--------------------------------\n"<<endl;


    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            cout << setw(8) << final[i][j];
        }
        cout<<endl;
    }

    cout<<"\n--------------------------------------------------------------------------------"<<endl;
    cout<<"\n--------------------------------------------------------------------------------"<<endl;
    cout<<"\nCalling Steepest Ascent Hill Climbing function\n"<<endl;
   steepestAscentHillClimbing(initial,final,0);
    for(int i=0;i<3;i++)
    {
        delete initial[i];
        delete final[i];
    }
    delete initial;
    delete final;
    return 0;
}




Practical 5:::::::

#include<bits/stdc++.h>
using namespace std;

struct Move
{
    int row, col;
};

char player = 'x', opponent = 'o';

// This function returns true if there are moves
// remaining on the board. It returns false if
// there are no moves left to play.
bool isMovesLeft(char board[3][3])
{
    for (int i = 0; i<3; i++)
        for (int j = 0; j<3; j++)
            if (board[i][j]=='_')
                return true;
    return false;
}

// This is the evaluation function as discussed
// in the previous article ( http://goo.gl/sJgv68 )
int evaluate(char b[3][3])
{
    // Checking for Rows for X or O victory.
    for (int row = 0; row<3; row++)
    {
        if (b[row][0]==b[row][1] &&
            b[row][1]==b[row][2])
        {
            if (b[row][0]==player)
                return +10;
            else if (b[row][0]==opponent)
                return -10;
        }
    }

    // Checking for Columns for X or O victory.
    for (int col = 0; col<3; col++)
    {
        if (b[0][col]==b[1][col] &&
            b[1][col]==b[2][col])
        {
            if (b[0][col]==player)
                return +10;

            else if (b[0][col]==opponent)
                return -10;
        }
    }

    // Checking for Diagonals for X or O victory.
    if (b[0][0]==b[1][1] && b[1][1]==b[2][2])
    {
        if (b[0][0]==player)
            return +10;
        else if (b[0][0]==opponent)
            return -10;
    }

    if (b[0][2]==b[1][1] && b[1][1]==b[2][0])
    {
        if (b[0][2]==player)
            return +10;
        else if (b[0][2]==opponent)
            return -10;
    }

    // Else if none of them have won then return 0
    return 0;
}

// This is the minimax function. It considers all
// the possible ways the game can go and returns
// the value of the board
int minimax(char board[3][3], int depth, bool isMax)
{
    int score = evaluate(board);

    // If Maximizer has won the game return his/her
    // evaluated score
    if (score == 10)
        return score;

    // If Minimizer has won the game return his/her
    // evaluated score
    if (score == -10)
        return score;

    // If there are no more moves and no winner then
    // it is a tie
    if (isMovesLeft(board)==false)
        return 0;

    // If this maximizer's move
    if (isMax)
    {
        int best = -1000;

        // Traverse all cells
        for (int i = 0; i<3; i++)
        {
            for (int j = 0; j<3; j++)
            {
                // Check if cell is empty
                if (board[i][j]=='_')
                {
                    // Make the move
                    board[i][j] = player;

                    // Call minimax recursively and choose
                    // the maximum value
                    best = max( best,
                        minimax(board, depth+1, !isMax) );

                    // Undo the move
                    board[i][j] = '_';
                }
            }
        }
        return best;
    }

    // If this minimizer's move
    else
    {
        int best = 1000;

        // Traverse all cells
        for (int i = 0; i<3; i++)
        {
            for (int j = 0; j<3; j++)
            {
                // Check if cell is empty
                if (board[i][j]=='_')
                {
                    // Make the move
                    board[i][j] = opponent;

                    // Call minimax recursively and choose
                    // the minimum value
                    best = min(best,
                        minimax(board, depth+1, !isMax));

                    // Undo the move
                    board[i][j] = '_';
                }
            }
        }
        return best;
    }
}

// This will return the best possible move for the player
Move findBestMove(char board[3][3])
{
    int bestVal = -1000;
    Move bestMove;
    bestMove.row = -1;
    bestMove.col = -1;

    // Traverse all cells, evaluate minimax function for
    // all empty cells. And return the cell with optimal
    // value.
    for (int i = 0; i<3; i++)
    {
        for (int j = 0; j<3; j++)
        {
            // Check if cell is empty
            if (board[i][j]=='_')
            {
                // Make the move
                board[i][j] = player;

                // compute evaluation function for this
                // move.
                int moveVal = minimax(board, 0, false);

                // Undo the move
                board[i][j] = '_';

                // If the value of the current move is
                // more than the best value, then update
                // best/
                if (moveVal > bestVal)
                {
                    bestMove.row = i;
                    bestMove.col = j;
                    bestVal = moveVal;
                }
            }
        }
    }

    printf("The value of the best Move is : %d\n\n",
            bestVal);

    return bestMove;
}

// Driver code
int main()
{
    char board[3][3] =
    {
        { 'x', 'o', 'x' },
        { 'o', 'o', 'x' },
        { '_', '_', '_' }
    };

    Move bestMove = findBestMove(board);

    printf("The Optimal Move is :\n");
    printf("ROW: %d COL: %d\n\n", bestMove.row,
                                bestMove.col );
    return 0;
}


Practical 7:::::::

#include <stdio.h>
#define max 100

int main(void)
{
    int n;
    int m = 9999;
    printf("Enter the number of nodes: \n");
    scanf("%d", &n);
    int i, j;
    int mat[n][n];
    printf("Enter the matrix: \n");
    for (i = 0; i < n; i++)
    {
    for (j = 0; j < n; j++)
    {
    scanf("%d", &mat[i][j]);
    }
    }
    int arr[n];
    printf("Enter the heuristic: \n");
    for (i = 0; i < n; i++)
    {
    scanf("%d", &arr[i]);
    }
    int start;
    printf("Enter the start node: \n");
    scanf("%d", &start);
    int goal;
    printf("Enter the goal state: \n");
    scanf("%d", &goal);
    int visited[max] = {0};
    visited[start] = 1;
    int x = start;
    int p = 0;
    int y;
    int v;
    int sum = 0;
    printf("Start stare is %c\n", start + 65);
    printf("Goal state is %c\n", goal + 65);
    while (x != goal)
    {
    for (i = 0; i < n; i++)
    {
    if (mat[x][i] != 0 && visited[i] != 1)
    {
    p = mat[x][i] + arr[i];
    if (m > p)
    {
    y = mat[x][i];
    m = p;
    v = i;
    }
    }
    }
    sum = sum + y;
    visited[v] = 1;
    printf("%c", v + 65);
    x = v;
    m = 9999;
    }
    printf("The cost is %d\n", sum);
    return 0;
}


Practical 8:::::::

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <time.h>
#include <getopt.h>
static int arrows;
static int debug = 0;
#define YOU 0
#define WUMPUS 1
#define PIT1 2
#define PIT2 3
#define BATS1 4
#define BATS2 5
#define LOCS 6
static int loc[LOCS];
#define NOT 0
#define WIN 1
#define LOSE -1
static int finished;
static int cave[20][3] =
    {
    {1,4,7},
    {0,2,9}, {1,3,11}, {2,4,13}, {0,3,5}, {4,6,14},
    {5,7,16}, {0,6,8}, {7,9,17}, {1,8,10}, {9,11,18},
    {2,10,12}, {11,13,19}, {3,12,14}, {5,13,15},
     {14,16,19}, {6,15,17}, {8,16,18}, {10,17,19}, {12,15,18},
     };

int getnum(char* prompt)
    {
        int n;
        printf("%s: ", prompt);
        scanf("%d", &n);
        return n;
    }

int getlet(char* prompt)
    {
        char c = '\n';
        printf("%s: ", prompt);
        while (c == '\n') {
        scanf("%c", &c);
        }
        return toupper(c);
    }

void print_instructions()
{
        printf( "WELCOME TO 'HUNT THE WUMPUS'\n"
        "THE WUMPUS LIVES IN A CAVE OF 20 ROOMS. EACH ROOM\n"
        "HAS 3 TUNNELS LEADING TO OTHER ROOMS. (LOOK AT A\n"
        "DODECAHEDRON TO SEE HOW THIS WORKS-IF YOU DON'T KNOW\n"
        "WHAT A DODECAHEDRON IS, ASK SOMEONE)\n"
        "\n"
        " HAZARDS:\n"
        " BOTTOMLESS PITS: TWO ROOMS HAVE BOTTOMLESS PITS INTHEM\n"" IF YOU GO THERE, YOU FALL INTO THE PIT (& LOSE!)\n"
        " SUPER BATS : TWO OTHER ROOMS HAVE SUPER BATS. IF YOU\n"
        " GO THERE, A BAT GRABS YOU AND TAKES YOU TO SOME OTHER\n"
        " ROOM AT RANDOM. (WHICH MAY BE TROUBLESOME)\n"
        " WUMPUS:\n"
        " THE WUMPUS IS NOT BOTHERED BY HAZARDS (HE HAS SUCKER\n"
        " FEET AND IS TOO BIG FOR A BAT TO LIFT). USUALLY\n"
        " HE IS ASLEEP. TWO THINGS WAKE HIM UP: YOU SHOOTINGAN\n"
        " ARROW OR YOU ENTERING HIS ROOM.\n"
        " IF THE WUMPUS WAKES HE MOVES (P=.75) ONE ROOM\n"
        " OR STAYS STILL (P=.25). AFTER THAT, IF HE IS WHERE YOU\n"
        " ARE, HE EATS YOU UP AND YOU LOSE!\n"
        "\n"
        " YOU:\n"
        " EACH TURN YOU MAY MOVE OR SHOOT A CROOKED ARROW\n"
        " MOVING: YOU CAN MOVE ONE ROOM (THRU ONE TUNNEL)\n"
        " ARROWS: YOU HAVE 5 ARROWS. YOU LOSE WHEN YOU RUNOUT\n"
        " EACH ARROW CAN GO FROM 1 TO 5 ROOMS. YOU AIMBYTELLING\n"
        " THE COMPUTER THE ROOM#S YOU WANT THE ARROWTOGOTO.\n"
        " IF THE ARROW CAN'T GO THAT WAY (IF NO TUNNEL) IT MOVES\n"
        " AT RANDOM TO THE NEXT ROOM.\n"
        " IF THE ARROW HITS THE WUMPUS, YOU WIN.\n"
        " IF THE ARROW HITS YOU, YOU LOSE.\n"
        " WARNINGS:\n"
        " WHEN YOU ARE ONE ROOM AWAY FROM A WUMPUS OR HAZARD,\n"
        " THE COMPUTER SAYS:\n"
        " WUMPUS: 'I SMELL A WUMPUS'\n"
        " BAT : 'BATS NEARBY'\n"
        " PIT : 'I FEEL A DRAFT'\n"
        "\n"
        );
    }

void show_room()
    {
        printf("\n");
        for (int k = 0; k < 3; k++) {
        int room = cave[loc[YOU]][k];
        if (room == loc[WUMPUS]) {
        printf("I SMELL A WUMPUS!\n");
        } else if (room == loc[PIT1] || room == loc[PIT2]) {
        printf("I FEEL A DRAFT\n");
        } else if (room == loc[BATS1] || room == loc[BATS2]) {
        printf("BATS NEARBY!\n");
        }
        }
        printf("YOU ARE IN ROOM %d\n", loc[YOU]+1);
        printf("TUNNELS LEAD TO %d %d %d\n\n", cave[loc[YOU]][0]+1, cave[loc[YOU]][1]+1, cave[loc[YOU]][2]+1);
    }

int move_or_shoot()
    {
    int c = -1;
    while ((c != 'S') && (c != 'M')) {
    c = getlet("SHOOT OR MOVE (S-M)");
    }
    return (c == 'S') ? 1 : 0;
    }

void move_wumpus()
{
    int k = rand() % 4;
    if (k < 3) {
    loc[WUMPUS] = cave[loc[WUMPUS]][k];
    }
    if (loc[WUMPUS] == loc[YOU]) {
    printf("TSK TSK TSK - WUMPUS GOT YOU!\n");
    finished = LOSE;
    }
}

void shoot()
    {
    int path[5];
    int scratchloc = -1;
    finished = NOT;
    int len = -1;
    while (len < 1 || len > 5) {
    len = getnum("NO. OF ROOMS (1-5)");
    }
    int k = 0;
    while (k < len) {
    path[k] = getnum("ROOM #") - 1;
    if ((k>1) && (path[k] == path[k-2])) {
    printf("ARROWS AREN'T THAT CROOKED - TRY ANOTHER ROOM\n");
    continue;
    }
    k++;
    }
    scratchloc = loc[YOU];
    for (int k = 0; k < len; k++) {
    if ((cave[scratchloc][0] == path[k]) ||
    (cave[scratchloc][1] == path[k]) ||
    (cave[scratchloc][2] == path[k])) {
    scratchloc = path[k];
    } else {
    scratchloc = cave[scratchloc][rand()%3];
    }
    if (scratchloc == loc[WUMPUS]) {
    printf("AHA! YOU GOT THE WUMPUS!\n");
    finished = WIN;
    } else if (scratchloc == loc[YOU]) {
    printf("OUCH! ARROW GOT YOU!\n");
    finished = LOSE;
    }
    if (finished != NOT) {
    return;
    }
    }
    printf("MISSED\n");
    move_wumpus();
    if (--arrows <= 0) {
    finished = LOSE;
    }
}

void move()
    {
    int scratchloc = -1;
    while (scratchloc == -1) {
    scratchloc = getnum("WHERE TO")-1;
    if (scratchloc < 0 || scratchloc > 19) {
    scratchloc = -1;
    continue;
    }
    if ((cave[loc[YOU]][0] != scratchloc) &
    (cave[loc[YOU]][1] != scratchloc) &
    (cave[loc[YOU]][2] != scratchloc) &
    (loc[YOU] != scratchloc)) {
    printf("NOT POSSIBLE\n");
    scratchloc = -1;
    continue;
    }
    }
    loc[YOU] = scratchloc;
    while ((scratchloc == loc[BATS1]) || (scratchloc == loc[BATS2])) {
    printf("ZAP--SUPER BAT SNATCH! ELSEWHEREVILLE FOR YOU!\n");
    scratchloc = loc[YOU] = rand()%20;
    }
    if (scratchloc == loc[WUMPUS]) {
    printf("... OOPS! BUMPED A WUMPUS!\n");
    move_wumpus();
    }
    if (scratchloc == loc[PIT1] || scratchloc == loc[PIT2]) {
    printf("YYYYIIIIEEEE . . . FELL IN PIT\n");
    finished = LOSE;
    }
}

void game_setup()
{
    for (int j = 0; j < LOCS; j++) {
    loc[j] = -1;
    while (loc[j] < 0) {
    loc[j] = rand()%20;
    for (int k=0; k<j-1; k++) {
    if (loc[j] == loc[k]) {
    loc[j] = -1;
    }
    }
    }
    }
}

    void game_play() {
    arrows = 5;
    printf("HUNT THE WUMPUS\n");
    if (debug) {
    printf("Wumpus is at %d, pits at %d & %d, bats at %d & %d\n", loc[WUMPUS]+1, loc[PIT1]+1, loc[PIT2]+1, loc[BATS1]+1, loc[BATS2]+1);
    }
    finished = NOT;
    while (finished == NOT) {
    show_room();
    if (move_or_shoot()) {
    shoot();
    } else {
    move();
    }
    }
    if (finished == WIN) {
    printf("HEE HEE HEE - THE WUMPUS'LL GET YOU NEXT TIME!!\n");
    }
    if (finished == LOSE) {
    printf("HA HA HA - YOU LOSE!\n");
    }
    int c = getlet("NEW GAME (Y-N)");
    if (c == 'N') {
    exit(0);
    }
}

void handle_params(int argc, char* argv[]) {
int c;
    while ((c = getopt(argc, argv, "s:dh")) != -1) {
    switch (c) {
    case 's':
    srand(atoi(optarg));
    break;
    case 'd':
    debug = 1;
    break;
    case 'h':
    default:
    printf("usage: ./%s [-h] [-d] [-s seed]\n", argv[0]);
    exit(1);
    }
    }
}

int main(int argc, char* argv[])
{
    srand(time(0));
    handle_params(argc, argv);
    int c = getlet("INSTRUCTIONS (Y-N)");
    if (c == 'Y') {
    print_instructions();
    }
    do {
    game_setup();
    game_play();
    } while (getlet("NEW GAME (Y-N)") != 'N');
    return 0;
}


Practical 10::::::

#include <bits/stdc++.h>
using namespace std;

class NaiveBayesClassifier
{
private:
    unordered_map<int,double> classes;
    unordered_map<int, unordered_map<int, double>> attributesPerClass;
public:
    NaiveBayesClassifier(vector<vector<int>> &data, int DimSize)
    {
        for(auto entry:data)
        {
            if(classes.find(entry[0])==classes.end())
            {
                classes[entry[0]] = 1;
                unordered_map<int, double> pxc;
                attributesPerClass[entry[0]] = pxc;
            }
            else
            {
                classes[entry[0]] += 1;
            }
            for(int k=1; k<=DimSize; k++)
            {
                if(attributesPerClass[entry[0]].find(entry[k]) == attributesPerClass[entry[0]].end())
                {
                    attributesPerClass[entry[0]][entry[k]] = 1;
                }
                else
                {
                    attributesPerClass[entry[0]][entry[k]] += 1;
                }
            }
        }

        for(auto seg: attributesPerClass)
        {
            if(seg.first == 0)
            {
                cout<<"---Class Apple"<< " ---"<<endl;
            }
            if(seg.first == 1)
            {
                cout<<"---Class PineApple"<< " ---"<<endl;
            }
            if(seg.first == 2)
            {
                cout<<"---Class Cherry"<< " ---"<<endl;
            }
            for(auto entry: seg.second)
            {
                entry.second /= classes[seg.first];
                cout<<"Attribute P(A="<<entry.first << "| B="<<seg.first<<") = "<<entry.second<<endl;
            }
            classes[seg.first] /= data.size();
            cout<<"Class P(B="<<seg.first<< ") = "<<classes[seg.first]<<"\n\n";
        }
    }

    int predict(vector<int> attributes)
    {
        int maxcid = -1;
        double maxp = 0;
        for(auto cls: classes)
        {
            double pCx = cls.second;
            for(int i=0; i<attributes.size(); i++)
            {
                pCx *= attributesPerClass[cls.first][attributes[i]];
            }
            if(pCx > maxp)
            {
                maxp = pCx;
                maxcid = cls.first;
            }
    }
    cout<<"PRedict Class:\t"<<maxcid<< "===>P(A|B) = "<<maxp<<endl;
    return maxcid;
    }

};

void populateData(vector<vector<int>> &data, unordered_map<string, int> &classmap, unordered_map<string, int> &attrimap,
                  string c, string a1, string a2, int K)
                  {
                      vector<int> apair = {classmap[c],attrimap[a1], attrimap[a2]};
                      vector<vector<int>> newarr(K, apair);
                      data.insert(data.end(), newarr.begin(), newarr.end());
                  }

int main() {
        unordered_map<string, int> classmap = {{"apple", 0}, {"pineapple", 1}, {"cherry", 2}};
        unordered_map<string, int> attrimap =
        {
            {"red",0},{"green",1},{"yellow",2},
            {"round",10},{"oval",11}, {"heart", 12}
        };
        vector<vector<int>> data;
        populateData(data, classmap, attrimap, "apple", "green","round",20);
        populateData(data, classmap, attrimap, "apple", "red","round",50);
        populateData(data, classmap, attrimap, "apple", "yellow","round",10);
        populateData(data, classmap, attrimap, "apple", "red","oval",5);
        populateData(data, classmap, attrimap, "apple", "red","heart",5);
        populateData(data, classmap, attrimap, "pineapple", "green","oval",30);
        populateData(data, classmap, attrimap, "pineapple", "yellow","oval",70);
        populateData(data, classmap, attrimap, "pineapple", "green","round",5);
        populateData(data, classmap, attrimap, "pineapple", "yellow","round",5);
        populateData(data, classmap, attrimap, "cherry", "yelloe","heart",50);
        populateData(data, classmap, attrimap, "cherry", "red","heart",70);
        populateData(data, classmap, attrimap, "cherry", "yellow","round",5);
        random_shuffle(data.begin(),data.end());

        NaiveBayesClassifier mymodel(data,2);

        int cls = mymodel.predict({attrimap["red"],attrimap["round"]});
        if(cls == 0)
        {
            cout<<"Predicted Class:\tApple"<<endl;
        }
        if(cls==1)
        {
            cout<<"Predicted Class:\tPineApple"<<endl;
        }
         if(cls==2)
        {
            cout<<"Predicted Class:\tCherry"<<endl;
        }

        return 0;
}