Scribd
Upload
12 views6 pages

Python Graph and Game Algorithms

The document contains four Python programs: the first implements Breadth First Search (BFS) for graph traversal, the second implements Depth First Search (DFS), the third is a Tic-Tac-Toe game, and the fourth implements the A* algorithm for solving an 8-puzzle game. Each program includes function definitions and example usage. The document provides a comprehensive overview of various algorithms and game implementations in Python.

Uploaded by

mmanojm005
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
12 views6 pages

Python Graph and Game Algorithms

The document contains four Python programs: the first implements Breadth First Search (BFS) for graph traversal, the second implements Depth First Search (DFS), the third is a Tic-Tac-Toe game, and the fourth implements the A* algorithm for solving an 8-puzzle game. Each program includes function definitions and example usage. The document provides a comprehensive overview of various algorithms and game implementations in Python.

Uploaded by

mmanojm005
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Program 01: Write a program to implement Breadth First search using Python.

from collections import deque


def bfs(graph, start):
visited = set() # To keep track of visited nodes
queue = deque([start]) # Initialize queue with the start node
result = [] # To store the BFS traversal order
while queue:
node = [Link]() # Dequeue a node
if node not in visited:
[Link](node) # Mark node as visited
[Link](node) # Store traversal order
[Link]([Link](node, [])) # Enqueue all unvisited neighbors
return result
# Example usage
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', '2'],
'C': ['A', 'F', 'G'],
'D': ['B'],
'2': ['B', 'H'],
'F': ['C'],
'G': ['C'],
'H': ['2']
}
start_node = 'A'
print("BFS Traversal:", bfs(graph, start_node))

Output:
BFS Traversal: ['A', 'B', 'C', 'D', '2', 'F', 'G', 'H']
Program 02: Write a Program to implement Depth First search algorithm using python.

# DFS algorithm in Python

# DFS algorithm
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
[Link](start)

print(start)

for next in graph[start] - visited:


dfs(graph, next, visited)
return visited

graph = {'0': set(['1', '2']),


'1': set(['0', '3', '4']),
'2': set(['0']),
'3': set(['1']),
'4': set(['2', '3'])}

dfs(graph, '0')
output:
Program 03: Write a Program to implement Tic-Tac-Toe game using python.

# Tic-Tac-Toe Game in Python


# Function to initialize the board
def initialize_board():
return [[' ' for _ in range(3)] for _ in range(3)]
# Function to print the board
def print_board(board):
for row in board:
print('|'.join(row))
print('-' * 5)
# Function to check if a player has won
def check_winner(board, player):
# Check rows and columns
for i in range(3):
if all(board[i][j] == player for j in range(3)) or all(board[j][i] == player for j in range(3)):
return True
# Check diagonals
if all(board[i][i] == player for i in range(3)) or all(board[i][2 - i] == player for i in
range(3)):
return True
return False
# Function to check if the board is full
def is_draw(board):
return all(board[i][j] != ' ' for i in range(3) for j in range(3))
# Function to handle player moves
def make_move(board, player):
while True:
try:
row, col = map(int, input(f"Player {player}, enter row and column (0-2): ").split())
if board[row][col] == ' ':
board[row][col] = player
break
else:
print("Cell already occupied! Choose another one.")
except (ValueError, IndexError):
print("Invalid input! Enter row and column as two numbers between 0 and 2.")
# Main game function
def play_tic_tac_toe():
board = initialize_board()
current_player = 'X'
while True:
print_board(board)
make_move(board, current_player)
if check_winner(board, current_player):
print_board(board)
print(f"Player {current_player} wins!")
break
if is_draw(board):
print_board(board)
print("It's a draw!")
break
# Switch player
current_player = 'O' if current_player == 'X' else 'X'
# Start the game
if __name__ == "__main__":
play_tic_tac_toe()

Output:
Program 04: Write a program to implement 8-puzzle game using python.

import heapq
import numpy as np

def find_zero(board):
x, y = [Link](board == 0)
return x[0], y[0] # Extract first element properly

def get_moves(board):
x, y = find_zero(board)
moves = []
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

for dx, dy in directions:


nx, ny = x + dx, y + dy
if 0 <= nx < 3 and 0 <= ny < 3:
new_board = [Link]()
new_board[x, y], new_board[nx, ny] = new_board[nx, ny], new_board[x, y]
[Link](new_board)

return moves

def heuristic(board):
goal = [Link]([[1, 2, 3], [4, 5, 6], [7, 8, 0]])
return int([Link](board != goal)) # Ensure heuristic returns an integer

def a_star(initial_board):
pq = [(heuristic(initial_board), 0, tuple(map(tuple, initial_board)), [])]
visited = set()
goal_state = tuple(map(tuple, [Link]([[1, 2, 3], [4, 5, 6], [7, 8, 0]])))

while pq:
_, moves, board, path = [Link](pq)

if board == goal_state:
return path + [board]

[Link](board)

for move in get_moves([Link](board)):


move_tuple = tuple(map(tuple, move))
if move_tuple not in visited:
[Link](pq, (heuristic(move) + moves + 1, moves + 1, move_tuple, path +
[board]))

return None

if __name__ == "__main__":
initial_board = [Link]([[1, 2, 3], [4, 0, 6], [7, 5, 8]])
solution = a_star(initial_board)

if solution:
for step, board in enumerate(solution):
print(f"Step {step}:")
print([Link](board), "\n")
else:
print("No solution found!")

Common questions

Powered by AI

The use of a priority queue in the A* algorithm implementation enhances efficiency by ensuring that nodes with the lowest combined cost of the current path and estimated path (from the heuristic) are always expanded first . This prioritization allows the algorithm to systematically explore paths that are most promising towards solving the puzzle, minimizing processing time and ensuring optimal pathfinding compared to a breadth-first approach that does not use heuristics or prioritization.

BFS uses a queue to explore the graph level by level, ensuring that all neighbors of a node are visited before moving on to the next node at a deeper level . DFS, on the other hand, uses recursion or a stack to explore as deep as possible along a branch before backtracking, visiting nodes more in a depth-wise manner . This structural difference leads to BFS usually being better suited for finding the shortest path in unweighted graphs, while DFS is often more memory efficient in deep graphs.

BFS explicitly addresses the challenge of finding the shortest path in an unweighted graph as it explores nodes layer by layer, guaranteeing that the first time it visits the target node, it has found the shortest path . DFS does not inherently find the shortest path because it explores as deep as possible before backtracking, potentially ignoring optimal paths that could be explored earlier if it followed a breadth-wise strategy . While DFS can be adapted to find paths, it requires additional logic to compare path lengths post-traversal.

In both BFS and DFS algorithms, the 'visited' set functions as a crucial component for avoiding reprocessing nodes and preventing infinite loops. In BFS, every node is marked as visited once dequeued and processed, ensuring level order exploration without redundancy . Similarly, in DFS, the 'visited' set keeps track of nodes that have been completely explored, allowing the algorithm to backtrack appropriately and explore all potential branches of the graph . This mechanism fundamentally optimizes traversal efficiency and correctness.

The Tic-Tac-Toe program determines the end of the game by checking for a winner or a draw. It scans rows, columns, and diagonals for three consecutive identical marks ('X' or 'O') to declare a winner. A draw is identified by checking if all board cells are occupied without any player winning . These checks are continuously executed after each move, enabling prompt game termination upon fulfillment of either condition.

Separating game functions in the Tic-Tac-Toe code offers the advantage of modularity, making the code easier to read, maintain, and debug . Each function is responsible for a distinct aspect of the game, such as initializing the board, checking for a winner, handling player moves, or detecting a draw, allowing developers to manage, test, and update these features independently or collaboratively without affecting the entire system.

The heuristic function in the A* algorithm estimates the cost to reach the goal state from the current state by counting the number of tiles not in their goal position, which helps prioritize nodes closer to the solution . By always evaluating the sum of the past path cost and this heuristic estimate, A* can efficiently explore paths that are likely to lead to a solution, reducing unnecessary computations compared to uninformed search strategies.

The Tic-Tac-Toe program ensures valid and fair gameplay by prompting players to input their moves and checking that the chosen cell is not already occupied. Invalid inputs are rejected, and the game enforces alternating turns between players 'X' and 'O' . This built-in validation and turn alternation prevent illegal moves and ensure that each player has an equal opportunity to make a move.

The 8-puzzle game implementation demonstrates the principles of the A* search algorithm by using a combination of path cost and heuristic cost to guide the search process. It employs a priority queue to manage the exploration of game states, always choosing the node that offers the lowest total cost based on current path length and heuristic estimates towards the goal . This implementation ensures efficient exploration and optimal pathfinding typical of A*, leveraging cost-effective decision-making to solve complex puzzles.

The initial placement of the '0' (empty tile) in the 8-puzzle game significantly affects the number of moves required to solve the puzzle. When '0' is positioned near the center, it maximizes the potential adjacent moves, leading to more flexible solutions . If '0' starts in a corner or edge, fewer immediate moves are possible, which can constrain the solution path and potentially increase the number of moves needed to reach the goal state compared to a more centrally located '0' tile.

You might also like