boggle_solver_script.py

import string
import random
from typing import Dict, Generator, Iterator, Tuple

def gen_n_dimensional_boggle_board(n: int) -> list:
    return [ [random.choice(string.ascii_lowercase) 
              for x in range(n)] for row in range(n)]


BOARD = gen_n_dimensional_boggle_board(4)

def load_words_prefixes() -> tuple:
    with open('/Users/jeff/Downloads/ten-hundred', 'r') as f:
        words = f.readlines()
        data = [word.strip().lower() for word in words]
        prefixes_1 = list(set([w[0] for w in data]))
        prefixes_2 = list(set([w[:2] for w in data]))
        prefixes_3 = list(set([w[:3] for w in data]))
        prefixes = prefixes_1 + prefixes_2 + prefixes_3
    return (data, prefixes)

words, prefixes = load_words_prefixes()
assert(words[-1] == 'yourself')


DIRECTIONS = {'up': (0, -1), 
              'down': (0, 1), 
              'left': (-1, 0), 
              'right': (1, 0),
              'left_up': (-1, -1),
              'left_down': (-1, 1),
              'right_up': (1, -1),
              'right_down': (1, 1)}

def get_valid_moves_from_position(_directions: dict, _board: list, _row: int, _col: int) -> Iterator[Tuple[int, int]]:
    """Takes a board, a dictionary of valid directions and a current position
       returns a list of tuples of valid moves to iterate over during the search algorithm
       valid means the move is on the board itself
    """
    _valid_moves = [] # type: list
    
    for _, coordinate in _directions.items():
        temp_row, temp_col = coordinate
        delta_row, delta_col = _row + temp_row, _col + temp_col
        if min(delta_row, delta_col) >= 0:
            if delta_row < len(_board) and delta_col < len(_board[0]):
                yield (delta_row, delta_col)

        
from_top_left = get_valid_moves_from_position(DIRECTIONS, BOARD, 0, 0)
from_lower_right = get_valid_moves_from_position(DIRECTIONS, BOARD, len(BOARD) - 1, len(BOARD) - 1)
from_one_one = get_valid_moves_from_position(DIRECTIONS, BOARD, 1, 1)

assert(list(from_top_left) == [(0, 1), (1, 0), (1, 1)])
assert(list(from_lower_right) == [(3, 2), (2, 3), (2, 2)])
assert(len(list(from_one_one)) == 8)

def recursive_call(board_object: list, word_list: list, prefix_list: list, current_word: str, 
                   current_row: int, current_col: int, used_tiles: set) -> list:
    found_words = []
    
    if current_word in word_list:
        found_words.append(current_word)
    
    if current_word in prefix_list:
        moves = get_valid_moves_from_position(DIRECTIONS, board_object, current_row, current_col)
        for next_row, next_col in moves:
            if (next_row, next_col) not in used_tiles:
                used_tiles.add((next_row, next_col))
                found_words = found_words + recursive_call(board_object, word_list, prefix_list, 
                                                          current_word + board_object[next_row][next_col], 
                                                           next_row, next_col, used_tiles)

                used_tiles.remove((next_row, next_col)) # The very sneaky part - each tile can revisit others
                # provided they start from a different current tile
            
    return found_words



def main(the_board):
    word_results = []
    for row_idx, row in enumerate(the_board):
        for col_idx, _ in enumerate(row):
            word_results = word_results +\
                recursive_call(the_board, words, prefixes, the_board[row_idx][col_idx], 
                            row_idx, col_idx, set([(row_idx, col_idx)]))
    print(set(word_results))
    print('_________________________')
    for row in the_board:
        print(" ".join(row))


if __name__ == '__main__':
    main(BOARD)