Word Search Solver: Implementing
Certainly! Here's a step-by-step algorithm for the word search
program using backtracking in Python:
1. is_valid_move**
- Input: `board` (2D list of characters), `row` (current row),
`col` (current column), `visited` (2D list indicating visited
positions)
- Output: Boolean (True if the move is valid, False otherwise)
- Checks if the move is within the board boundaries and the
position has not been visited.
2. search_word**
- Input: `board` (2D list of characters), `word` (the word to
search), `row` (current row), `col` (current column), `visited`
(2D list indicating visited positions)
- Output: Boolean (True if the word is found, False otherwise)
- Base case: If the word is empty, return True (word found).
- Check if the current position is a valid move and the
current character matches the first character of the word.
- Mark the current position as visited.
- Explore in all four directions (up, down, left, right)
recursively, checking if the remaining characters match.
- Backtrack by marking the current position as not visited
before returning.
3. word_search
- Input: `board` (2D list of characters), `word` (the word to
search)
- Output: Boolean (True if the word is found, False otherwise)
- Create a 2D list `visited` to track visited positions.
- Iterate through each position on the board.
- Call `search_word` for each position to check if the word
can be found starting from that position.
4. **Example usage**
- Define a 2D list `grid` representing the board.
- Create a list `words_to_search` containing the words to
search.
- Iterate through each word and print whether it is found or
not using the `word_search` function.
This algorithm outlines the structure of the provided Python
code and describes the purpose of each function. You can use
this as a guide to understand the flow of the program.
FlowChart:
Coding:
def is_valid_move(board, row, col, visited):
rows, cols = len(board), len(board[0])
return 0 <= row < rows and 0 <= col < cols and not visited[row][col]
def search_word(board, word, row, col, visited):
if not word:
return True
if is_valid_move(board, row, col, visited) and board[row][col] == word[0]:
visited[row][col] = True
# Explore in all four directions
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
for dr, dc in directions:
new_row, new_col = row + dr, col + dc
if search_word(board, word[1:], new_row, new_col, visited):
return True
visited[row][col] = False
return False
def word_search(board, word):
rows, cols = len(board), len(board[0])
visited = [[False] * cols for _ in range(rows)]
for i in range(rows):
for j in range(cols):
if search_word(board, word, i, j, visited):
return True
return False
# Example usage:
grid = [
['A', 'B', 'C', 'E'],
['S', 'F', 'C', 'S'],
['A', 'D', 'E', 'E']
]
words_to_search = ['ABCCED', 'SEE', 'ABCB']
for word in words_to_search:
if word_search(grid, word):
print(f'Found: {word}')
else:
print(f'Not found: {word}')
output:
Found: ABCCED
Found: SEE
Not found: ABCB
