SOURCE CODE:

from collections import deque

def is_solvable(state, n):
inv_count = 0
flat = [tile for tile in state if tile != 0]
for i in range(len(flat)):
for j in range(i + 1, len(flat)):
if flat[i] > flat[j]:
inv_count += 1
if n % 2 == 1:
return inv_count % 2 == 0
else:
zero_row = [Link](0) // n
return (inv_count + zero_row) % 2 == 1

def get_neighbors(state, n):

neighbors = []
zero_index = [Link](0)
x, y = divmod(zero_index, n)
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for dx, dy in directions:
new_x, new_y = x + dx, y + dy
if 0 <= new_x < n and 0 <= new_y < n:
new_index = new_x * n + new_y
new_state = list(state)
new_state[zero_index], new_state[new_index] = new_state[new_index],
new_state[zero_index]
[Link]((tuple(new_state), new_state[zero_index]))
return neighbors

def print_board(state, n):

for i in range(n):
row = state[i*n:(i+1)*n]
print(' '.join(str(x) if x != 0 else '_' for x in row))
print()

def reconstruct_path(parents, end_state):

path = []
state = end_state
while parents[state][0] is not None:
parent_state, moved_tile = parents[state]
[Link]((state, moved_tile))
state = parent_state
[Link]((state, None)) # start state, no move
[Link]()
return path

def bfs(start, goal, n):

if not is_solvable(start, n):
 print("❌ Puzzle is not solvable.")
return

queue = deque([start])
visited = set([start])
parents = {start: (None, None)}

while queue:
current = [Link]()
if current == goal:
path = reconstruct_path(parents, current)
print(f"\n✅ Total moves: {len(path) - 1}")
print("🔁 Sequence of states and moves:\n")
for i, (state, move) in enumerate(path):
print(f"Step {i}:", end=' ')
if move is not None:
print(f"(Moved tile {move})")
else:
print("(Start state)")
print_board(state, n)
return

for neighbor, moved_tile in get_neighbors(current, n):

if neighbor not in visited:
[Link](neighbor)
parents[neighbor] = (current, moved_tile)
[Link](neighbor)

print("❌ Goal not reachable.")

# ===== Input Section =====

n = int(input("Enter N for N-Puzzle (e.g., 3 for 8-puzzle, 4 for 15-puzzle): "))
print(f"Enter {n*n} space-separated values for start state (0 for blank):")
start = tuple(map(int, input().split()))
print(f"Enter {n*n} space-separated values for goal state:")
goal = tuple(map(int, input().split()))

bfs(start, goal, n)

INPUT AND OUTPUT :

SOURCE CODE :
def is_goal(state, target_jug, target_value):
return state[target_jug - 1] == target_value

def get_next_states(state, jug1_cap, jug2_cap):

x, y = state
possible_states = set()

# Fill Jug 1 or Jug 2

possible_states.add((jug1_cap, y))
possible_states.add((x, jug2_cap))

# Empty Jug 1 or Jug 2

possible_states.add((0, y))
possible_states.add((x, 0))

# Pour Jug 1 → Jug 2

transfer = min(x, jug2_cap - y)
possible_states.add((x - transfer, y + transfer))

# Pour Jug 2 → Jug 1

transfer = min(y, jug1_cap - x)
possible_states.add((x + transfer, y - transfer))

return possible_states

def dfs(jug1_cap, jug2_cap, target_value, target_jug):

visited = set()
stack = [((0, 0), [])] # (current_state, path)

while stack:
current_state, path = [Link]()
if current_state in visited:
continue
[Link](current_state)

path = path + [current_state]

if is_goal(current_state, target_jug, target_value):

print("\nSolution Path (DFS):")
for step in path:
print(f"Jug1: {step[0]}, Jug2: {step[1]}")
return

for next_state in get_next_states(current_state, jug1_cap, jug2_cap):

if next_state not in visited:
[Link]((next_state, path))

print("No solution found.")

# === 🔹 Example Usage ===

if __name__ == "__main__":
jug1_cap = int(input("Enter capacity of Jug 1: "))
jug2_cap = int(input("Enter capacity of Jug 2: "))
target_value = int(input("Enter target amount of water: "))

while True:
target_jug = int(input("Which jug should contain the target amount? (1 or 2): "))
if target_jug in [1, 2]:
break
else:
print("Please enter 1 or 2.")

dfs(jug1_cap, jug2_cap, target_value, target_jug)

INPUT AND OUTPUT :

SOURCE CODE :
import heapq
from math import inf

def reconstruct_path(came_from, current):

path = [current]
while current in came_from:
current = came_from[current]
[Link](current)
[Link]()
return path

def a_star(graph, heuristics, start, goal):

# g_score: best known cost from start
g_score = {node: inf for node in graph}
g_score[start] = 0

# Min-heap of (f, counter, node); counter breaks ties to keep heap stable
open_heap = []
counter = 0
f_start = g_score[start] + [Link](start, inf)
[Link](open_heap, (f_start, counter, start))
counter += 1

# For pretty/accurate printing

open_set = {start}
closed_set = set()

# For path reconstruction

came_from = {}
step = 1
while open_heap:
# Clean printing of current OPEN/CLOSED (names only, sorted)
print(f"\n--- Step {step} ---")
print("Open List:", sorted(open_set))
print("Closed List:", sorted(closed_set))

# Pop best; skip stale entries

f, _, current = [Link](open_heap)
if current in closed_set:
# Already expanded with a better path earlier
continue
# It's no longer in open_set since we're expanding it now
if current in open_set:
open_set.remove(current)
print(f"Expanding node: {current}")
# Goal check
if current == goal:
path = reconstruct_path(came_from, current)
return path, g_score[current]
 # Mark current as expanded
closed_set.add(current)
# Explore neighbors
for neighbor, weight in graph[current].items():
if neighbor in closed_set:
continue

tentative_g = g_score[current] + weight

if tentative_g < g_score[neighbor]:
# Found a better path to neighbor
came_from[neighbor] = current
g_score[neighbor] = tentative_g
f_neighbor = tentative_g + [Link](neighbor, inf)
[Link](open_heap, (f_neighbor, counter, neighbor))
counter += 1
open_set.add(neighbor)

step += 1

return None, inf # No path found

# ---------------------- INPUT FUNCTIONS ----------------------

def input_graph():
n = int(input("Enter number of nodes: "))
print("Enter node names (space separated):")
nodes = input().split()

# Initialize adjacency as dict-of-dicts to dedupe edges (keep minimum weight)

graph = {u: {} for u in nodes}

undirected = input("Is the graph undirected? (y/n): ").strip().lower() in ("y", "yes")

m = int(input("Enter number of edges: "))

print("Enter edges as: source destination weight")
for _ in range(m):
u, v, w = input().split()
w = int(w)
# Keep only the minimum weight for (u,v)
if v not in graph[u] or w < graph[u][v]:
graph[u][v] = w
if undirected:
if u not in graph[v] or w < graph[v][u]:
graph[v][u] = w

print("Enter heuristic values for each node (name heuristic):")

heuristics = {}
for _ in range(n):
node, h = input().split()
heuristics[node] = int(h)
 start = input("Enter start node: ").strip()
goal = input("Enter goal node: ").strip()

# Basic validation
if start not in graph or goal not in graph:
raise ValueError("Start/Goal must be among the listed nodes.")

return graph, heuristics, start, goal

# ---------------------- MAIN ----------------------
if __name__ == "__main__":
graph, heuristics, start, goal = input_graph()
path, cost = a_star(graph, heuristics, start, goal)

if path:
print("\n✅ Shortest path found by A*:")
print(" -> ".join(path))
print("Total cost:", cost)
else:
print("❌ No path found.")

INPUT AND OUTPUT :

SOURCE CODE:
class AOStar:
def __init__(self, graph, heuristics):
[Link] = graph
self.H = heuristics
self.solution_graph = {}

def get_neighbors(self, node):

return [Link](node, [])

def ao_star(self, node, backtrack=False):

print(f"\nProcessing Node: {node}")

if node not in [Link]:

print(f"{node} is a goal node.")
return self.H[node]

min_cost = float('inf')
best_child = None

# Evaluate all child groups (AND/OR sets)

for child_group in self.get_neighbors(node):
cost = 0
for (child, edge_cost) in child_group:
cost += edge_cost + self.H[child]
print(f"Evaluating children {child_group} → Total cost = {cost}")

if cost < min_cost:

min_cost = cost
best_child = child_group

self.H[node] = min_cost
self.solution_graph[node] = best_child
print(f"Best choice for {node} → {best_child} with cost {min_cost}")

# Recursively solve best children

for (child, _) in best_child:
self.ao_star(child)

if backtrack:
print("Backtracking...")
self.ao_star(node)

def print_solution(self):
print("\nFinal Solution Graph:")
for k, v in self.solution_graph.items():
print(f"{k} → {v}")
graph = {}
heuristics = {}
n = int(input("Enter number of nodes: "))

for _ in range(n):
# Ask node name and heuristic in one line
node_input = input("\nEnter node name and heuristic value (format: Node,Heuristic): ")
node_name, h_val = node_input.split(",")
heuristics[node_name.strip()] = int(h_val.strip())

# Ask number of child groups

groups = int(input(f"How many AND/OR child groups for {node_name}? "))
child_groups = []

for _ in range(groups):
# Ask children with costs in one line
cg_input = input("Enter children and costs (format: child,cost child,cost ...): ").split()
child_group = [([Link](",")[0], int([Link](",")[1])) for c in cg_input]
child_groups.append(child_group)

if child_groups:
graph[node_name] = child_groups

ao = AOStar(graph, heuristics)
start = input("\nEnter start node: ")
ao.ao_star(start)
ao.print_solution()

INPUT AND OUTPUT :

SOURCE CODE :
import tkinter as tk
import random
import time

BOARD_SIZE = 8
QUEEN_SYMBOL = "♛"

class EightQueensHillClimb:
def __init__(self, root):
[Link] = root
[Link]("8-Queens Hill Climbing")
[Link] = []
self.create_board()
self.solve_button = [Link]([Link], text="Solve with Hill Climbing",
command=self.start_solving)
self.solve_button.pack(pady=10)

def create_board(self):
frame = [Link]([Link])
[Link]()
for i in range(BOARD_SIZE):
row_buttons = []
for j in range(BOARD_SIZE):
btn = [Link](frame, text="", width=4, height=2, relief="ridge", font=("Arial",
18))
[Link](row=i, column=j)
color = "white" if (i + j) % 2 == 0 else "lightgray"
[Link](bg=color)
row_buttons.append(btn)
[Link](row_buttons)

def display_state(self, state):

"""Show queens on the GUI board"""
for i in range(BOARD_SIZE):
for j in range(BOARD_SIZE):
[Link][i][j]['text'] = ""
for col, row in enumerate(state):
[Link][row][col]['text'] = QUEEN_SYMBOL
[Link]()
[Link](0.4)

def heuristic(self, state):

"""Count number of attacking pairs of queens"""
conflicts = 0
for i in range(BOARD_SIZE):
for j in range(i + 1, BOARD_SIZE):
if state[i] == state[j] or abs(state[i] - state[j]) == abs(i - j):
conflicts += 1
 return conflicts

def get_best_neighbor(self, state):

"""Generate neighbors and return best one"""
best_state = list(state)
best_h = [Link](state)
for col in range(BOARD_SIZE):
for row in range(BOARD_SIZE):
if state[col] != row:
neighbor = list(state)
neighbor[col] = row
h = [Link](neighbor)
if h < best_h:
best_h = h
best_state = neighbor
return best_state, best_h

def hill_climb(self):
"""Perform hill climbing with step logging"""
state = [[Link](0, BOARD_SIZE - 1) for _ in range(BOARD_SIZE)]
h = [Link](state)
step_count = 0

print(f"\n🚀 Starting new attempt with initial state: {state}, h={h}")

self.display_state(state)

while True:
neighbor, h_new = self.get_best_neighbor(state)
if h_new >= h: # No improvement
print(f"⚠️Local optimum reached at state {state}, h={h}")
break

print(f"➡️Step {step_count+1}: Move to {neighbor}, h={h_new}")

state, h = neighbor, h_new
step_count += 1
self.display_state(state)

return state, h, step_count

def start_solving(self):
attempt = 1
while True:
print(f"\n================ Attempt {attempt} ================")
state, h, steps = self.hill_climb()
if h == 0:
self.display_state(state)
print(f"\n✅ Solution found in Attempt {attempt} after {steps} steps!")
print("Final state (row positions by column):", state)
break
else:
 print("🔄 Restarting with a new random state...")
attempt += 1

# Run
if __name__ == "__main__":
root = [Link]()
game = EightQueensHillClimb(root)
[Link]()

INPUT AND OUTPUT :

SOURCE CODE :
import tkinter as tk
from tkinter import messagebox
import math

# ----------- Tic Tac Toe AI -----------

class TicTacToe:
def __init__(self, n):
self.n = n
[Link] = [['' for _ in range(n)] for _ in range(n)]
[Link] = 'X'
[Link] = 'O'

def make_move(self, row, col, player):

if [Link][row][col] == '':
[Link][row][col] = player
return True
return False

def check_winner(self, board=None):

if board is None:
board = [Link]
n = self.n
# Rows and columns
for i in range(n):
if board[i][0] != '' and all(board[i][j] == board[i][0] for j in range(n)):
return board[i][0]
if board[0][i] != '' and all(board[j][i] == board[0][i] for j in range(n)):
return board[0][i]
# Diagonals
if board[0][0] != '' and all(board[i][i] == board[0][0] for i in range(n)):
return board[0][0]
if board[0][n-1] != '' and all(board[i][n-1-i] == board[0][n-1] for i in range(n)):
return board[0][n-1]
# Check tie
if all(board[i][j] != '' for i in range(n) for j in range(n)):
return 'Tie'
return None

# ----------- Minimax with Alpha-Beta -----------

def minimax(self, board, depth, is_max, alpha, beta):
winner = self.check_winner(board)
if winner == [Link]:
return 10 - depth
elif winner == [Link]:
return depth - 10
elif winner == 'Tie':
return 0
 if is_max: # AI's move (Maximizer)
best = -[Link]
for i in range(self.n):
for j in range(self.n):
if board[i][j] == '':
board[i][j] = [Link]
print(" " * depth*2 + f"Max: Trying ({i},{j}), α={alpha}, β={beta}")
val = [Link](board, depth+1, False, alpha, beta)
board[i][j] = ''
best = max(best, val)
alpha = max(alpha, best)
print(" " * depth*2 + f"Max updated best={best}, α={alpha}, β={beta}")
if beta <= alpha:
print(" " * depth*2 + f"Pruned at ({i},{j}) with α={alpha}, β={beta}")
break
return best
else: # Player's move (Minimizer)
best = [Link]
for i in range(self.n):
for j in range(self.n):
if board[i][j] == '':
board[i][j] = [Link]
print(" " * depth*2 + f"Min: Trying ({i},{j}), α={alpha}, β={beta}")
val = [Link](board, depth+1, True, alpha, beta)
board[i][j] = ''
best = min(best, val)
beta = min(beta, best)
print(" " * depth*2 + f"Min updated best={best}, α={alpha}, β={beta}")
if beta <= alpha:
print(" " * depth*2 + f"Pruned at ({i},{j}) with α={alpha}, β={beta}")
break
return best

def best_move(self):
best_val = -[Link]
move = None
for i in range(self.n):
for j in range(self.n):
if [Link][i][j] == '':
[Link][i][j] = [Link]
move_val = [Link]([Link], 0, False, -[Link], [Link])
[Link][i][j] = ''
if move_val > best_val:
best_val = move_val
move = (i, j)
return move

# ----------- GUI -----------

class TicTacToeGUI:
def __init__(self, root, n):
 [Link] = root
self.n = n
[Link] = TicTacToe(n)
[Link] = [[None for _ in range(n)] for _ in range(n)]
self.create_board()

def create_board(self):
for i in range(self.n):
for j in range(self.n):
b = [Link]([Link], text='', font=('Helvetica', 24), width=4, height=2,
command=lambda row=i, col=j: self.player_move(row, col))
[Link](row=i, column=j)
[Link][i][j] = b
reset_btn = [Link]([Link], text='Reset', font=('Helvetica', 14),
command=self.reset_board)
reset_btn.grid(row=self.n, column=0, columnspan=self.n, sticky='we')

def player_move(self, row, col):

if [Link].make_move(row, col, [Link]):
[Link][row][col].config(text=[Link])
winner = [Link].check_winner()
if winner:
self.end_game(winner)
return
# AI move
ai_move = [Link].best_move()
if ai_move:
ai_row, ai_col = ai_move
[Link].make_move(ai_row, ai_col, [Link])
[Link][ai_row][ai_col].config(text=[Link])
winner = [Link].check_winner()
if winner:
self.end_game(winner)
else:
[Link]("Invalid Move", "Cell already occupied!")

def end_game(self, winner):

if winner == 'Tie':
[Link]("Game Over", "It's a Tie!")
else:
[Link]("Game Over", f"{winner} wins!")
print(f"\nFinal Board:")
for row in [Link]:
print(row)

def reset_board(self):
[Link] = TicTacToe(self.n)
for i in range(self.n):
for j in range(self.n):
[Link][i][j].config(text='')
# ----------- Run Game -----------
if __name__ == "__main__":
n = int(input("Enter board size n (e.g., 3 for 3x3): "))
root = [Link]()
[Link](f"{n}x{n} Tic Tac Toe vs AI (Alpha-Beta)")
gui = TicTacToeGUI(root, n)
[Link]()

INPUT AND OUTPUT :

SOURCE CODE :
from itertools import permutations

def solve_cryptarithmetic(puzzle):
"""
Solve a cryptarithmetic puzzle like SEND + MORE = MONEY
"""
# Remove spaces
puzzle = [Link](" ", "")

# Split left and right side

if '=' not in puzzle or '+' not in puzzle:
print("Puzzle format must be like SEND + MORE = MONEY")
return

left, right = [Link]('=')

left_terms = [Link]('+')

# Extract unique letters

letters = set(''.join(left_terms) + right)
if len(letters) > 10:
print("Too many unique letters (>10), cannot assign digits")
return

letters = list(letters)
digits = range(10)

# Try all permutations of digits for the letters

for perm in permutations(digits, len(letters)):
mapping = dict(zip(letters, perm))

# Skip if first letter of any term or result is 0

if any(mapping[word[0]] == 0 for word in left_terms + [right]):
continue

# Compute numeric values

left_sum = sum(int(''.join(str(mapping[ch]) for ch in word)) for word in left_terms)
right_value = int(''.join(str(mapping[ch]) for ch in right))

if left_sum == right_value:
print("Solution found!")
print("Mapping:", mapping)
print(f"{' + '.join([''.join(str(mapping[ch]) for ch in word) for word in left_terms])} =
{right_value}")
return mapping

print("No solution found.")

# ----------- Example Usage -------------

if __name__ == "__main__":
print("Cryptarithmetic Solver")
puzzle = input("Enter puzzle (format: SEND + MORE = MONEY): ")
solve_cryptarithmetic(puzzle)

INPUT AND OUPUT :

SOURCE CODE:
import math
import time

# Tic Tac Toe Board

board = [" " for _ in range(9)]

# Track nodes visited

minimax_nodes = 0
alphabeta_nodes = 0

# Print board
def print_board():
for row in [board[i*3:(i+1)*3] for i in range(3)]:
print("| " + " | ".join(row) + " |")
print()

# Check winner
def check_winner(brd):
win_conditions = [
[0,1,2], [3,4,5], [6,7,8], # rows
[0,3,6], [1,4,7], [2,5,8], # cols
[0,4,8], [2,4,6] # diagonals
]
for cond in win_conditions:
if brd[cond[0]] == brd[cond[1]] == brd[cond[2]] and brd[cond[0]] != " ":
return brd[cond[0]]
if " " not in brd:
return "Tie"
return None

# ---------------- Minimax ---------------- #

def minimax(brd, depth, is_maximizing):
global minimax_nodes
minimax_nodes += 1
result = check_winner(brd)
if result == "O":
return 10 - depth
elif result == "X":
return depth - 10
elif result == "Tie":
return 0

if is_maximizing:
best_score = -[Link]
for i in range(9):
if brd[i] == " ":
brd[i] = "O"
score = minimax(brd, depth+1, False)
 brd[i] = " "
best_score = max(best_score, score)
return best_score
else:
best_score = [Link]
for i in range(9):
if brd[i] == " ":
brd[i] = "X"
score = minimax(brd, depth+1, True)
brd[i] = " "
best_score = min(best_score, score)
return best_score

def best_move_minimax():
global minimax_nodes
minimax_nodes = 0
best_score = -[Link]
move = None
start = [Link]()
for i in range(9):
if board[i] == " ":
board[i] = "O"
score = minimax(board, 0, False)
board[i] = " "
if score > best_score:
best_score = score
move = i
end = [Link]()
return move, best_score, (end-start), minimax_nodes

# ---------------- Alpha-Beta ---------------- #

def alpha_beta(brd, depth, alpha, beta, is_maximizing):
global alphabeta_nodes
alphabeta_nodes += 1
result = check_winner(brd)
if result == "O":
return 10 - depth
elif result == "X":
return depth - 10
elif result == "Tie":
return 0

if is_maximizing:
best_score = -[Link]
for i in range(9):
if brd[i] == " ":
brd[i] = "O"
score = alpha_beta(brd, depth+1, alpha, beta, False)
brd[i] = " "
best_score = max(best_score, score)
 alpha = max(alpha, score)
if beta <= alpha:
break
return best_score
else:
best_score = [Link]
for i in range(9):
if brd[i] == " ":
brd[i] = "X"
score = alpha_beta(brd, depth+1, alpha, beta, True)
brd[i] = " "
best_score = min(best_score, score)
beta = min(beta, score)
if beta <= alpha:
break
return best_score

def best_move_alphabeta():
global alphabeta_nodes
alphabeta_nodes = 0
best_score = -[Link]
move = None
start = [Link]()
for i in range(9):
if board[i] == " ":
board[i] = "O"
score = alpha_beta(board, 0, -[Link], [Link], False)
board[i] = " "
if score > best_score:
best_score = score
move = i
end = [Link]()
return move, best_score, (end-start), alphabeta_nodes

# ---------------- Play ---------------- #

def play_game():
print("Welcome to Tic Tac Toe! You are X, AI is O.")
print_board()

while True:
# Human move
move = int(input("Enter your move (1-9): ")) - 1
if board[move] != " ":
print("Invalid move, try again.")
continue
board[move] = "X"
print_board()
if check_winner(board):
break
 # AI move with Minimax
move_m, score_m, time_m, nodes_m = best_move_minimax()
# AI move with Alpha-Beta
move_ab, score_ab, time_ab, nodes_ab = best_move_alphabeta()

# Use Alpha-Beta move for AI

board[move_ab] = "O"

print(f"Minimax → Move: {move_m+1}, Score: {score_m}, Time: {time_m:.8f}s,

Nodes: {nodes_m}")
print(f"Alpha-Beta → Move: {move_ab+1}, Score: {score_ab}, Time: {time_ab:.8f}s,
Nodes: {nodes_ab}")
print_board()

if check_winner(board):
break

winner = check_winner(board)
if winner == "Tie":
print("It's a Tie!")
else:
print(winner, "wins!")

# Run
if __name__ == "__main__":
play_game()
INPUT AND OUTPUT :