I have a game board which is a 2D array of letters – 6 x 8. The objective is to find a list of words with the length equal to X that complete the matrix without a letter being used twice. To create a word you can go up, down, left, right, and all diagonals. There is one word that going all the way from left to right, right to left, up to down, or down to up. This word describes the theme of the rest of the words.
My original solution was to use a backtracking algorithm to find all the possible words in the 2D matrix. From this, I would use another backtracking algorithm to find the combination of words that complete the matrix. I imagined each word being a puzzle piece that when put together it would complete the matrix with no overlaps. The list of possible words was much longer than I expected, averaging 1500 words. Since the list length is so long it causes the second backtracking algorithm to be 2^1500 which will never finish. So my first thought was I need to reduce the number of words in the possible words list. I tried to find a dictionary that had reduced words but I always ran into one that missed a word or two that were used to complete the matrix. Another solution I thought of was to use ChatGPT to analyze the theme and filter the list based off that. But GPT doesn’t perform well in this regard. If anyone has any suggestions or comments I am very open to anything.
Here is the code below:
run.py
from DictionaryAVLTree import dictionaryAVLTree, MINIMUM_WL, MAXIMUM_WL
WIDTH, HEIGHT = 6, 8
outputFile = open("strands_words.txt", "w")
# strandsArray = [[0 for x in range(w)] for y in range(h)]
strandsArray = [['e', 'w' ,'r', 'p', 'b', 'r'],
['n', 'e', 'u', 'b', 'o', 'w'],
['e', 'm', 'c', 'i', 'l', 's'],
['e', 'l', 'o', 'r', 'r', 'e'],
['t', 'd', 'i', 'w', 'o', 'b'],
['y', 'u', 'b', 'r', 'a', 'r'],
['r', 'e', 't', 'r', 'n', 'a'],
['a', 'd', 's', 'y', 'l', 'e']]
totalWords = 6
# strandsArray = [
# ['t', 'h', 'i', 's'],
# ['w', 'a', 't', 's'],
# ['o', 'a', 'h', 'g'],
# ['f', 'g', 'd', 't']
# ]
# Backtracking recursive function to find words in 2D Matrix
# @Params
def searchLetter(currentString, row, col, usedLettersSet, usedLettersArray, possibleWords):
# Check if the row and col is in bounds if its not then return false
if not isInBounds(row, col):
return
# if the string is too long then just return
if len(currentString) + 1 >= MAXIMUM_WL:
return
# 3 Possible conditions:
# 1. Got to end of tree
# 2. Found a sub string
# 3. Found a word
# If the word is less than the minimum then dont check and just process the next possible letter
if len(currentString) >= MINIMUM_WL:
searchResults = dictionaryAVLTree.search_value(currentString)
if searchResults['isSubString'] == False:
return
elif searchResults['isWord'] == True:
possibleWords.append(usedLettersArray.copy())
outputFile.write(currentString + 'n')
# all possible directions to check
directions = [(-1, 0), (0, 1), (1, 0), (0, -1), (-1, 1), (1, 1), (1, -1), (-1, -1)]
for direction in directions:
newRow, newCol = row + direction[0], col + direction[1]
searchNextLetter(currentString, newRow, newCol, usedLettersSet, usedLettersArray, possibleWords)
def searchNextLetter(currentString, row, col, usedLettersSet, usedLettersArray, possibleWords):
# Makes sure it is a valid element in the 2D matrix and also it hasnt been used yet
if isInBounds(row, col) and getId(row, col) not in usedLettersSet:
usedLettersSet.add(getId(row, col))
usedLettersArray.append(getId(row, col))
searchLetter(currentString + strandsArray[row][col], row, col, usedLettersSet, usedLettersArray, possibleWords)
usedLettersSet.remove(getId(row, col))
usedLettersArray.remove(getId(row, col))
# Backtracking recursive function to complete the 2D matrix with words
def completeMatrix(start, usedLettersSet, usedWords, completedMatrixWords, possibleWords, matrixArea, totalWords, currentTotalWords):
print(usedWords)
if len(usedLettersSet) == matrixArea:
completedMatrixWords.append(usedWords.copy())
return
if currentTotalWords >= totalWords:
return
if len(usedWords) >= totalWords:
return
if len(usedLettersSet) > matrixArea:
return
for index in range(start, len(possibleWords)):
# Check that non of the letters in this word are in the usedLettersSet
word = possibleWords[index]
if all(letter not in usedLettersSet for letter in word):
for letter in word:
usedLettersSet.add(letter)
usedWords.append(word)
if completeMatrix(index + 1, usedLettersSet, usedWords, completedMatrixWords, possibleWords, matrixArea, totalWords, currentTotalWords + 1):
return True # Early termination if one solution is sufficient
usedWords.pop()
for letter in word:
usedLettersSet.remove(letter)
# Helper Functions
def isInBounds(row, col):
if (row < 0 or row >= len(strandsArray)) or (col < 0 or col >= len(strandsArray[0])):
return False
return True
def getId(row, col):
return f"{row}#{col}"
# Main
def main():
# For loop to iterate through strandsArray. Each element we do the algorithm
possibleWords = []
for row in range(len(strandsArray)):
for col in range(len(strandsArray[0])):
searchLetter(strandsArray[row][col], row, col, {getId(row, col)}, [getId(row, col)], possibleWords)
completedMatrixWords = []
# completeMatrix(0, set(), [], completedMatrixWords, possibleWords, len(strandsArray) * len(strandsArray[0]), totalWords, 0)
# print(completedMatrixWords)
for word in possibleWords:
print(word)
main()
outputFile.close()
DictionaryAVLTree.py
from AVLTree import Node, AVLTree
import sys
# Constants
MINIMUM_WL = 4
MAXIMUM_WL = 15
# Function to simulate a dynamic print
def dynamic_print(text):
sys.stdout.write('r' + text)
sys.stdout.flush()
dictionaryAVLTree = AVLTree()
print("[Creating Dict AVL Tree]")
with open("words_alpha.txt", "r") as file:
counter = 0
for word in file:
currWord = word.strip()
if len(currWord) >= MINIMUM_WL and len(currWord) <= MAXIMUM_WL:
dictionaryAVLTree.insert_value(currWord)
counter += 1
dynamic_print(f"{counter} words added")
print()
print("[Finished Dict AVL Tree]")
AVLTree.py
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
self.height = 1
class AVLTree:
def __init__(self):
self.root = None
def height(self, node):
if not node:
return 0
return node.height
def balance(self, node):
if not node:
return 0
return self.height(node.left) - self.height(node.right)
def insert(self, root, value):
if not root:
return Node(value)
elif value < root.value:
root.left = self.insert(root.left, value)
else:
root.right = self.insert(root.right, value)
root.height = 1 + max(self.height(root.left), self.height(root.right))
balance = self.balance(root)
# Left rotation
if balance > 1 and value < root.left.value:
return self.right_rotate(root)
# Right rotation
if balance < -1 and value > root.right.value:
return self.left_rotate(root)
# Left-Right rotation
if balance > 1 and value > root.left.value:
root.left = self.left_rotate(root.left)
return self.right_rotate(root)
# Right-Left rotation
if balance < -1 and value < root.right.value:
root.right = self.right_rotate(root.right)
return self.left_rotate(root)
return root
def delete(self, root, value):
if not root:
return root
if value < root.value:
root.left = self.delete(root.left, value)
elif value > root.value:
root.right = self.delete(root.right, value)
else:
if not root.left:
temp = root.right
root = None
return temp
elif not root.right:
temp = root.left
root = None
return temp
temp = self.min_value_node(root.right)
root.value = temp.value
root.right = self.delete(root.right, temp.value)
if not root:
return root
root.height = 1 + max(self.height(root.left), self.height(root.right))
balance = self.balance(root)
# Left rotation
if balance > 1 and self.balance(root.left) >= 0:
return self.right_rotate(root)
# Right rotation
if balance < -1 and self.balance(root.right) <= 0:
return self.left_rotate(root)
# Left-Right rotation
if balance > 1 and self.balance(root.left) < 0:
root.left = self.left_rotate(root.left)
return self.right_rotate(root)
# Right-Left rotation
if balance < -1 and self.balance(root.right) > 0:
root.right = self.right_rotate(root.right)
return self.left_rotate(root)
return root
def left_rotate(self, z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
z.height = 1 + max(self.height(z.left), self.height(z.right))
y.height = 1 + max(self.height(y.left), self.height(y.right))
return y
def right_rotate(self, z):
y = z.left
T3 = y.right
y.right = z
z.left = T3
z.height = 1 + max(self.height(z.left), self.height(z.right))
y.height = 1 + max(self.height(y.left), self.height(y.right))
return y
def min_value_node(self, root):
current = root
while current.left:
current = current.left
return current
def search(self, root, value, output=None):
if not output:
output={'isWord':False, 'isSubString':False}
# We made it through the AVL and didnt find a word so we will just return
if not root:
return output
# Check to see if the value is a sub string of a word meaning there exists a possible combination we can find in the 2d matrix that includes this substring
if not output['isSubString'] and value == root.value[:len(value)]:
output['isSubString'] = True
# We found a word
if root.value == value:
output['isWord'] = True
return output
if root.value < value:
return self.search(root.right, value, output)
return self.search(root.left, value, output)
def insert_value(self, value):
self.root = self.insert(self.root, value)
def delete_value(self, value):
self.root = self.delete(self.root, value)
def search_value(self, value):
return self.search(self.root, value)
New contributor
Dino is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.