Boggled Solver (Trie + DFS Backtracking)

A Python solver for a modified Boggle-style word search game. This implementation uses a custom Trie and DFS/backtracking to efficiently enumerate valid words on a board under additional constraints (suffix requirement, multi-letter tiles, and limited tile reuse).

Note: Completed as part of a coursework project. The code shown here was implemented by me and is included in my portfolio.

---

Features

• Custom Trie-based dictionary indexing
  • Built using reversed words to support efficient suffix filtering
• DFS search across the board in 8 directions (including diagonals)
• Supports multi-letter tiles (e.g., "qu")
• Allows configurable max uses per tile
• Uses Trie-based pruning to cut off invalid paths early

---

Key Components

• Trie / TrieNode
  • Builds a reverse Trie from a dictionary file
  • Validates whether a formed string is a valid suffix-matching word
• Boggled
  • setup_board(max_uses_per_tile, board)
  • get_all_words(suffix) → returns a set of valid words
  • Recursive DFS helper with backtracking + usage tracking

---

Concepts & Data Structures

• Tries (prefix trees, reverse indexing)
• DFS recursion + backtracking
• Constraint-based search + pruning
• Sets/maps for fast membership + deduplication

---

Author

Prisha Shah