In an effort to get everyone familiar with Python, we will develop a simple game. Boggle is a word$-$finding game.

The goal is to find as many words as possible in an NxN grid of letters.

RULES

Words must use adjacent tiles, including diagonals.

Each word may not use a cube more than once.

Words must be at least $3$ letters long.

Warning: The $$Qu$$ tile counts as $2$ letters. There are no raw $$Q$$ tiles. The $$St$$ tile counts as $2$ letters. There are no raw $$S$$ tiles.

T W Y R

E N P H

G St Qu R

O N T A

Valid Words $($A Partial List$)$:

art ego gent get net new newt prat pry qua quart rat tar tarp ten went wet stont stqura

Invalid Words:

arty egg not

Your task is to implement a solver for the game. Given a valid grid of letters and an arbitrary dictionary of words, return a list of contained words.

Artificial RequirementS

Submit your solution in a single boggle solver.py file.

Do not import any libraries. Use only the standard built$-$in types.

Artificial Design Insights

Design your solution as a Python Class called Boggle

Your Boogle Class should contain the following data members:

Grid

Dictionary

solution

Your Boogle Class should contain the following getter and setter methods:

setGrid $(2$D array of Strings$)$

setDictionary$($array of words$)$

Boggle$($grid$,$ dictionary$)$: Constructor

getSolution : The function returns an array or found words.

Add any additional methods and data members as needed.

Please document your code with $$ Comments $$

Examples:

Input: grid $=[[$A$,$ B$],$

$[$C$,$ D$]],$

dictionary $=[$A$,$ B$,$ AC$,$ ACA, ACB, DE$]$

Output: $[$ACB$]$

Input: grid $=[[$A$,$ B$,$ C$,$ D$],$

$[$E$,$ F$,$ G$,$ H$],$

$[$I$,$ J$,$ K$,$ L$],$

$[$A$,$ B$,$ C$,$ D$]]$

dictionary $=[$ABEF$,$ AFJIEB, DGKD$,$ DGKA$]$

Output: $[$ABEF$,$ AFJIEB, DGKD$]$