`Boggle is a word game in which letters are randomly placed in a 4x4 grid e.g:
A D Q P
N L E M
O S R T
V K J H
Words can be started from any letter and are formed by finding a sequence of connecting letters. Letters may connect diagonally, vertically or horizontally.
Example words on the above board are "son", lad" and "land". Letters may not be re-used.
Below is a recursive solution to the boggle board. The problem with my solution is it is very slow. I had to limit word length to 8 otherwise it takes far too long.
Please can you comment on general style improvements and if you can think of another method to solve this game, a hint as to what I should do for my next attempt.
The dictionary is from here
"""Boggle game solver"""
import copy
def words_from(board, row, column, running_string="", list_words=[]):
"""Calculate all possible words from a given starting position [row, column]"""
if row in (4, -1) or column in (4, -1):
return
if len(running_string) > 4:
return
if board[row][column] != "-":
new_string = running_string + board[row][column]
new_board = copy.deepcopy(board)
new_board[row][column] = "-"
# Add new word
if len(new_string) >= 3:
list_words.append(new_string.lower())
# Find next word
next_move = [
(1, 1),
(-1, -1),
(1, -1),
(-1, 1),
(1, 0),
(0, 1),
(-1, 0),
(0, -1),
]
for dx, dy in next_move:
words_from(new_board, row + dx, column + dy, new_string, list_words)
return list_words
def get_permutations(board):
"""Get all permutations """
set_permutations = set()
counter = 0
print("Working..", end = "")
for row in range(4):
for column in range(4):
print(".", end="")
counter += 1
words = words_from(board, row, column, list_words=[])
if words:
for word in words:
set_permutations.add(word)
words = None
return sorted(list(set_permutations))
def dictionary_check(set_permuations):
"""Check set_permutations for valid English words"""
dictionary = {}
with open("en-dict.txt", "r", encoding="utf8") as file:
for line in file:
dictionary[line.strip()] = 0
counter = 0
for word in set_permuations:
if word.lower() in dictionary:
counter += 1
print(word)
print(f"======\n{counter} words")
def find_words(board):
"""Find words on the boggle board"""
set_permutations = get_permutations(board)
print("Performing dictionary check....")
dictionary_check(set_permutations)
def build_board(string):
"""Build board from string"""
if len(string) != 16:
print("Error. Must enter 4*4 grid (16 characters)")
return
board = [[*string[0:4]], [*string[4:8]], [*string[8:12]], [*string[12:16]]]
find_words(board)
if __name__ == "__main__":
string_board = "playthiswordgame"
build_board(string_board)
