Ищем алгоритм, позволяющий разместить кусочки головоломки в 2D-матрице. ⇐ Python

[Anonymous]

У меня есть игровое поле, представляющее собой двумерный массив букв — 6 x 8. Цель — найти список слов длиной, равной X, которые завершают матрицу без повторного использования буквы. Чтобы создать слово, вы можете идти вверх, вниз, влево, вправо и по всем диагоналям. Есть одно слово, которое идет слева направо, справа налево, сверху вниз или снизу вверх. Это слово описывает тему остальных слов.
Моим первоначальным решением было использовать алгоритм поиска с возвратом, чтобы найти все возможные слова в двумерной матрице. Исходя из этого, я бы использовал другой алгоритм поиска с возвратом, чтобы найти комбинацию слов, завершающую матрицу. Я представлял себе, что каждое слово — это кусочек головоломки, который, сложив вместе, образует матрицу без дублирования. Список возможных слов оказался намного длиннее, чем я ожидал, в среднем 1500 слов. Поскольку длина списка очень велика, второй алгоритм возврата будет 2 ^ 1500, который никогда не завершится. Итак, моей первой мыслью было: нужно сократить количество слов в списке возможных слов. Я пытался найти словарь, в котором было бы сокращено количество слов, но всегда попадался тот, в котором пропускалось одно-два слова, которые использовались для заполнения матрицы. Еще одно решение, о котором я подумал, — использовать ChatGPT для анализа темы и фильтрации списка на основе этого. Но GPT в этом отношении работает не очень хорошо. Если у кого-то есть предложения или комментарии, я открыт для всего.
Вот код ниже:
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[/b]

Код: Выделить всё

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)  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)  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)

Загрузить word_alpha.txt:
words_alpha.txt

Подробнее здесь: https://stackoverflow.com/questions/788 ... -2d-matrix