AI Lab file 2024

 

 

Assignment 1

 

Problem – Write a program to find out the next state of a given 8-puzzle problem.

 

Solution:

 

import heapq

 

# Define the goal state

goal_state = [[1, 2, 3],

              [4, 5, 6],

              [7, 8, 0]]

 

# Define the possible moves

moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]

 

 

def heuristic(state):

    # Manhattan distance heuristic

    distance = 0

    for i in range(3):

        for j in range(3):

            if state[i][j] != 0:

                goal_row, goal_col = (state[i][j] - 1) // 3, (state[i][j] - 1) % 3

                distance += abs(i - goal_row) + abs(j - goal_col)

    return distance

 

 

def get_next_states(state):

    next_states = []

    for i in range(3):

        for j in range(3):

            if state[i][j] == 0:

                for move in moves:

                    new_i, new_j = i + move[0], j + move[1]

                    if 0 <= new_i < 3 and 0 <= new_j < 3:

                        new_state = [row[:] for row in state]

                        new_state[i][j], new_state[new_i][new_j] = new_state[new_i][new_j], new_state[i][j]

                        next_states.append(new_state)

    return next_states

 

 

def astar(start_state):

    frontier = [(heuristic(start_state), 0, start_state)]

    explored = set()

 

    while frontier:

        _, cost, current_state = heapq.heappop(frontier)

        if current_state == goal_state:

            return current_state

 

        explored.add(tuple(map(tuple, current_state)))

 

        for next_state in get_next_states(current_state):

            if tuple(map(tuple, next_state)) not in explored:

                heapq.heappush(frontier, (heuristic(next_state) + cost + 1, cost + 1, next_state))

 

    return None

 

 

def print_puzzle(puzzle):

    for row in puzzle:

        print(" ".join(map(str, row)))

 

 

if __name__ == "__main__":

    # Example usage

    initial_state = [[1, 2, 3],

                     [4, 0, 5],

                     [7, 8, 6]]

 

    print("Initial state:")

    print_puzzle(initial_state)

 

    solution = astar(initial_state)

 

    if solution:

        print("\nSolution found:")

        print_puzzle(solution)

    else:

        print("No solution found!")

 

Assignment 2

 

Problem – Write a program to compute Manhattan distance of a state in 8-puzzle problem.

 

Solution:-

 

def manhattan_distance(state):

    distance = 0

    for i in range(3):

        for j in range(3):

            if state[i][j] != 0:

                goal_row, goal_col = (state[i][j] - 1) // 3, (state[i][j] - 1) % 3

                distance += abs(i - goal_row) + abs(j - goal_col)

    return distance

# Example usage

initial_state = [[1, 2, 3],

                 [4, 0, 5],

                 [7, 8, 6]]

 

print("Initial state:")

for row in initial_state:

    print(" ".join(map(str, row)))

 

print("\nManhattandistance:", manhattan_distance(initial_state))

Assignment 3

 

Problem – Write a program to check the 8-puzzle problem is solvable or not.

 

Solution:-

 

def count_inversions(puzzle):

    inversions = 0

    puzzle_list = [number for row in puzzle for number in row if number != 0]

    for i in range(len(puzzle_list)):

        for j in range(i + 1, len(puzzle_list)):

            if puzzle_list[i] > puzzle_list[j]:

                inversions += 1

            return inversions

def is_solvable(puzzle):

    inversions = count_inversions(puzzle)

    blank_row = 0

    for i in range(3):

        if 0 in puzzle[i]:

            blank_row = i

   if (inversions % 2 == 0 and blank_row % 2 == 0) or (inversions % 2 != 0 and blank_row % 2 != 0):

        return True

    else:

        return False

# Example usage

puzzle = [[1, 2, 3],

          [4, 5, 6],

          [8, 7, 0]]  # Unsolvable puzzle

 

print("Is the puzzle solvable?  A program by Madhav",is_solvable(puzzle))

Assignment 4

Problem – Write a program to solve 8-puzzle problem using BFS Algorithm.

 

 

Solution:

 

 

from collections import deque

goal_state = [[1, 2, 3],

              [4, 5, 6],

              [7, 8, 0]]

moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]

# Program by MADHAV

def get_next_states(state):

    next_states = []

    for i in range(3):

        for j in range(3):

            if state[i][j] == 0:

                for move in moves:

                    new_i, new_j = i + move[0], j + move[1]

                    if 0 <= new_i < 3 and 0 <= new_j < 3:

                        new_state = [row[:] for row in state]

                        new_state[i][j], new_state[new_i][new_j] = new_state[new_i][new_j], new_state[i][j]

                        next_states.append(new_state)

    return next_states

 

def bfs(start_state):

    queue = deque([(start_state, [])])

    visited = set()

 

    while queue:

        current_state, path = queue.popleft()

        if current_state == goal_state:

            return path

 

        visited.add(tuple(map(tuple, current_state)))

 

        for next_state in get_next_states(current_state):

            if tuple(map(tuple, next_state)) not in visited:

                queue.append((next_state, path + [next_state]))

# Example usage

initial_state = [[1, 2, 3],

                 [4, 0, 5],

                 [7, 8, 6]]

 

print("Initial state:")

for row in initial_state:

    print(" ".join(map(str, row)))

 

solution_path = bfs(initial_state)

 

if solution_path:

    print("\nSolution found in", len(solution_path), "steps:")

    for step, state in enumerate(solution_path):

        print("Step", step + 1, ":")

        for row in state:

            print(" ".join(map(str, row)))

else:

    print("No solution found!")

Assignment 4

 

Problem – Write a program to solve 8-puzzle problem using BFS Algorithm.

 

 

Solution:

 

 

from collections import deque

goal_state = [[1, 2, 3],

              [4, 5, 6],

              [7, 8, 0]]

moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]

# Program by MADHAV

def get_next_states(state):

    next_states = []

    for i in range(3):

        for j in range(3):

            if state[i][j] == 0:

                for move in moves:

                    new_i, new_j = i + move[0], j + move[1]

                    if 0 <= new_i < 3 and 0 <= new_j < 3:

                        new_state = [row[:] for row in state]

                        new_state[i][j], new_state[new_i][new_j] = new_state[new_i][new_j], new_state[i][j]

                        next_states.append(new_state)

    return next_states

 

def bfs(start_state):

    queue = deque([(start_state, [])])

    visited = set()

 

    while queue:

        current_state, path = queue.popleft()

        if current_state == goal_state:

            return path

 

        visited.add(tuple(map(tuple, current_state)))

 

        for next_state in get_next_states(current_state):

            if tuple(map(tuple, next_state)) not in visited:

                queue.append((next_state, path + [next_state]))

# Example usage

initial_state = [[1, 2, 3],

                 [4, 0, 5],

                 [7, 8, 6]]

 

print("Initial state:")

for row in initial_state:

    print(" ".join(map(str, row)))

 

solution_path = bfs(initial_state)

 

if solution_path:

    print("\nSolution found in", len(solution_path), "steps:")

    for step, state in enumerate(solution_path):

        print("Step", step + 1, ":")

        for row in state:

            print(" ".join(map(str, row)))

else:

    print("No solution found!")

Assignment 5

 

Problem – Write a program in prolog to implement movie recommendation system.

 

 

Solution:

 

1. likes(Madhav, south).

2. likes(viral, mystery).

3. likes(anuj, action).

4. likes(ravi, sci-fi).

5. likes(anu, history).

6. likes(vicky, sci-fi).

 

7. movies(hum tum, mystery).

8. movies(the nun, horror).

9. movies(humshakals, comedy).

10. movies(avengers, sci-fi).

11. movies(war, action).

12. movies(extraction, action).

13. movies(the_maze_runner, sci-fi).

14. movies(inside, action).

15. movies(mummy, history).

16. movies(lucky_the_racer, south).

17. movies(pushpa, south).

 

18. recommend_to(Person, Movies) :-

    likes(Person, Category),

    movies(Movie, Category), Movies = Movie.

Assignment 6

 

Problem - Write a program in prolog to check whether a number is natural or not.

 

 

Solution:

 

1.     mother_child(rahul,ram).

2.     father_child(prateek, shyam).

3.     father_child(prateek, ravi).

4.     father_child(prateek, shyam).

5.     sibling(X, Y) :- parent_child(Z, X), parent_child(Z, Y).

6.     parent_child(X, Y) :- father_child(X, Y).

7.     parent_child(X, Y) :- mother_child(X, Y).

Assignment 7

 

 

Problem - Write a program in prolog to check whether a number is natural or not.

 

Solution:

 

1. nat(N) :- between(0, infinite, N).

 

Output:

 

 

Assignment 8

 

 

Problem - Write a program in prolog to check the membership of an element from a list.

 

Solution:

 

1. member(X, [X|_]).

2. member(X, [_|T]) :- member(X, T).

 

 

 

Output:

Assignment 9

 

 

Problem - Write a program in prolog to add an element in front of a list.

 

Solution:

 

1. add_front(X, [], [X]).

2. add_front(X, [H|T], [X,H|T]).

 

 

 

Output:

Assignment 10

 

 

Problem - Write a program in prolog to delete an element from the front of a list.

 

Solution:

 

1. delete_front([_|T], T).

 

 Output:

Assignment 11

 

 

Problem – Write a program in prolog to find out gcd of two numbers.

 

Solution:

 

1. gcd(X,0,X).

2. gcd(X,Y,Z) :- R is mod(X,Y), gcd(Y,R,Z).

                                                  OUTPUT

Assignment 12

 

 

Problem - The monkey-and-bananas problem is often used in the Al literature to demonstrate ideas about common-sense reasoning. The problem can be stated as follows: A monkey is in a room containing a box and a bunch of bananas. The bananas are hanging from the ceiling out of reach of the monkey. How can the monkey obtain the bananas. (The monkey is supposed to go to the box, push it under the bananas, climb on top of it and grasp the bananas.)

Write the production rules for the above problem. Implement the above problem in prolog.

 

 

Solution:

 

1. move(state(middle, onbox, middle, hasnot), grasp,   state(middle, onbox, middle, has)).

2. move(state(P, onfloor, P, H), climb, state(P, onbox, P, H)).

3. move(state(P1, onfloor, P1, H), push(P1, P2), state(P2, onfloor, P2, H)).

4. move(state(P1, onfloor, B, H), walk(P1, P2), state(P2, onfloor, B, H)).

5. canget(state(_,_,_,has)) :- write("yes can get").

6. canget(State1) :- move(State1, Op, State2), canget(State2).

 

Output: