breadth_first_search_(1).py

# -*- coding: utf-8 -*-
"""BFS (2).ipynb

Automatically generated by Colab.

Original file is located at
    https://colab.research.google.com/drive/10VP702-aU28qCw3FyD-Nx0C4HK9Kpsu1
"""

from collections import deque
def bfs(graph, start, goal):
    queue=deque([(start, [start])])
    visited = set([start])
    while queue:
        current_node, path = queue.popleft()
        if current_node == goal:
            return path
        for neighbor in graph[current_node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path+[neighbor]))
    return None

graph = {
    'A':['F', 'C', 'B'],
    'F':['C', 'B', 'D'],
    'C':['B', 'D', 'E', 'G'],
    'B':['D', 'E', 'G'],
    'D':['E', 'G', 'J'],
    'F':['G', 'J', 'K']
}
start_node = 'A'
goal_node = 'F'

path = bfs(graph, start_node, goal_node)

if path:
    print("Path from ", start_node, "to ", goal_node,":", path)
else:
    print("NO PATH FOUND!!!")

from collections import deque
import os

def is_valid_state(m,c):
        return(m==0 or m>=c) and (3-m==0 or 3-m >= 3-c)
def get_successor(state):
        m,c, boat = state
        successors= []

        if boat == "left":
            moves = [(1,0), (2,0), (0,1),(0,2),(1,1)]
        else:
            moves = [(-1,0),(-2,0),(0,-1),(0,-2), (-1,-1)]
        for m_move, c_move in moves:
            new_m = m+m_move
            new_c = c+c_move
            new_boat = 'right' if boat == 'left' else 'left'
            if 0<=new_m<=3 and 0<=new_c<=3 and is_valid_state(new_m,new_c):
                successors.append((new_m, new_c, new_boat))
        return successors

def bfs():
        initial = (3, 3, 'left')
        goal = (0, 0, 'right')
        queue = deque([(initial, [])])
        visited = set()
        while queue:
            current, path = queue.popleft()
            if current in visited:
                continue
            visited.add(current)
            path = path + [current]
            if current == goal:
                return path
            for successor in get_successor(current):
                 queue.append((successor, path))
        return None

def main():
    soln = bfs()
    if soln:
        print("Solution: ")
        for state in soln:
            print(state)
    else:
        print("No solution found")

if __name__ == "__main__":
    main()

from collections import deque

class State:
    def __init__(self, cannibalLeft, missionaryLeft, boat, cannibalRight, missionaryRight):
        self.cannibalLeft = cannibalLeft
        self.missionaryLeft = missionaryLeft
        self.boat = boat
        self.cannibalRight = cannibalRight
        self.missionaryRight = missionaryRight
        self.parent = None

    def is_goal(self):
        return self.cannibalLeft == 0 and self.missionaryLeft == 0

    def is_valid(self):
        return self.missionaryLeft >= 0 and self.missionaryRight >= 0 \
               and self.cannibalLeft >= 0 and self.cannibalRight >= 0 \
               and (self.missionaryLeft == 0 or self.missionaryLeft >= self.cannibalLeft) \
               and (self.missionaryRight == 0 or self.missionaryRight >= self.cannibalRight)

def bfs(start_state):
    queue = deque([(start_state, [start_state])])
    visited = set([start_state])

    while queue:
        current_state, path = queue.popleft()

        if current_state.is_goal():
            return path

        for next_state in successors(current_state):
            if next_state not in visited:
                visited.add(next_state)
                next_path = path + [next_state]
                queue.append((next_state, next_path))

    return None

def successors(cur_state):
    children = []
    if cur_state.boat == 'left':

    else:
        # Define possible moves from right to left
        # Add valid moves to children list
    return children

# Define initial state
initial_state = State(3, 3, 'left', 0, 0)

# Solve the problem using BFS
path = bfs(initial_state)

if path:
    print("Solution found:")
    for i, state in enumerate(path):
        print(f"Step {i}: {state.cannibalLeft}, {state.missionaryLeft}, {state.boat}, {state.cannibalRight}, {state.missionaryRight}")
else:
    print("No solution found.")

from collections import deque

def bfs(graph, start, goal):
    queue = deque([(start, [start])])
    visited = set([start])

    while queue:
        current_node, path = queue.popleft()

        if current_node == goal:
            return path

        for neighbor in graph[current_node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    return None

def backtrack(graph, path):
    for i in range(len(path) - 1):
        current_node = path[i]
        next_node = path[i + 1]

        if next_node not in graph[current_node]:
            return False

    return True

# Sample input graph with adjacency nodes for each node
graph = {
    'A': ['F', 'C', 'B'],
    'F': ['C', 'B', 'D'],
    'C': ['B', 'D', 'E', 'G'],
    'B': ['D', 'E', 'G'],
    'D': ['E', 'G', 'J'],
    'G': ['J', 'K']
}

start_node = 'A'
goal_node = 'D'

path = bfs(graph, start_node, goal_node)

if path:
    if backtrack(graph, path):
        print("Path from", start_node, "to", goal_node, ":", path)
    else:
        print("Invalid path found.")
else:
    print("NO PATH FOUND!!!")