0/1 Knapsack Problem C Code

The 0/1 Knapsack Problem can be effectively solved using backtracking. In this problem, given a set of items,
each with a weight and a value, you aim to maximize the value within a weight constraint by choosing items in
a binary way (either include or exclude each item).

Backtracking helps by exploring all possible combinations of included and excluded items, only pursuing
combinations that don’t exceed the weight constraint.

Here's the C code implementing the 0/1 Knapsack Problem using backtracking:

#include <stdio.h>

// Define maximum number of items

#define MAX_ITEMS 100

// Define the structure for items

typedef struct {
int weight;
int value;
} Item;

int max(int a, int b) {

return (a > b) ? a : b;
}

// Recursive backtracking function to find the maximum value

void knapsack(int i, int currentWeight, int currentValue, int *maxValue, int W, Item items[], int
n) {
// If reached the last item
if (i == n) {
if (currentValue > *maxValue)
*maxValue = currentValue;
return;
}

// Case 1: Exclude the current item

knapsack(i + 1, currentWeight, currentValue, maxValue, W, items, n);

// Case 2: Include the current item, if it doesn't exceed the max weight
if (currentWeight + items[i].weight <= W) {
knapsack(i + 1, currentWeight + items[i].weight, currentValue + items[i].value, maxValue,
W, items, n);
}
}

int main() {
int W, n;

// Input maximum weight capacity of knapsack

printf("Enter the maximum weight capacity of the knapsack: ");
scanf("%d", &W);

// Input number of items

printf("Enter the number of items: ");
scanf("%d", &n);

Item items[MAX_ITEMS];

// Input weights and values of items

for (int i = 0; i < n; i++) {
printf("Enter weight and value for item %d: ", i + 1);
scanf("%d %d", &items[i].weight, &items[i].value);
}

1/15
 int maxValue = 0;
knapsack(0, 0, 0, &maxValue, W, items, n);

printf("Maximum value that can be obtained: %d\n", maxValue);

return 0;
}

Explanation

1. Data Structure:
Each item is represented by a `struct Item` containing its `weight` and `value`.

2. Recursive Function (`knapsack`):

This function takes the current item index (`i`), the current weight and value, the maximum value
found so far, the capacity of the knapsack, and the list of items.
It checks whether including or excluding each item yields a higher value without exceeding the
weight constraint.

3. Base Case:
When `i == n` (end of the list), it updates the `maxValue` if the current value is greater.

4. Backtracking:
The function explores both including and excluding each item, backtracking if an inclusion causes
the knapsack's weight to exceed `W`.

This approach is not the most efficient, but it is useful for understanding all possible combinations.

Memory updated

Here’s an enhanced version of the 0/1 Knapsack Problem solution using backtracking with additional
functionalities:

1. Tracking Selected Items: Keeping track of which items are selected to achieve the maximum value.
2. User-Friendly Output: Displaying the final selected items with their weights and values.
3. Memoization: Adding an optimization step to reduce recomputation of the same subproblems.

Here's the improved C code:

#include <stdio.h>

// Define maximum number of items

#define MAX_ITEMS 100

// Define the structure for items

typedef struct {
int weight;
int value;
} Item;

int max(int a, int b) {

return (a > b) ? a : b;
}

// Memoization table to store already computed results

int memo[MAX_ITEMS][MAX_ITEMS];

2/15
// Track selected items
int selected[MAX_ITEMS] = {0};
int bestSelected[MAX_ITEMS] = {0};

// Recursive backtracking function to find the maximum value

void knapsack(int i, int currentWeight, int currentValue, int *maxValue, int W, Item items[], int
n) {
// If reached the last item
if (i == n) {
if (currentValue > *maxValue) {
*maxValue = currentValue;
// Update the best selection of items
for (int j = 0; j < n; j++) {
bestSelected[j] = selected[j];
}
}
return;
}

// Check if this subproblem has already been solved

if (memo[i][currentWeight] != -1 && memo[i][currentWeight] >= currentValue) {
return;
}

// Store the current value in the memo table

memo[i][currentWeight] = currentValue;

// Case 1: Exclude the current item

selected[i] = 0;
knapsack(i + 1, currentWeight, currentValue, maxValue, W, items, n);

// Case 2: Include the current item, if it doesn't exceed the max weight
if (currentWeight + items[i].weight <= W) {
selected[i] = 1;
knapsack(i + 1, currentWeight + items[i].weight, currentValue + items[i].value, maxValue,
W, items, n);
selected[i] = 0; // Backtrack
}
}

int main() {
int W, n;

// Input maximum weight capacity of knapsack

printf("Enter the maximum weight capacity of the knapsack: ");
scanf("%d", &W);

// Input number of items

printf("Enter the number of items: ");
scanf("%d", &n);

Item items[MAX_ITEMS];

// Input weights and values of items

for (int i = 0; i < n; i++) {
printf("Enter weight and value for item %d: ", i + 1);
scanf("%d %d", &items[i].weight, &items[i].value);
}

// Initialize memoization table with -1

for (int i = 0; i < MAX_ITEMS; i++) {
for (int j = 0; j < MAX_ITEMS; j++) {
memo[i][j] = -1;
}
}

int maxValue = 0;
knapsack(0, 0, 0, &maxValue, W, items, n);

printf("Maximum value that can be obtained: %d\n", maxValue);

// Display selected items for maximum value

printf("Selected items:\n");
for (int i = 0; i < n; i++) {
if (bestSelected[i]) {
printf("Item %d -> Weight: %d, Value: %d\n", i + 1, items[i].weight, items[i].value);
}
}

3/15
 return 0;
}

Enhancements Explained

1. Tracking Selected Items: The `selected` array records which items are included in each recursive call,
and `bestSelected` stores the final combination of items that gives the maximum value.

2. Memoization Table: The `memo` table stores computed results for specific `(i, currentWeight)` states,
ensuring that we do not recompute the same subproblems, making the solution more efficient.

3. Displaying Results: After finding the maximum value, the program prints out the selected items with
their weights and values, providing clarity on the solution.

These additions make the program more informative and efficient, especially for larger inputs.

The N-Queens Problem is a classic combinatorial problem that places N queens on an N × N chessboard
such that no two queens threaten each other. In other words, no two queens share the same row, column, or
diagonal.

Here’s the full C code using backtracking to solve the N-Queens Problem:

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 20

int board[MAX_N][MAX_N]; // Chessboard to place queens

int N; // Size of the board (N x N)

// Function to print the board

void printBoard() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
printf("%c ", board[i][j] ? 'Q' : '.');
}
printf("\n");
}
printf("\n");
}

// Function to check if it's safe to place a queen at board[row][col]

int isSafe(int row, int col) {
// Check this row on left side
for (int i = 0; i < col; i++) {
if (board[row][i]) return 0;
}

// Check upper diagonal on left side

for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (board[i][j]) return 0;
}

// Check lower diagonal on left side

for (int i = row, j = col; j >= 0 && i < N; i++, j--) {
if (board[i][j]) return 0;
}

return 1;
}

// Function to solve the N-Queens problem using backtracking

4/15
 int solveNQueens(int col) {
// If all queens are placed, return success
if (col >= N) {
printBoard();
return 1;
}

int res = 0; // Flag to track if any solution is found

// Try placing this queen in all rows one by one

for (int i = 0; i < N; i++) {
// Check if it's safe to place the queen at board[i][col]
if (isSafe(i, col)) {
// Place the queen
board[i][col] = 1;

// Recursively place the rest of the queens

res = solveNQueens(col + 1) || res;

// If placing queen at board[i][col] leads to a solution

// then the board is printed, and we backtrack
board[i][col] = 0; // Backtrack
}
}
return res;
}

int main() {
// Input the size of the board
printf("Enter the number of queens: ");
scanf("%d", &N);

if (N < 1 || N > MAX_N) {

printf("Please enter a value between 1 and %d\n", MAX_N);
return 1;
}

// Initialize the board

for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
board[i][j] = 0;
}
}

// Solve the N-Queens problem and display solutions

if (solveNQueens(0) == 0) {
printf("No solution exists for %d queens.\n", N);
}

return 0;
}

Explanation

1. Data Structures:
`board[N][N]`: Represents the chessboard. A value of `1` at `board[i][j]` indicates a queen is
placed there.
`N`: Stores the number of queens (and the board's size N × N ).

2. `isSafe` Function:
Checks if placing a queen at a given position `(row, col)` is safe by:
Ensuring no queen is placed on the same row.
Ensuring no queen is on the upper left diagonal.
Ensuring no queen is on the lower left diagonal.

3. `solveNQueens` Function:
Recursively tries to place queens column by column.
If all queens are placed (i.e., `col >= N`), it prints the board as a solution.

5/15
 The function backtracks if placing a queen in a particular row and column does not lead to a
solution.

4. Main Function:
Takes input for `N` and initializes the board.
Calls `solveNQueens` to solve the problem and print all solutions.
If no solution is found, it displays a message.

Sample Output

For `N = 4`, the program outputs solutions like:

css

Q . . .
. . Q .
. . . Q
. Q . .

. Q . .
. . . Q
Q . . .
. . Q .

This approach demonstrates all possible solutions for the N-Queens problem by backtracking.

The Subset Sum Problem involves finding a subset of a set S of integers that adds up to a given sum K .
Using backtracking, we can explore all possible subsets of S and stop as soon as we find one that matches the
sum.

Here's the C code to solve the Subset Sum Problem using backtracking:

#include <stdio.h>

#define MAX_SIZE 100

// Function to print a subset that adds up to the target sum

void printSubset(int subset[], int size) {
printf("{ ");
for (int i = 0; i < size; i++) {
printf("%d ", subset[i]);
}
printf("}\n");
}

// Recursive backtracking function to find the subset sum

int subsetSum(int arr[], int subset[], int n, int targetSum, int subsetSize, int currentIndex) {
// If the target sum is reached, print the subset
if (targetSum == 0) {
printSubset(subset, subsetSize);
return 1;
}

// If we've reached the end of the array or targetSum is negative, stop

if (currentIndex == n || targetSum < 0) {
return 0;
}

// Include the current element in the subset and recurse

subset[subsetSize] = arr[currentIndex];

6/15
 int withCurrent = subsetSum(arr, subset, n, targetSum - arr[currentIndex], subsetSize + 1, cur
rentIndex + 1);

// Exclude the current element from the subset and recurse

int withoutCurrent = subsetSum(arr, subset, n, targetSum, subsetSize, currentIndex + 1);

// Return 1 if at least one solution exists

return withCurrent || withoutCurrent;
}

int main() {
int n, K;
int arr[MAX_SIZE];
int subset[MAX_SIZE]; // Array to store the subset

// Input number of elements in the set

printf("Enter the number of elements in the set: ");
scanf("%d", &n);

// Input the elements of the set

printf("Enter the elements of the set:\n");
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}

// Input the target sum

printf("Enter the target sum (K): ");
scanf("%d", &K);

printf("Subsets of S that sum to %d are:\n", K);

if (!subsetSum(arr, subset, n, K, 0, 0)) {
printf("No subset found with the sum %d\n", K);
}

return 0;
}

Explanation

1. Data Structures:
`arr`:Holds the input set of integers.
`subset`: Temporarily stores elements of the subset that are being tested.

2. Recursive Function `subsetSum`:

Parameters: It takes the set `arr`, the subset being built, the number of elements `n`, the
`targetSum`, the current size of the subset, and the current index in `arr`.
Base Cases:
If `targetSum == 0`: A valid subset with the required sum is found, and it prints the subset.
If `currentIndex == n` or `targetSum < 0`: The recursion terminates because no valid subset
can be formed.
Recursive Steps:
Include the Current Element: The current element at `currentIndex` is added to the subset,
and we call `subsetSum` with the updated `targetSum` and the next index.
Exclude the Current Element: The function is called without including the current element.

3. Main Function:
Takes user input for the set and the target sum K .
Calls `subsetSum` to find and display all subsets that sum to K .
If no subset is found, it prints a message indicating so.

Sample Output

For example, if the set S = {3, 34, 4, 12, 5, 2} and K = 9, the output may look like:

7/15
 mathematica

Enter the number of elements in the set: 6

Enter the elements of the set:
3 34 4 12 5 2
Enter the target sum (K): 9
Subsets of S that sum to 9 are:
{ 4 5 }
{ 3 4 2 }

This code finds and displays all subsets of S whose sum is equal to K , or indicates if no subset exists.

The Graph Coloring Problem is to assign colors to the vertices of a graph G such that no two adjacent
vertices have the same color, using at most m colors. Using backtracking, we can try to color each vertex with
different colors and backtrack if the constraints are violated.

Here’s the C code to solve the Graph Coloring Problem using backtracking:

#include <stdio.h>
#include <stdbool.h>

#define MAX_VERTICES 20

int graph[MAX_VERTICES][MAX_VERTICES]; // Adjacency matrix to represent the graph

int color[MAX_VERTICES]; // Array to store the color of each vertex
int V; // Number of vertices

// Function to check if it's safe to color vertex v with color c

bool isSafe(int v, int c) {
for (int i = 0; i < V; i++) {
// Check if vertex v has an edge with vertex i and vertex i has the same color
if (graph[v][i] && color[i] == c) {
return false;
}
}
return true;
}

// Recursive function to solve the graph coloring problem

bool graphColoringUtil(int m, int v) {
// If all vertices are assigned a color, return success
if (v == V) {
return true;
}

// Try different colors for vertex v

for (int c = 1; c <= m; c++) {
// Check if assigning color c to vertex v is safe
if (isSafe(v, c)) {
color[v] = c; // Assign color c to vertex v

// Recursively assign colors to the rest of the vertices

if (graphColoringUtil(m, v + 1)) {
return true;
}

// If assigning color c doesn't lead to a solution, backtrack

color[v] = 0;
}
}
// If no color can be assigned, return false
return false;
}

// Function to solve the graph coloring problem using m colors

8/15
 bool graphColoring(int m) {
// Initialize all colors as 0 (no color)
for (int i = 0; i < V; i++) {
color[i] = 0;
}

// Start from the first vertex and call the utility function
if (graphColoringUtil(m, 0)) {
printf("Solution exists with %d colors:\n", m);
for (int i = 0; i < V; i++) {
printf("Vertex %d -> Color %d\n", i + 1, color[i]);
}
return true;
} else {
printf("No solution exists with %d colors.\n", m);
return false;
}
}

int main() {
int m;

// Input the number of vertices

printf("Enter the number of vertices: ");
scanf("%d", &V);

// Input the adjacency matrix of the graph

printf("Enter the adjacency matrix:\n");
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
scanf("%d", &graph[i][j]);
}
}

// Input the number of colors

printf("Enter the number of colors: ");
scanf("%d", &m);

// Solve the graph coloring problem

graphColoring(m);

return 0;
}

Explanation

1. Data Structures:
`graph[V][V]`: Represents the adjacency matrix of the graph. If `graph[i][j] = 1`, there is an edge
between vertex `i` and vertex `j`.
`color[V]`: Stores the color assigned to each vertex.

2. `isSafe` Function:
Checks if assigning a particular color `c` to vertex `v` is safe by ensuring no adjacent vertex has the
same color.

3. `graphColoringUtil` Function:
A recursive function that tries to color each vertex starting from vertex `v`.
It attempts to assign each color from 1 to `m` to the current vertex and recursively tries to color the
rest of the graph.
If a color assignment doesn’t lead to a solution, it backtracks by resetting the color of the current
vertex.

4. `graphColoring` Function:
Initializes all vertices to no color (`0`) and starts the coloring process from the first vertex.
If a solution is found, it prints the color of each vertex; otherwise, it reports that no solution exists.

9/15
 5. Main Function:
Reads the number of vertices, the adjacency matrix, and the number of colors m.
Calls `graphColoring` to solve the problem.

Sample Output

For example, if you have a graph with 4 vertices and input an adjacency matrix like this:

0 1 1 1
1 0 1 0
1 1 0 1
1 0 1 0

And you provide m = 3 colors, the program may output:

rust

Solution exists with 3 colors:

Vertex 1 -> Color 1
Vertex 2 -> Color 2
Vertex 3 -> Color 3
Vertex 4 -> Color 2

This solution assigns colors such that no two adjacent vertices share the same color.

The Maze Traversal Problem involves finding a path from a start point to an end point in a maze represented
by a 2D array of 0s and 1s. Here, `1` represents a traversable path, and `0` represents a wall. Using
backtracking, we can explore different paths and backtrack if a path leads to a dead-end.

Here’s the C code to solve the maze traversal problem using backtracking:

#include <stdio.h>
#include <stdbool.h>

#define MAX_SIZE 100

// Directions for moving: right, down, left, up

int rowDir[] = {0, 1, 0, -1};
int colDir[] = {1, 0, -1, 0};

// Maze and visited matrix

int maze[MAX_SIZE][MAX_SIZE];
bool visited[MAX_SIZE][MAX_SIZE];
int solution[MAX_SIZE][MAX_SIZE];
int rows, cols; // Dimensions of the maze

// Function to print the solution path

void printSolution() {
printf("Path found:\n");
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
printf("%d ", solution[i][j]);
}
printf("\n");
}
printf("\n");

10/15
 }

// Function to check if the cell is within the maze and valid to move to
bool isValid(int x, int y) {
return (x >= 0 && x < rows && y >= 0 && y < cols && maze[x][y] == 1 && !visited[x][y]);
}

// Recursive backtracking function to find the path in the maze

bool solveMaze(int x, int y, int endX, int endY) {
// If the end point is reached, mark and return true
if (x == endX && y == endY) {
solution[x][y] = 1;
return true;
}

// Check if it's safe to move to cell (x, y)

if (isValid(x, y)) {
// Mark current cell as part of the path
visited[x][y] = true;
solution[x][y] = 1;

// Explore in all four directions

for (int i = 0; i < 4; i++) {
int newX = x + rowDir[i];
int newY = y + colDir[i];
if (solveMaze(newX, newY, endX, endY)) {
return true;
}
}

// If no path found, backtrack: unmark this cell

visited[x][y] = false;
solution[x][y] = 0;
}

return false;
}

int main() {
int startX, startY, endX, endY;

// Input the dimensions of the maze

printf("Enter the number of rows and columns in the maze: ");
scanf("%d %d", &rows, &cols);

// Input the maze matrix

printf("Enter the maze matrix (0 for wall, 1 for path):\n");
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
scanf("%d", &maze[i][j]);
visited[i][j] = false;
solution[i][j] = 0;
}
}

// Input the starting and ending points

printf("Enter the start coordinates (x y): ");
scanf("%d %d", &startX, &startY);
printf("Enter the end coordinates (x y): ");
scanf("%d %d", &endX, &endY);

// Solve the maze

if (solveMaze(startX, startY, endX, endY)) {
printSolution();
} else {
printf("No path found from (%d, %d) to (%d, %d)\n", startX, startY, endX, endY);
}

return 0;
}

Explanation

1. Data Structures:
`maze`: Represents the input maze matrix where `1` is a path and `0` is a wall.

11/15
 `visited`:Keeps track of visited cells to avoid cycles.
`solution`: Records the path found from start to end; cells on the path are marked with `1`.

2. `isValid` Function:
Checks if the cell `(x, y)` is within bounds, is a path (`maze[x][y] == 1`), and hasn’t been visited.

3. `solveMaze` Recursive Function:

The function tries to reach the end point `(endX, endY)` from the current cell `(x, y)` by moving in
the four possible directions: right, down, left, and up.
Base Case: If `(x, y)` is the end point, it sets `solution[x][y]` to `1` and returns `true`.
Recursive Steps:
Marks `(x, y)` as part of the solution path and sets it as visited.
Recursively explores each direction.
If no solution is found in any direction, it backtracks by marking `(x, y)` as unvisited and
removing it from the solution path.

4. Main Function:
Takes the maze dimensions, the maze matrix, start coordinates, and end coordinates as input.
Calls `solveMaze` and prints the solution if a path is found, or reports if no path exists.

Sample Output

For example, with a 5x5 maze input like this:

1 0 1 1 1
1 1 1 0 1
0 1 0 1 1
1 0 0 1 0
1 1 1 1 1

Starting at `(0, 0)` and ending at `(4, 4)`, the program may output:

mathematica

Path found:
1 0 0 0 0
1 1 1 0 0
0 0 0 1 1
0 0 0 1 0
0 0 0 1 1

Each `1` in `solution` represents a cell in the path from the start to the end. If no path exists, it outputs a
message stating so.

The Word Search Problem involves finding words in a grid of letters. Using backtracking, we can search for
words starting from each cell, moving in any of the 8 possible directions (up, down, left, right, and the 4
diagonals). If a valid word is found in the dictionary, it’s recorded.

Here’s the C code to solve the Word Search Problem with backtracking:

12/15
c

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define MAX_SIZE 20
#define MAX_WORD_LEN 20
#define DICT_SIZE 10

// Directions for moving in all 8 possible directions

int rowDir[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int colDir[] = {-1, 0, 1, 1, 1, 0, -1, -1};

char grid[MAX_SIZE][MAX_SIZE];
bool visited[MAX_SIZE][MAX_SIZE];
int rows, cols;
int minWordLen; // Minimum length of a word to search for
char dictionary[DICT_SIZE][MAX_WORD_LEN]; // Dictionary of valid words

// Function to check if a cell is within bounds and not visited

bool isValid(int x, int y) {
return (x >= 0 && x < rows && y >= 0 && y < cols && !visited[x][y]);
}

// Function to check if a word is in the dictionary

bool isInDictionary(char *word) {
for (int i = 0; i < DICT_SIZE; i++) {
if (strcmp(dictionary[i], word) == 0) {
return true;
}
}
return false;
}

// Recursive backtracking function to find words starting from (x, y)

void searchWord(int x, int y, char *currentWord, int index) {
// Mark the current cell as visited and add its letter to the word
visited[x][y] = true;
currentWord[index] = grid[x][y];
currentWord[index + 1] = '\0';

// Check if the current word is in the dictionary and meets the min length
if (index + 1 >= minWordLen && isInDictionary(currentWord)) {
printf("Found word: %s\n", currentWord);
}

// Explore in all 8 directions

for (int dir = 0; dir < 8; dir++) {
int newX = x + rowDir[dir];
int newY = y + colDir[dir];

if (isValid(newX, newY)) {
searchWord(newX, newY, currentWord, index + 1);
}
}

// Backtrack by unmarking the cell as visited

visited[x][y] = false;
currentWord[index] = '\0';
}

void findWordsInGrid() {
char currentWord[MAX_WORD_LEN];

// Initialize visited array to false

memset(visited, 0, sizeof(visited));

// Start search from each cell in the grid

for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
searchWord(i, j, currentWord, 0);
}
}
}

int main() {
// Input the dimensions of the grid

13/15
 printf("Enter the number of rows and columns of the grid: ");
scanf("%d %d", &rows, &cols);

// Input the grid of letters

printf("Enter the grid of letters:\n");
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
scanf(" %c", &grid[i][j]);
}
}

// Input minimum length of words to search

printf("Enter the minimum length of words to find: ");
scanf("%d", &minWordLen);

// Input the dictionary

printf("Enter the number of words in the dictionary (max %d): ", DICT_SIZE);
int dictSize;
scanf("%d", &dictSize);
printf("Enter the dictionary words:\n");
for (int i = 0; i < dictSize; i++) {
scanf("%s", dictionary[i]);
}

// Find words in the grid

printf("Words found in the grid:\n");
findWordsInGrid();

return 0;
}

Explanation

1. Data Structures:
`grid`:Holds the grid of letters.
`visited`: Tracks which cells have been visited during the current search.
`dictionary`: Holds the list of valid words.
`currentWord`: Stores the word being constructed during a search.

2. `isValid` Function:
Ensures the cell `(x, y)` is within bounds and hasn’t been visited.

3. `isInDictionary` Function:
Checks if a constructed word exists in the dictionary.

4. `searchWord` Recursive Function:

Parameters: Takes coordinates `(x, y)`, the current word being constructed, and its length.
Base Case: When the constructed word is of sufficient length and is in the dictionary, it is printed.
Recursive Steps:
Marks `(x, y)` as visited and appends `grid[x][y]` to `currentWord`.
Recursively calls `searchWord` for each direction.
Backtracks by unmarking the cell and removing the last character from `currentWord`.

5. Main Function:
Takes the grid, dictionary, and minimum word length as input.
Calls `findWordsInGrid` to find and print all valid words in the grid.

Sample Output

With a 4x4 grid:

14/15
 mathematica

A B C D
E F G H
I J K L
M N O P

And a dictionary containing `{"ABCF", "FGL", "JOK", "GHO"}`, if the minimum word length is 3, the program
might output:

yaml

Words found in the grid:

Found word: ABCF
Found word: FGL

This solution finds and prints all words from the dictionary that meet the length requirement and can be
formed by traversing neighboring cells in the grid.

Printed using Save ChatGPT as PDF, powered by PDFCrowd HTML to PDF API. 15/15