AI Lab 6

1. Graph Traversal using BFS

Write a program to perform a Breadth-First Search (BFS) on a directed graph. Given a graph represented by an adjacency list and a starting node, your program should print the nodes in the order they are visited.

Sample Input:

The input should be a dictionary or map representing the adjacency list, and an integer or string for the starting node.

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

Expected Output:

A list or a string showing the sequence of visited nodes.

['A', 'B', 'C', 'D', 'E', 'F']

▶ View Approach & Pseudocode

Approach:

Use a queue to store nodes to visit and a set to track visited nodes. Start with the root, add it to the queue and visited set. While the queue isn't empty, dequeue a node, process it, and add its unvisited neighbors to both the queue and the visited set.

Pseudocode:

function BFS(graph, startNode):
  queue = new Queue()
  visited = new Set()
  result = []

  queue.enqueue(startNode)
  visited.add(startNode)

  while queue is not empty:
    currentNode = queue.dequeue()
    result.add(currentNode)

    for each neighbor in graph[currentNode]:
      if neighbor is not in visited:
        visited.add(neighbor)
        queue.enqueue(neighbor)
  
  return result

2. Path Finding using DFS

Implement Depth-First Search (DFS) to find if a path exists in a maze. The maze is given as a 2D grid where 'S' is the start, 'E' is the end, '.' is a valid path, and '#' is a wall.

Sample Input:

A 2D list or array representing the maze.

maze = [
  ['S', '.', '.', '#'],
  ['.', '#', '.', '#'],
  ['.', '#', '.', '.'],
  ['.', '.', '#', 'E']
]

Expected Output:

A boolean value: `True` if a path is found, otherwise `False`.

True

▶ View Approach & Pseudocode

Approach:

Use recursion or a stack. From the starting point 'S', explore one neighbor as far as possible. If you hit a dead end (a wall or visited cell), backtrack and try another path. The base cases for the recursion are: finding 'E' (success), or going out of bounds/hitting a wall (failure). Mark visited cells to avoid loops.

Pseudocode:

function solveMaze(maze, row, col):
  if out_of_bounds(row, col) or maze[row][col] is '#':
    return false
  if maze[row][col] is 'E':
    return true
  if maze[row][col] is 'visited':
    return false
  
  mark maze[row][col] as 'visited'

  path_found = solveMaze(maze, row+1, col) OR
               solveMaze(maze, row-1, col) OR
               solveMaze(maze, row, col+1) OR
               solveMaze(maze, row, col-1)

  return path_found

3. Implement Tic-Tac-Toe Game

Create a two-player, command-line Tic-Tac-Toe game. The program should display the 3x3 board, accept player moves, update the board, and declare a winner or a draw. It should also handle invalid moves (e.g., choosing an already occupied cell).

Sample Input:

A sequence of integer inputs from 1 to 9 from two alternating players, corresponding to the board positions.

Player X, enter your move (1-9): 5
Player O, enter your move (1-9): 1
...and so on.

Expected Output:

The board state printed after each move, followed by a final game-over message.

  |   |  
-----------
  | X |  
-----------
  |   |  
...
Player X wins!

▶ View Approach & Pseudocode

Approach:

Use a 1D or 2D array to represent the board. Create a game loop that continues until a win or draw. Inside the loop: display the board, get the current player's input, validate it, update the board state, check for a win/draw, and then switch players.

Pseudocode:

function main():
  board = create_empty_board()
  currentPlayer = 'X'

  while game_is_not_over:
    printBoard(board)
    move = getPlayerInput(currentPlayer)
    
    if isValidMove(board, move):
      updateBoard(board, move, currentPlayer)
      if checkWinner(board, currentPlayer):
        print(currentPlayer + " wins!")
        break
      if isBoardFull(board):
        print("It's a draw!")
        break
      currentPlayer = switchPlayer(currentPlayer)
    else:
      print("Invalid move.")

4. Shuffle a Deck of Cards in Python

Write a Python program that creates a standard 52-card deck (4 suits, 13 ranks), and then shuffles it into a random order.

NoInputNeeded:

This program does not require any user input.

Expected Output:

A list of 52 strings, where each string represents a card. The order of the cards in the list should be random.

['7 of Diamonds', 'King of Spades', '2 of Clubs', ... (and 49 other random cards)]

▶ View Approach & Pseudocode

Approach:

First, generate a list of all 52 cards. You can do this with nested loops: one for suits and one for ranks. Once you have the ordered list, use a shuffling algorithm like Fisher-Yates or a built-in library function (e.g., Python's `random.shuffle`) to randomize the list in-place.

Pseudocode:

function createDeck():
  suits = ["Hearts", "Diamonds", "Clubs", "Spades"]
  ranks = ["2", "3", "4", ..., "King", "Ace"]
  deck = new List()
  
  for each suit in suits:
    for each rank in ranks:
      deck.add(rank + " of " + suit)
  return deck

function shuffle(deck):
  // Use built-in random shuffle function
  random.shuffle(deck)

// Main execution
deck = createDeck()
shuffle(deck)
print(deck)