Solving Boggle Using AI - Dynamic Programming + Trie in Python
Offered By: Yacine Mahdid via YouTube
Course Description
Overview
Learn to develop a classical AI algorithm for solving Boggle boards efficiently in this 36-minute tutorial. Explore data structures, graph theory, and dynamic programming as you build a solution that can tackle any Boggle board in under 10 seconds. Dive into key concepts such as tries for dictionary encoding, graph representation of Boggle boards, and recursive traversal techniques. Follow along with step-by-step demonstrations, from trie construction to graph creation and final algorithm implementation. Gain practical insights into optimizing search algorithms and applying computer science principles to solve real-world puzzles.
Syllabus
- Introduction:
- What is Boggle:
- Demonstration of Algorithm:
- Algorithm Planning:
- What the heck is a trie?:
- Dictionary encoded as a trie:
- Finding a dictionary:
- Building a trie dynamically:
- Demonstration of Trie Building:
- Boggle Solving:
- Boggle Board as a Graph:
- Adjacency Matrix for Boggle:
- Boggle Solving creating the graph:
- Demonstration of graph creation:
- Traversing the Boggle Graph:
- Movement for traversal cut and jump:
- Traversing the Boggle Graph recursion:
- Final Demonstration:
- Conclusion:
- ° ͜ʖ °:
Taught by
Yacine Mahdid
Related Courses
Algorithms: Design and Analysis, Part 2Stanford University via Coursera Discrete Optimization
University of Melbourne via Coursera Conception et mise en œuvre d'algorithmes.
École Polytechnique via Coursera Computability, Complexity & Algorithms
Georgia Institute of Technology via Udacity Discrete Inference and Learning in Artificial Vision
École Centrale Paris via Coursera