==============================
PROGRAM: TOWER OF HANOI
==============================

AIM:
To solve the Tower of Hanoi problem using recursion.

DESCRIPTION:
The Tower of Hanoi is a classical recursive problem in Artificial Intelligence and Data Structures. It consists of three pegs (source, auxiliary, destination) and n disks of different sizes placed on the source peg. The objective is to move all disks from the source peg to the destination peg following these rules: only one disk can be moved at a time, a larger disk cannot be placed on top of a smaller disk, and only the top disk of a peg can be moved. The problem is solved using recursion. To move n disks: first move n-1 disks from source to auxiliary, then move the nth disk to destination, finally move n-1 disks from auxiliary to destination. The minimum number of moves required is 2^n - 1. Time Complexity is O(2^n).

PROGRAM:
n=int(input("Enter no. of disks:"))
def toh(n,S,A,D):
    if(n==1):
        print(f"Move disk 1 from {S} to {D}")
        return
    toh(n-1,S,D,A)
    print(f"Move disk {n} from {S} to {D}")
    toh(n-1,A,S,D)
toh(n,'S','A','D')

OUTPUT:
Enter no. of disks: 3
Move disk 1 from S to D
Move disk 2 from S to A
Move disk 1 from D to A
Move disk 3 from S to D
Move disk 1 from A to S
Move disk 2 from A to D
Move disk 1 from S to D

==============================
PROGRAM: VACUUM CLEANER PROBLEM
==============================

AIM:
To implement a simple reflex agent for a vacuum cleaner in a two-room environment.

DESCRIPTION:
The Vacuum Cleaner problem is a simple example of a reflex agent in Artificial Intelligence. The environment consists of two rooms (A and B) which may be in either Dirty (1) or Clean (0) state. The agent can perform two actions: SUCK to clean the current room, and MOVE to move to the other room. The agent senses the current room state. If the room is dirty, it cleans it. If the room is clean, it moves to the other room. This problem demonstrates simple reflex agent behavior, environment perception and action, and state-based decision making. The agent continues until both rooms are clean.

PROGRAM:
room_a = int(input("Enter state of Room A (1 = Dirty, 0 = Clean): "))
room_b = int(input("Enter state of Room B (1 = Dirty, 0 = Clean): "))
vacuum_location = input("Enter vacuum starting room (A or B): ").upper()

rooms = {
    "A": room_a,
    "B": room_b
} 

def vacuum_cleaner(rooms, location):
    print("\nInitial State:", rooms)
    print("Vacuum starts in Room", location)  
    print("-" * 35)

    while rooms["A"] == 1 or rooms["B"] == 1:
        if rooms[location] == 1:
            print(f"Room {location} is Dirty → Cleaning")
            rooms[location] = 0
        else:
            print(f"Room {location} is Clean")

        if location=='A':
            location='B'
        else:
            location='A'
        print(f"Moving to Room {location}")
        print("Current State:", rooms)
        print("-" * 35)

    print("All rooms are clean!")
    print("Final State:", rooms)

vacuum_cleaner(rooms, vacuum_location)

OUTPUT:
Enter state of Room A (1 = Dirty, 0 = Clean): 1
Enter state of Room B (1 = Dirty, 0 = Clean): 1
Enter vacuum starting room (A or B): A

Initial State: {'A': 1, 'B': 1}
Vacuum starts in Room A
-----------------------------------
Room A is Dirty → Cleaning
Moving to Room B
Current State: {'A': 0, 'B': 1}
-----------------------------------
Room B is Dirty → Cleaning
Moving to Room A
Current State: {'A': 0, 'B': 0}
-----------------------------------
All rooms are clean!
Final State: {'A': 0, 'B': 0}

==============================
PROGRAM: WATER JUG PROBLEM USING BFS
==============================

AIM:
To solve the water jug problem using Breadth First Search (BFS).

DESCRIPTION:
The Water Jug problem is a state-space search problem. Two jugs with fixed capacities are given, and the goal is to measure a specific quantity of water. The possible operations are: fill a jug, empty a jug, or pour water from one jug to another. The problem is solved using Breadth First Search (BFS). Each state is represented as (x, y) where x is the amount of water in jug1 and y is the amount in jug2. BFS explores all possible states level by level until the target amount is found. This guarantees finding the shortest solution path. Time Complexity is O(V + E) where V is number of states and E is number of transitions.

PROGRAM:
from collections import deque

def water_jug_bfs(jug1, jug2, goal):
    visited = set()
    queue = deque()

    start = (0, 0)
    queue.append((start, [start]))
    visited.add(start)

    while queue:
        (x, y), path = queue.popleft()

        if (x, y) == goal:
            print("\n Goal reached!")
            print("Steps:")
            for step in path:
                print(step)
            return True

        next_states = []
        next_states.append((jug1, y))
        next_states.append((x, jug2))
        next_states.append((0, y))
        next_states.append((x, 0))
        pour = min(x, jug2 - y)
        next_states.append((x - pour, y + pour))
        pour = min(y, jug1 - x)
        next_states.append((x + pour, y - pour))

        for state in next_states:
            if state not in visited:
                visited.add(state)
                queue.append((state, path + [state]))

    print("\n Goal not reachable")
    return False

jug1 = int(input("Enter capacity of Jug 1: "))
jug2 = int(input("Enter capacity of Jug 2: "))
goal_x = int(input("Enter goal amount in Jug 1: "))
goal_y = int(input("Enter goal amount in Jug 2: "))
goal = (goal_x, goal_y)

if goal_x > jug1 or goal_y > jug2:
    print("\n Goal exceeds jug capacity.")
else:
    water_jug_bfs(jug1, jug2, goal)

OUTPUT:
Enter capacity of Jug 1: 4
Enter capacity of Jug 2: 3
Enter goal amount in Jug 1: 2
Enter goal amount in Jug 2: 0

Goal reached!
Steps:
(0, 0)
(4, 0)
(1, 3)
(1, 0)
(0, 1)
(4, 1)
(2, 3)
(2, 0)

==============================
PROGRAM: RECURSIVE BFS
==============================

AIM:
To implement Breadth First Search (BFS) using recursion.

DESCRIPTION:
Recursive BFS simulates Breadth-First Search using recursion. BFS explores graph nodes level by level, using a queue (FIFO) to process nodes. In recursive BFS, the base case stops when the queue is empty. Each recursive call processes one node, enqueues its unvisited neighbors, then recurses. Recursive BFS is less common than iterative but demonstrates how recursion can simulate queue-based traversal. It maintains the same properties: O(V + E) time complexity and shortest path in unweighted graphs. This approach helps understand the relationship between recursion and iterative algorithms.

PROGRAM:
from collections import deque

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

def bfs_recursive_util(graph, queue, visited):
    if not queue:
        return
    node = queue.popleft()
    print(node, end=" ")
    for neighbor in graph[node]:
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append(neighbor)
    bfs_recursive_util(graph, queue, visited)

def bfs_recursive(graph, start):
    visited = set([start])
    queue = deque([start])
    bfs_recursive_util(graph, queue, visited)

print("Recursive BFS: ")
bfs_recursive(graph, 'A')

OUTPUT:
Recursive BFS: 
A B C D E F

==============================
PROGRAM: NON-RECURSIVE BFS
==============================

AIM:
To implement Breadth First Search (BFS) without recursion using a queue.

DESCRIPTION:
Non-recursive BFS uses an explicit queue to traverse the graph. Starting from the source node, it marks it visited and enqueues it. While the queue is not empty, it dequeues a node, processes it, and enqueues all unvisited neighbors. This iterative approach is standard because recursion depth can be problematic for large graphs. BFS guarantees finding the shortest path in unweighted graphs. Time complexity is O(V + E), space complexity is O(V) for the queue and visited set. This method is widely used in AI for state-space search and pathfinding.

PROGRAM:
from collections import deque

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

def bfs_non_recursive(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    while queue:
        node = queue.popleft()
        print(node, end=" ")
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

print("Non-Recursive BFS: ")
bfs_non_recursive(graph, 'A')

OUTPUT:
Non-Recursive BFS: 
A B C D E F

==============================
PROGRAM: RECURSIVE DFS
==============================

AIM:
To implement Depth First Search (DFS) using recursion.

DESCRIPTION:
Recursive DFS uses the system call stack to traverse the graph depth-first. Starting from the source, it marks the node visited, processes it, then recursively visits each unvisited neighbor. This algorithm explores as deep as possible before backtracking. It does not guarantee the shortest path but uses less memory than BFS in sparse graphs. Time complexity is O(V + E). Recursive DFS is elegant for problems like topological sorting or cycle detection. However, for large graphs, recursion depth may cause stack overflow, requiring iterative implementation.

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

def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()
    print(node, end=" ")
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

print("Recursive DFS: ")
dfs_recursive(graph, 'A')

OUTPUT:
Recursive DFS: 
A B D E F C

==============================
PROGRAM: NON-RECURSIVE DFS
==============================

AIM:
To implement Depth First Search (DFS) without recursion using a stack.

DESCRIPTION:
Non-recursive DFS uses an explicit stack (LIFO) instead of recursion. It starts by pushing the source node onto the stack. While the stack is not empty, it pops a node. If that node is unvisited, it marks it visited, processes it, and pushes all unvisited neighbors (often in reverse order to mimic recursion order). This approach avoids recursion limits and is more memory-efficient for deep graphs. Time complexity remains O(V + E). Iterative DFS is used in AI for solving mazes, puzzles, and exploring state spaces where recursion depth is unpredictable.

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

def dfs_non_recursive(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node not in visited:
            print(node, end=" ")
            visited.add(node)
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)

print("Non-Recursive DFS: ")
dfs_non_recursive(graph, 'A')

OUTPUT:
Non-Recursive DFS: 
A B D E F C

==============================
PROGRAM: A* SEARCH ALGORITHM
==============================

AIM:
To find the shortest path from start to goal using the A* search algorithm.

DESCRIPTION:
A* (A-star) is an informed search algorithm used in Artificial Intelligence. It finds the shortest path from a start node to a goal node using heuristics. It uses the evaluation function f(n) = g(n) + h(n), where g(n) is the actual cost from start to node n, h(n) is the heuristic estimated cost from node n to goal, and f(n) is the total estimated cost. A* selects the node with the lowest f(n) value. Properties: uses priority queue, guarantees optimal solution if heuristic is admissible, more efficient than uninformed search. A* is widely used in pathfinding and navigation systems.

PROGRAM:
import heapq

def a_star(graph, heuristic, start, goal):
    open_set = []
    heapq.heappush(open_set, (heuristic[start], start))
    g_cost = {start: 0}
    parent = {start: None}
    closed_set = set()

    while open_set:
        current_f, current = heapq.heappop(open_set)
        if current in closed_set:
            continue
        closed_set.add(current)
        if current == goal:
            path = []
            while current is not None:
                path.append(current)
                current = parent[current]
            return path[::-1]
        for neighbor, cost in graph[current]:
            if neighbor in closed_set:
                continue
            new_g = g_cost[current] + cost
            new_f = new_g + heuristic[neighbor]
            if neighbor not in g_cost or new_g < g_cost[neighbor]:
                g_cost[neighbor] = new_g
                parent[neighbor] = current
                heapq.heappush(open_set, (new_f, neighbor))
    return None

graph = {
    'S': [('A', 1), ('B', 4)],
    'A': [('B', 2), ('D', 12), ('C', 5)],
    'B': [('C', 2)],
    'C': [('D', 3)],
    'D': []
}
heuristic = {'S': 7, 'A': 6, 'B': 2, 'C': 1, 'D': 0}
start_node = 'S'
goal_node = 'D'
path = a_star(graph, heuristic, start_node, goal_node)
print("Path selected using A*:", path)

OUTPUT:
Path selected using A*: ['S', 'B', 'C', 'D']

==============================
PROGRAM: SIMPLE CALCULATOR
==============================

AIM:
To perform basic arithmetic operations using a simple calculator.

DESCRIPTION:
This program performs basic arithmetic operations such as addition, subtraction, multiplication, and division. It takes two numbers and an operator as input from the user, then computes and displays the result. For division, it includes a check to prevent division by zero. The program demonstrates user input handling, conditional statements (if-elif-else), and basic arithmetic operations. It is useful for beginners to understand control flow and how to handle different cases based on user input. The calculator covers addition (+), subtraction (-), multiplication (*), and division (/).

PROGRAM:
num1 = float(input("Enter first number: "))
num2 = float(input("Enter second number: "))
op = input("Enter operator (+, -, *, /): ")
if op == '+':
    print("Result =", num1 + num2)
elif op == '-':
    print("Result =", num1 - num2)
elif op == '*':
    print("Result =", num1 * num2)
elif op == '/':
    if num2 != 0:
        print("Result =", num1 / num2)
    else:
        print("Division by zero not allowed")
else:
    print("Invalid operator")

OUTPUT:
Enter first number: 10
Enter second number: 5
Enter operator (+, -, *, /): +
Result = 15.0

==============================
PROGRAM: CALENDAR DISPLAY
==============================

AIM:
To display the calendar of a given month and year.

DESCRIPTION:
This program displays a calendar for a given month and year using Python's built-in calendar module. The user inputs the year and month number (1-12), and the program uses the calendar.month() function to generate and print a formatted text calendar showing all days of the month with proper alignment. The calendar module provides various functions for working with dates, and month() specifically returns a multiline string representing the calendar. This program demonstrates module usage, user input handling, and formatted output in Python.

PROGRAM:
import calendar
year = int(input("Enter year: "))
month = int(input("Enter month (1-12): "))
cal = calendar.month(year, month)
print("\nCalendar:\n")
print(cal)

OUTPUT:
Enter year: 2025
Enter month (1-12): 4

Calendar:

     April 2025
Mo Tu We Th Fr Sa Su
    1  2  3  4  5  6
 7  8  9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30

==============================
PROGRAM: ODD MAGIC SQUARE
==============================

AIM:
To generate a magic square for odd-order matrices.

DESCRIPTION:
A magic square is an n x n grid filled with distinct numbers 1 to n² such that each row, column, and both main diagonals sum to the same value (magic constant = n(n²+1)/2). For odd n, the program uses the Siamese method: start at top-middle, move up-right, if cell is occupied move down instead. This algorithm works only for odd-sized squares (n = 3, 5, 7, ...). Magic squares have applications in mathematics, puzzles, and combinatorial design. The program prints the generated magic square row by row.

PROGRAM:
def odd_magic_square(n):
    magic = [[0]*n for _ in range(n)]
    i = 0
    j = n // 2
    for num in range(1, n*n + 1):
        magic[i][j] = num
        new_i = (i - 1) % n
        new_j = (j + 1) % n
        if magic[new_i][new_j]:
            i = (i + 1) % n
        else:
            i = new_i
            j = new_j
    for row in magic:
        print(row)

n = 3
odd_magic_square(n)

OUTPUT:
[8, 1, 6]
[3, 5, 7]
[4, 9, 2]

==============================
PROGRAM: EVEN MAGIC SQUARE
==============================

AIM:
To generate a magic square for even-order (doubly even) matrices.

DESCRIPTION:
A magic square is an n x n grid filled with distinct numbers 1 to n² such that each row, column, and both main diagonals sum to the same value. For doubly even squares (n divisible by 4), the program uses the Strachey method: fill sequentially, then complement cells in 4x4 subgrids where indices satisfy (i%4 == j%4) or (i%4 + j%4 == 3). This works for n = 4, 8, 12, etc. The magic constant is n(n²+1)/2. The program prints the generated magic square row by row.

PROGRAM:
def even_magic_square(n):
    magic = [[(i*n) + j + 1 for j in range(n)] for i in range(n)]
    for i in range(n):
        for j in range(n):
            if (i % 4 == j % 4) or ((i % 4 + j % 4) == 3):
                magic[i][j] = n*n + 1 - magic[i][j]
    for row in magic:
        print(row)

n = 4
even_magic_square(n)

OUTPUT:
[16, 2, 3, 13]
[5, 11, 10, 8]
[9, 7, 6, 12]
[4, 14, 15, 1]

==============================
PROGRAM: PERCEPTRON (LOGIC GATES - MCP NEURON)
==============================

AIM:
To implement AND, OR, and NOT logic gates using the MCP neuron model.

DESCRIPTION:
The McCulloch-Pitts (MCP) neuron is a simple mathematical model of a biological neuron. It computes the weighted sum of inputs, then applies a threshold activation function: output = 1 if weighted sum >= threshold, else 0. This program implements three logic gates using appropriate weights and thresholds. AND gate requires both inputs to be 1 (weights [1,1], threshold=2). OR gate outputs 1 if at least one input is 1 (threshold=1). NOT gate inverts the input (weight [-1], threshold=0). This demonstrates linear separability and forms the foundation of neural networks.

PROGRAM:
def mcp_neuron(inputs, weights, threshold):
    summation = 0
    for i in range(len(inputs)):
        summation += inputs[i] * weights[i]
    if summation >= threshold:
        return 1
    else:
        return 0

inputs = [(0,0), (0,1), (1,0), (1,1)]

print("AND GATE")
weights = [1, 1]
threshold = 2
for x in inputs:
    print(x, "->", mcp_neuron(list(x), weights, threshold))

print("\nOR GATE")
weights = [1, 1]
threshold = 1
for x in inputs:
    print(x, "->", mcp_neuron(list(x), weights, threshold))

print("\nNOT GATE")
weights = [-1]
threshold = 0
inputs_not = [0, 1]
for x in inputs_not:
    print(x, "->", mcp_neuron([x], weights, threshold))

OUTPUT:
AND GATE
(0, 0) -> 0
(0, 1) -> 0
(1, 0) -> 0
(1, 1) -> 1

OR GATE
(0, 0) -> 0
(0, 1) -> 1
(1, 0) -> 1
(1, 1) -> 1

NOT GATE
0 -> 1
1 -> 0

==============================
PROGRAM: POS TAGGING (NLTK)
==============================

AIM:
To perform Part-of-Speech (POS) tagging using NLTK.

DESCRIPTION:
Part-of-Speech tagging is the process of marking each word in a sentence with its grammatical category (noun, verb, adjective, etc.). This program uses NLTK's averaged_perceptron_tagger, which is a pre-trained model for POS tagging. The program first tokenizes the input sentence into words using word_tokenize (requires downloading the 'punkt' tokenizer model). Then it applies pos_tag() to assign tags to each token. POS tagging is fundamental for natural language processing tasks like sentiment analysis, information extraction, and syntactic parsing.

PROGRAM:
import nltk
from nltk.tokenize import word_tokenize

nltk.download('punkt')
nltk.download('averaged_perceptron_tagger')

sentence = "The quick brown fox jumps over the lazy dog."

tokens = word_tokenize(sentence)
tags = nltk.pos_tag(tokens)

print("Tokens:", tokens)
print("POS tags:", tags)

OUTPUT:
Tokens: ['The', 'quick', 'brown', 'fox', 'jumps', 'over', 'the', 'lazy', 'dog', '.']
POS tags: [('The', 'DT'), ('quick', 'JJ'), ('brown', 'JJ'), ('fox', 'NN'), ('jumps', 'VBZ'), ('over', 'IN'), ('the', 'DT'), ('lazy', 'JJ'), ('dog', 'NN'), ('.', '.')]

==============================
PROGRAM: PUNCTUATION REMOVAL
==============================

AIM:
To remove punctuation from tokenized text.

DESCRIPTION:
This program demonstrates text preprocessing by removing punctuation marks from a given sentence. It uses NLTK's word_tokenize to split the sentence into words including punctuation as separate tokens. Then it filters out non-alphanumeric tokens using the isalnum() method, which returns True only for alphanumeric characters. Removing punctuation is an important preprocessing step in natural language processing because punctuation marks generally do not carry semantic meaning. The program outputs both the original tokens (with punctuation) and the cleaned tokens (without punctuation).

PROGRAM:
import nltk
from nltk.tokenize import word_tokenize
import string

nltk.download('punkt')

sentence = "Hello world! This is an example sentence. Can you tokenize it?"

words = word_tokenize(sentence)

words_with_punct = words
words_without_punct = [word for word in words if word.isalnum()]

print("Words with punctuation:", words_with_punct)
print("Words without punctuation:", words_without_punct)

OUTPUT:
Words with punctuation: ['Hello', 'world', '!', 'This', 'is', 'an', 'example', 'sentence', '.', 'Can', 'you', 'tokenize', 'it', '?']
Words without punctuation: ['Hello', 'world', 'This', 'is', 'an', 'example', 'sentence', 'Can', 'you', 'tokenize', 'it']

==============================
PROGRAM: STOPWORD REMOVAL
==============================

AIM:
To remove stopwords from a given sentence using NLTK.

DESCRIPTION:
Stopwords are common words (like 'a', 'an', 'the', 'is', 'of', 'to') that often do not contribute significant meaning to text analysis. This program uses NLTK's corpus of English stopwords to filter out these words from an input sentence. The program tokenizes the input, converts each token to lowercase for case-insensitive comparison, and checks if it belongs to the stopwords set. Words that are not stopwords are retained. Stopword removal is a crucial preprocessing step in text classification, information retrieval, and search engines to reduce noise and improve efficiency.

PROGRAM:
import nltk
from nltk.corpus import stopwords
from nltk.tokenize import word_tokenize

nltk.download('punkt')
nltk.download('stopwords')

text = input("Enter a sentence: ")

words = word_tokenize(text)

stop_words = set(stopwords.words("english"))

filtered_words = []

for word in words:
    if word.lower() not in stop_words:
        filtered_words.append(word)

print("Original sentence:", text)
print("After removing stop words:", " ".join(filtered_words))

OUTPUT:
Enter a sentence: The quick brown fox jumps over the lazy dog
Original sentence: The quick brown fox jumps over the lazy dog
After removing stop words: quick brown fox jumps lazy dog

==============================
PROGRAM: TOKENIZATION & CORPUS ANALYSIS
==============================

AIM:
To perform sentence and word tokenization and analyze corpus statistics.

DESCRIPTION:
This program performs multiple levels of tokenization: sentence tokenization (splitting text into sentences), word tokenization (splitting into words and punctuation), and paragraph tokenization (splitting by newlines). It uses NLTK's sent_tokenize and word_tokenize functions, which are based on the Punkt tokenizer that handles abbreviations and complex sentence boundaries. The program also calculates total word count and distinct word count (vocabulary size) from the tokenized words. This is essential for corpus analysis, text statistics, and understanding lexical diversity in a text corpus.

PROGRAM:
import nltk
from nltk.tokenize import word_tokenize, sent_tokenize

nltk.download('punkt')

text = input("Enter a paragraph:\n")

sen = sent_tokenize(text)
print("\nSentences:")
print(sen)

words = word_tokenize(text)
print("\nWords:")
print(words)

para = text.split("\n")
print("\nParagraphs:")
print(para)

total_words = len(words)
print("\nTotal no. of words:", total_words)

dist_words = len(set(words))
print("\nNo. of distinct words:", dist_words)

OUTPUT:
Enter a paragraph:
Hello world. This is NLP. It is fun.

Sentences:
['Hello world.', 'This is NLP.', 'It is fun.']

Words:
['Hello', 'world', '.', 'This', 'is', 'NLP', '.', 'It', 'is', 'fun', '.']

Paragraphs:
['Hello world. This is NLP. It is fun.']

Total no. of words: 11

No. of distinct words: 8

==============================
PROGRAM: SUDOKU SOLVER
==============================

AIM:
To solve a 9x9 Sudoku puzzle using backtracking algorithm.

DESCRIPTION:
This program solves a standard 9x9 Sudoku puzzle using the backtracking algorithm. Empty cells are represented as 0. The algorithm works by finding an empty cell, trying numbers 1-9, checking if the number is safe to place (no conflict in row, column, or 3x3 subgrid), then recursively attempting to solve the rest. If a number leads to a solution, it returns True; otherwise, it backtracks by resetting the cell to 0 and trying the next number. Backtracking is a depth-first search technique commonly used for constraint satisfaction problems. The program prints the solved Sudoku grid.

PROGRAM:
def print_board(board):
    for row in board:
        print(row)

def is_safe(board, row, col, num):
    for i in range(9):
        if board[row][i] == num:
            return False
    for i in range(9):
        if board[i][col] == num:
            return False
    start_row = row - row % 3
    start_col = col - col % 3
    for i in range(3):
        for j in range(3):
            if board[start_row + i][start_col + j] == num:
                return False
    return True

def solve_sudoku(board):
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                for num in range(1, 10):
                    if is_safe(board, row, col, num):
                        board[row][col] = num
                        if solve_sudoku(board):
                            return True
                        board[row][col] = 0
                return False
    return True

board = [
    [5,3,0,0,7,0,0,0,0],
    [6,0,0,1,9,5,0,0,0],
    [0,9,8,0,0,0,0,6,0],
    [8,0,0,0,6,0,0,0,3],
    [4,0,0,8,0,3,0,0,1],
    [7,0,0,0,2,0,0,0,6],
    [0,6,0,0,0,0,2,8,0],
    [0,0,0,4,1,9,0,0,5],
    [0,0,0,0,8,0,0,7,9]
]

if solve_sudoku(board):
    print("Solved Sudoku:")
    print_board(board)
else:
    print("No solution exists")

OUTPUT:
Solved Sudoku:
[5, 3, 4, 6, 7, 8, 9, 1, 2]
[6, 7, 2, 1, 9, 5, 3, 4, 8]
[1, 9, 8, 3, 4, 2, 5, 6, 7]
[8, 5, 9, 7, 6, 1, 4, 2, 3]
[4, 2, 6, 8, 5, 3, 7, 9, 1]
[7, 1, 3, 9, 2, 4, 8, 5, 6]
[9, 6, 1, 5, 3, 7, 2, 8, 4]
[2, 8, 7, 4, 1, 9, 6, 3, 5]
[3, 4, 5, 2, 8, 6, 1, 7, 9]