Backtracking Algorithm
The backtracking algorithm is a powerful technique for solving problems by exhaustively searching through all possible solutions. It follows a depth-first search approach and tries out different choices at each step, backtracking when it reaches a dead end. With backtracking, we can efficiently solve combinatorial problems like the word search puzzle.
To illustrate how the backtracking algorithm works, let's consider an example of finding a word in a grid of letters. Given a grid and a word, we want to determine if the word exists in the grid by moving horizontally, vertically, or diagonally.
Let's take the word "BIT" and the grid below as an example:
1A B C
2F I N
3T O RWe can start searching for the first letter of the word and then explore the neighboring cells to find the next letter. If at any point, we can't find the next letter or reach a boundary of the grid, we backtrack to the previous letter and try a different path.
Here's an implementation of the backtracking algorithm in C++ to solve the word search problem:
1#include <iostream>
2using namespace std;
3
4// Function to check if the given word is present in the grid
5bool isWordExist(char grid[3][3], int row, int col, string word, int index, int n, int m) {
6 // If all the characters of the word are checked and are present in the grid
7 if (index == word.length()) {
8 return true;
9 }
10
11 // If we reach beyond the boundaries of the grid or the current character
12 // in the grid doesn't match the character in the word
13 if (row < 0 || row >= n || col < 0 || col >= m || grid[row][col] != word[index]) {
14 return false;
15 }
16
17 // Mark the current cell as visited
18 char temp = grid[row][col];
19 grid[row][col] = '#';
20
21 // Recur for all the adjacent cells
22 if (isWordExist(grid, row, col + 1, word, index + 1, n, m) ||
23 isWordExist(grid, row, col - 1, word, index + 1, n, m) ||
24 isWordExist(grid, row + 1, col, word, index + 1, n, m) ||
25 isWordExist(grid, row - 1, col, word, index + 1, n, m)) {
26 return true;
27 }
28
29 // Mark the cell as unvisited
30 grid[row][col] = temp;
31
32 return false;
33}
34
35int main() {
36 // Size of the grid
37 int n = 3;
38 int m = 3;
39
40 // The grid representing the word search puzzle
41 char grid[3][3] = {{'A', 'B', 'C'}, {'F', 'I', 'N'}, {'T', 'O', 'R'}};
42
43 // The word to search for
44 string word = "BIT";
45
46 // Starting index of the character in the word to search
47 int index = 0;
48
49 // Initialize a flag to check if the word exists in the grid
50 bool wordExists = false;
51
52 // Iterate over the grid
53 for (int i = 0; i < n; i++) {
54 for (int j = 0; j < m; j++) {
55 if (grid[i][j] == word[0]) {
56 // Check if the word exists in the grid
57 if (isWordExist(grid, i, j, word, index, n, m)) {
58 wordExists = true;
59 break;
60 }
61 }
62 }
63 if (wordExists) {
64 break;
65 }
66 }
67
68 // Print the result
69 if (wordExists) {
70 cout << "The word \"" << word << "\" exists in the grid." << endl;
71 } else {
72 cout << "The word \"" << word << "\" does not exist in the grid." << endl;
73 }
74
75 return 0;
76}In this implementation, we use recursion to explore all possible paths in the grid. The isWordExist function checks if the current cell matches the current character of the word. If it does, we mark the cell as visited (using the '#' symbol) and recursively check the neighboring cells. If at any point, the word is completely matched, we return true. Otherwise, we mark the cell as unvisited and continue exploring other paths.
The main function initializes the grid, word, and starting index for the character in the word. It iterates over the grid to find the first character of the word. If a match is found, the isWordExist function is called to check if the complete word exists in the grid. Finally, the result is printed based on the value of the wordExists flag.
The backtracking algorithm allows us to systematically explore all possible paths in the word search puzzle and efficiently determine if a word exists in the grid.
xxxxxxxxxx}using namespace std;// Function to check if the given word is present in the gridbool isWordExist(char grid[3][3], int row, int col, string word, int index, int n, int m) { // If all the characters of the word are checked and are present in the grid if (index == word.length()) { return true; } // If we reach beyond the boundaries of the grid or the current character // in the grid doesn't match the character in the word if (row < 0 || row >= n || col < 0 || col >= m || grid[row][col] != word[index]) { return false; } // Mark the current cell as visited char temp = grid[row][col]; grid[row][col] = '#'; // Recur for all the adjacent cells if (isWordExist(grid, row, col + 1, word, index + 1, n, m) || isWordExist(grid, row, col - 1, word, index + 1, n, m) || isWordExist(grid, row + 1, col, word, index + 1, n, m) || isWordExist(grid, row - 1, col, word, index + 1, n, m)) { return true; } // Mark the cell as unvisited