Введение
Игра Fillwords популярна благодаря своей простоте и увлекательности: она развивает словарный запас, тренирует внимательность и логику. Миллионы игроков по всему миру используют её как способ расслабиться и одновременно размять
Играя в Fillwords, я заметил, что сложные уровни требуют всё больше времени. Это натолкнуло меня на идею создать программу-помощник на Python.
Я считаю, что это решение будет полезным упражнением как для начинающих программистов, так и для игроков, которым сложно находить подходящие слова.
Это моя первая публикация на Хабре, и я буду признателен за ваши советы и конструктивную критику.
Правила игры
Игра Fillwords представляет собой головоломку, в которой необходимо находить слова в сетке из букв. Основные правила:
-
Игровое поле состоит из квадратных ячеек с буквами. Буквы в ячейках изначально окрашены в цвет по умолчанию (чёрный).
-
Игрок должен находить слова, соединяя буквы в свободных ячейках по соседним клеткам (вверх, вниз, влево, вправо).
-
Каждая буква в слове должна соединяться с предыдущей.
-
Одна и та же клетка не может использоваться дважды в одном слове.
-
Если буквы в выбранных ячейках составляют слово, совпадающее с заданным, то все буквы в этих ячейках окрашиваются в новый цвет.
-
Слова должны состоять из трех или более букв.
Пример игрового поля:
Р И Л О
К А В Т
Э Р А Й
Х О Л А
Список слов: ['АКРИЛ', 'ОТВАР', 'ЭХО', 'ЛАЙ']
Постановка задачи
Программа, которую мы разрабатываем, должна реализовать правила игры Fillwords и помочь игроку находить слова на игровом поле. Основные задачи программы:
-
Реализация правил игры:
-
Программа должна корректно обрабатывать игровое поле, состоящее из ячеек с буквами.
-
Она должна учитывать правила соединения букв: слова могут быть составлены только из соседних ячеек (вверх, вниз, влево, вправо).
-
Каждая ячейка может быть использована только один раз в рамках одного слова.
-
Слова должны состоять из трёх или более букв.
-
-
Цель — быть помощником игрока:
-
Программа должна находить полный список слов, который можно построить из ячеек с буквами на игровом поле.
-
Программа должна предлагать варианты заполнения игрового поля, выделяя слова разными цветами.
-
-
Использование словаря допустимых слов:
-
Для проверки корректности найденных слов в программе мы будем использовать словарь существительных русского языка.
-
Словарь должен быть представлен в виде списка слов в нижнем регистре, чтобы упростить процесс поиска и сравнения.
-
Программа должна проверять, что найденные слова присутствуют в словаре, и исключать из результатов недопустимые комбинации букв.
-
Мы выбрали словарь Список существительных по словарю Ефремовой. , так как он содержит более 50 тысяч слов, а его структура удобна для обработки в Python. Его можно найти на GitHub в проекте Russian Nouns.
-
-
Реализовать вывод букв в цвете:
-
Для наглядного отображения найденных слов программа будет использовать библиотеку colorama, которая позволяет легко форматировать цвет текста в терминале.
-
Библиотека colorama была выбрана благодаря своей простоте и кросс-платформенной поддержке (Windows, macOS, Linux).
-
Часть 1. Создание классов игрового поля
В этой части мы разработаем классы игрового поля такие, как Ячейка (Cell) и Доска (Board), после чего проведем тестирование работы разработанных классов
Класс Cell - ячейка
Ячейка (Cell) — элемент игрового поля, которая должна содержать:
-
letter - буква в нижнем регистре, чтобы производить поиск в словаре без дополнительных преобразований;
-
x - номер столбца;
-
y - номер строки, которые описывают координаты ячейки на игровом поле;
-
color - цвет буквы.
from colorama import init, Fore, Style
init()
# Цвет для незанятой ячейки
DEFAULT_COLOR = Fore.BLACK
# Список цветов для найденных слов
WORD_COLORS = [Fore.RED, Fore.GREEN, Fore.YELLOW, Fore.BLUE, Fore.MAGENTA, Fore.CYAN]
class Cell:
""" Ячейка игрового поля """
def __init__(self, letter, x, y):
"""Инициализация ячейки"""
self.letter = letter.lower()
self.x = x
self.y = y
self.color = DEFAULT_COLOR
def set_color(self, color):
"""Установка цвета ячейки"""
self.color = color
Класс Cell
использует colorama для цветового оформления, что придает ему гибкость при использовании других библиотек. Цвета хранятся в списке WORD_COLORS
, что позволяет задавать цвета для разных найденных слов без привязки к конкретной библиотеке. Смена цветовой схемы производится путем изменения значений элементов списка.
Класс Board - Доска
Доска (Board) — представляет собой игровое поле, которое содержит матрицу из ячеек Cell
. Оно содержит следующие атрибуты:
-
height — количество строк в игровом поле.
-
width — количество столбцов в игровом поле.
-
grid — двумерный список объектов
Cell
, представляющий игровое поле. Он отвечает за инициализацию матрицы и отображение текущего состояния поля.
class Board:
""" Игровое поле """
def __init__(self, letter_rows, dictionary_file='russian_nouns.txt'):
""" Инициализация игрового поля """
self.grid = [[Cell(letter, x, y) for x, letter in enumerate(row)] for y, row in enumerate(letter_rows)]
self.dictionary = self.load_dictionary(dictionary_file)
self.width = len(letter_rows[0]) if letter_rows else 0
self.height = len(letter_rows)
def load_dictionary(self, filename):
""" Загрузка словаря слов """
try:
with open(filename, 'r', encoding='utf-8') as file:
return set(word.strip().lower() for word in file if len(word.strip()) >= 3)
except FileNotFoundError:
print(f'Файл {filename} не найден.')
return set()
def get_cell(self, x, y):
""" Получение ячейки по координатам """
if 0 <= y < self.height and 0 <= x < self.width:
return self.grid[y][x]
return None # Вывод, если ячейка находится за границами игрового поля
def display(self):
""" Вывод игрового поля """
for row in self.grid:
print(' '.join(cell.color + cell.letter.upper() + Style.RESET_ALL for cell in row))
В разделе с кодом метода display()
мы используем Style.RESET_ALL
, чтобы после вывода цветных символов остальные элементы терминала отображались в стандартном формате.
Проверка работоспособности кода
Для проверки корректности работы классов Cell и Board используем следующий код:
# Тестовый пример
if __name__ == "__main__":
# Элементы поля. Символы в строках соответствуют строкам игрового поля
test_letters = [
"РИЛО",
"КАВТ",
"ЭРАЙ",
"ХОЛА"
]
# Проверка правильности заполнения и вывода поля
board = Board(test_letters)
print("Чистое поле:")
board.display()
# Проверка правильности заполнения ячеек игрового поля и их отображения при выводе
cells = ((0, 0), (1, 0), (2, 0), (0, 1), (1, 1))
for cell in cells:
board.get_cell(*cell).set_color(WORD_COLORS[0]) # 0 -раскрашивает ячейки в красный цвет (Fore.RED)
print("nЗаполнено одно слово:")
board.display()
Результат работы программы:

В этом коде мы проверяем правильность отображения игровой доски для занятых и свободных ячеек.
Полный код это части можно посмотреть здесь
Часть 2. Алгоритм поиска слов
Теперь, когда мы определили структуры игрового поля, самое время подумать над алгоритмом поиска слов
Шаги алгоритма
1. Выбираем стартовую ячейку
Допустим, что у нас есть игровое поле. Каждую букву на поле мы рассматриваем как принадлежащее некоторому слову:
Р И Л О
К А В Т
Э Р А Й
Х О Л А
Мы можем начать, например, с буквы "Р" в позиции (2,1).
2. Создаём начальное слово
В начале слово состоит только из одной буквы. Мы храним список ячеек, а не просто строку.
Пример:
Текущее слово = [ (2,1) ]
(ячейка с буквой "Р")
Поскольку мы ищем слова состоящие из 3-х букв и более, то выделение множества слов, которые содержат одну начальную букву мы не будем.
3. Создаем производные слова путем добавления соседних букв
Исходя из текущего слова, мы можем сформировать производные, добавляя соседние буквы либо в начало, либо в конец списка ячеек. Поскольку сейчас наше слово состоит из одной ячейки, то эта ячейка будет как началом, так и концом слова.
Поскольку слово можно читать в обоих направлениях, важно не допускать дублирования. При создании множества производных слов следует исключать как идентичные варианты, так и их зеркальные копии. Это позволяет значительно ускорить поиск, так как сокращает количество проверяемых слов.
Пример:
-
Добавляем "Э" (2,0) в начало: "ЭР"
-
Добавляем "Э" (2,0) в конец: "РЭ" ... повторяем для всех прилежащих букв
После обхода всех соседей у нас получится 8 слов состоящие из двух букв. Если убрать зеркальные дубли, то мы получим множество из 4 слов
[ (2,0), (2,1) ]
→ "ЭР"
[ (1,1), (2,1) ]
→ "АР"
[ (3,2), (2,1) ]
→ "АР"
[ (1,2), (2,1) ]
→ "ОР"
На этапе поиска игнорируем слова, содержащие две буквы.
4. Проверяем, есть ли наше слово в словаре
Когда мы пойдем к 3-х буквенным словам, то при создании множества производных слов с исключением прямых и зеркальных дублей, мы создаем новый словарь допустимых слов из словаря, которые содержат текущее слово в любом направлении как подстроку (например, "РЭК", "КЭР" или "РАЙ" , "ЙАР"). Например, для пары "РЭК", "КЭР" будут слова "РЕКЕТ", "РЭКЕТИР". "РЭКЕТИРСТВО" Тогда как для пары "РАЙ" , "ЙАР" - 22 слова. Мы заменяем текущий словарь новым, содержащим только подходящие слова.
После этого, мы проверяем слово на точное совпадение слова с о словами словаря. Если совпадение найдено, то мы заносим его в список найденных слов. Для слов ("РАЙ" , "ЙАР") найденное слово будет "РАЙ".
Если словарь допустимых слов пустой, то мы прекращаем поиск - потомков данного слова. В противном случае продолжаем создание производных слов. Если соседние ячейки в примыкающее к началу и концу слова заняты или уже использованы в составе слова, то поиск производных слов прекращаем.
Часть 3. Реализация алгоритма поиска слов
Прежде чем приступить к реализации алгоритма создадим класс WordPath.
Класс WordPath - Путь Слова
Класс Путь Слова (WordPath
) — представляет собой последовательность ячеек (Cell), которые образуют слово на игровом поле. Оно содержит следующие атрибуты:
-
board — игровое поле.
-
cells — список ячеек на игровом поле.
-
dictionary — множество, содержащих текущее слово как подстроку.
Основные методы
class WordPath:
""" Путь ячеек слова на игровом поле """
def __init__(self, board, cells):
""" Инициализация """
self.board = board
self.cells = cells
self.dictionary = board.dictionary
def get_word(self):
""" Возвращает строковое представление """
return ''.join(cell.letter for cell in self.cells)
def is_valid(self):
""" Проверка слова в прямом и обратном направлении"""
word = self.get_word()
if word in self.dictionary:
return 1
if word[::-1] in self.dictionary:
return 2
def filter_dictionary(self):
""" Фильтрация словаря """
word = self.get_word()
self.dictionary = {w for w in self.dictionary if word in w or word[::-1] in w}
Далее мы рассмотрим методы класса WordPath
, которые будут использованы при разработке алгоритма поиска слов.
Построение списка свободных ячеек
Для построения производных слов нам нужно реализовать метод, который создает список свободных ячеек, прилежащих к началу или концу к списка.
def get_adjacent_free_cells(self, begin=True):
""" Возвращает свободные соседние ячейки прилежащих к началу или к концу слову """
free_cells = [] # Список свободных ячеек
if not self.cells:
return free_cells
cell = self.cells[0] if begin else self.cells[-1] # Первая или последняя ячейка, вокруг которой ищутся свободные ячейки
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # Список направлений поиска свободных ячеек
for dx, dy in directions:
adjacent = self.board.get_cell(cell.x + dx, cell.y + dy)
if (adjacent and adjacent.color == DEFAULT_COLOR and adjacent not in self.cells):
free_cells.append(adjacent)
return free_cells
Перед занесением в список свободных ячеек проводится проверка условий:
-
adjacent
не равноNone
- координаты ячейки не выходят за пределы поля; -
adjacent.color == DEFAULT_COLOR
- ячейка свободная (присвоен цвет по умолчанию); -
adjacent not in self.cells
- ячейка не включена в список ячеек. Если ячейка соответствует приведенным критериям, то она включается в список свободных ячеек.
Построение списка производных слов.
Для обеспечения уникальности объектов класса WordPath в прямом и обратном направлении нужно создать пустое множество кортежей координат ячеек проверяемых слов existing_paths
как атрибут объекта board.
class Board:
""" Игровое поле """
def __init__(self, letter_rows, dictionary_file='russian_nouns.txt'):
""" Инициализация игрового поля """
self.grid = [[Cell(letter, x, y) for x, letter in enumerate(row)] for y, row in enumerate(letter_rows)]
self.dictionary = self.load_dictionary(dictionary_file)
self.width = len(letter_rows[0]) if letter_rows else 0
self.height = len(letter_rows)
self.existing_paths = set() # множество кортежей координат ячеек проверяемых слов
На основе списка ячеек мы должны построить список производных слов, путем использования метода def expand_paths()
класса WordPath
.
def expand_paths(self):
""" Построение списка производных слов """
new_paths = [] # Список производных слов
for begin in [True, False]: # Поиск свободных ячеек, прилежащих к началу или концу слова
free_cells = self.get_adjacent_free_cells(begin) # Список свободных ячеек
for cell in free_cells:
# Добавление ячейки к слову с начала или с конца
new_cells = [cell] + self.cells if begin else self.cells + [cell]
path_tuple = tuple((c.x, c.y) for c in new_cells) # Координаты кортежа ячеек
reverse_tuple = path_tuple[::-1] # Координаты обратного кортежа ячеек
# Проверка уникальности кортежа ячеек в прямом и обратном направлении
if path_tuple not in self.board.existing_paths and reverse_tuple not in self.board.existing_paths:
new_paths.append(WordPath(self.board, new_cells)) # Добавление производного слова
self.board.existing_paths.add(path_tuple) # Добавление уникального кортежа ячеек
return new_paths
В этом методе мы производим следующие операции:
-
Создаем пустой список производных слов
new_paths
; -
Для ячеек прилежащих к началу или концу слова:
2.1. Проводим поиск свободных ячеек
free_cells
;2.2. Для каждой свободной ячейки `cell:
2.2.1. Создаем производное слово
new_cells
путем присоединения ячейкиcell
к началу или к концу словаself.cells
;2.2.2. Создаем кортежи координат производного слова в прямом
path_tuple
и обратномreverse_tuple
направлении;2.2.3. Если кортежи в прямом и обратном направлении не содержатся в множестве кортежей координат ячеек
self.board.existing_paths
то, кортеж добавляется в в множествоself.board.existing_paths
а слово, добавляется в список производных словnew_paths
; -
Возвращаем список
new_paths
Теперь мы можем приступить к реализации алгоритма.
Реализация алгоритма поиска слов
Создадим функцию, которая производит поиск слов для заданной ячейки на игровом поле.
def find_words(board, start_cells):
""" Поиск слов для заданной ячейки на игровом поле """
found_words = [] # Список найденных слов
path = WordPath(board, [start_cells]) # Создаем слово для начальной ячейки
paths = [path] # включаем в список поисковых слов
while paths: # список поисковых слов не пуст
current_path = paths.pop() # извлекаем слово из конца списка
if len(current_path.cells) >= 3: # Игнорируем слова, которые содержат меньше 3 букв
current_path.filter_dictionary() # Обновляем множество подходящих слов
if not current_path.dictionary: # Если множество подходящих слов пустое
continue # Переходим к началу цикла
if directions := current_path.is_valid(): # Проверка слова в прямом и обратном направлении
if directions == 2: # Если слова содержится в словаре в обратном направлении, то переворачиваем список ячеек
current_path.cells.reverse()
found_words.append(current_path)
paths.extend(current_path.expand_paths()) # добавляем слово в список поисковых слов
return found_words
В этом методе мы производим следующие операции:
-
Создаем пустой список найденных слов
found_words
; -
Создаем слово для начальной ячейки
path
и включаем его в список поисковых словpaths
; -
Пока список поисковых слов
paths
не пуст:
3.1. Извлекаем слово из конца спискаpaths
в переменнуюcurrent_path
;
3.2. Если словоcurrent_path
содержит не меньше 3-х букв, то Обновляем множество подходящих словcurrent_path.dictionary
;
3.3. Если множество подходящих слов пустое, то переходим к следующей итерации цикла 3.
3.3. Если слово в прямом или обратном направлении содержится во множестве допустимых слов:
3.3.1. Если слово в обратном направлении содержится во множестве допустимых слов, то, переворачиваем в нем список ячеек;
3.3.2. Добавим слово в список найденных словfound_words
;3.4. Расширяем список поисковых слов созданных для слова
current_path
.
Проверка работоспособности кода
Для проверки корректности работы алгоритма поиска слов используем следующий код:
# Тестовый пример
if __name__ == '__main__':
# Данные для создания игрового поля
test_board = [
"РИЛО",
"КАВТ",
"ЭРАЙ",
"ХОЛА"
]
# Создание и отображение игрового поля
board = Board(test_board)
board.display()
start_cell = board.get_cell(2, 1) # Получение ячейки с заданными координатами
words = find_words(board, start_cell) # Запуск функции Поиска слов на игровом поле
# Вывод print('nНайденные слова:')
# Выводим найденные слова с сортировкой по длине слова и алфавиту
for word in sorted(words, key=lambda x: (len(x.get_word()), x.get_word())): print(word.get_word())
В тестовом примере мы проверяем правильность алгоритма для ячейки с координатами x=2
и y=1
.
При выполнении программы будет выведен текст:
Р И Л О
К А В Т
Э Р А Й
Х О Л А
Найденные слова:
вак
вал
вар
вар
авто
авто
лава
автол
автол
орава
орава
отвал
отвар
отвар
Обращает внимание наличие повторяющихся слов: вар
, авто
, автол
, орава
, отвар
. Это может свидетельствовать о том, что алгоритм работает не совсем правильно.
Что бы понять из каких ячеек состоят слова, нужно вывести содержимое ячеек на печать. Для этого, мы добавим новые функции __repr__
текстового представления классов Cell
и WordPath
. Добавим их в конец кода определения классов
class Cell:
...
def __repr__(self):
return f'Cell({self.letter}, {self.x}, {self.y})'
...
class WordPath:
...
def __repr__(self):
return f"WordPath('word={self.get_word()}, cells={self.cells})"
Внесем исправления последнюю строчку кода тестового примера. Вместо кода
print(word.get_word())
внесем код:
print(word)
Ниже приведен вывод программы, в котором приведен вывод для повторяющихся слов
Р И Л О
К А В Т
Э Р А Й
Х О Л А
Найденные слова:
WordPath('word=вар, cells=[Cell(в, 2, 1), Cell(а, 2, 2), Cell(р, 1, 2)])
WordPath('word=вар, cells=[Cell(в, 2, 1), Cell(а, 1, 1), Cell(р, 1, 2)])
WordPath('word=авто, cells=[Cell(а, 2, 2), Cell(в, 2, 1), Cell(т, 3, 1), Cell(о, 3, 0)])
WordPath('word=авто, cells=[Cell(а, 1, 1), Cell(в, 2, 1), Cell(т, 3, 1), Cell(о, 3, 0)])
WordPath('word=автол, cells=[Cell(а, 2, 2), Cell(в, 2, 1), Cell(т, 3, 1), Cell(о, 3, 0), Cell(л, 2, 0)])
WordPath('word=автол, cells=[Cell(а, 1, 1), Cell(в, 2, 1), Cell(т, 3, 1), Cell(о, 3, 0), Cell(л, 2, 0)])
WordPath('word=орава, cells=[Cell(о, 1, 3), Cell(р, 1, 2), Cell(а, 1, 1), Cell(в, 2, 1), Cell(а, 2, 2)])
WordPath('word=орава, cells=[Cell(о, 1, 3), Cell(р, 1, 2), Cell(а, 2, 2), Cell(в, 2, 1), Cell(а, 1, 1)])
WordPath('word=отвар, cells=[Cell(о, 3, 0), Cell(т, 3, 1), Cell(в, 2, 1), Cell(а, 2, 2), Cell(р, 1, 2)])
WordPath('word=отвар, cells=[Cell(о, 3, 0), Cell(т, 3, 1), Cell(в, 2, 1), Cell(а, 1, 1), Cell(р, 1, 2)])
Если мы рассмотрим вывод программы, то мы увидим, что, несмотря на то, что некоторые слова совпадают в своем написании, они образованы разными цепочками ячеек, что делает их уникальными в контексте алгоритма. На основании этого, мы можем сделать вывод, что алгоритм поиска слов работает корректно.
Полный код это части можно посмотреть здесь
Часть 4. Реализация.
У нас есть все необходимое для того, чтобы решить, поставленные задачи.
Поиск всех слов на игровом поле
Для того, что бы реализовать эту функцию - достаточно провести поиск слов для каждой ячейки игрового поля с помощью функции find_words()
что бы получить общий список слов. Поскольку процесс может занять длительное время, то мы добавим параметр progress
который будет отображать обработанную ячейку поля символом '.'
. Ниже приведен код функции поиска всех слов на игровом поле get_words()
:
def get_words(board, progress=False):
""" Поиск всех слов на игровом поле"""
result = []
for x in range(board.width):
for y in range(board.height):
start_cell = board.get_cell(x, y) # Получение ячейки с заданными координатами
words = find_words(board, start_cell) # Запуск функции Поиска слов на игровом поле
result.extend(words)
if progress: # Если нужно отразить прогресс работы функции
print('. ', end='')
if progress: # Если нужно отразить работы функции
print()
return result
Тестирование работы функции проводим с помощью следующего кода:
# Тестовый пример
if __name__ == '__main__':
# Данные для создания игрового поля
test_board = [
"РИЛО",
"КАВТ",
"ЭРАЙ",
"ХОЛА"
]
# Создание и отображение игрового поля
board = Board(test_board)
board.display()
print("nПолучаем список слов")
words = get_words(board, progress=True)
print('nВывод результата')
words_list = [word.get_word() for word in sorted(words, key=lambda x: (-len(x.get_word()), x.get_word()))]
print(*words_list, sep=', ')
Вывод работы программы:
Р И Л О
К А В Т
Э Р А Й
Х О Л А
Получаем список слов
. . . .
. . . .
. . . .
. . . .
Вывод результата
Всего слов: 35
автол, автол, акрил, орава, орава, орала, отвал, отвар, отвар, хорал, авто, авто, арак, илот, лава, рало, аил, аир, акр, вак, вал, вар, вар, лай, лай, лар, лох, рай, рак, рол, тол, хор, эра, эра, эхо
Таким образом - первая цель программы: "Программа должна находить полный список слов, который можно построить из ячеек с буквами на игровом поле" решена.
Полный код это части можно посмотреть здесь
Автоматическое заполнение игрового поля
Постановка задачи
-
Дано игровое поле, состоящее из квадратных ячеек, заполненных буквами.
-
Найдены все возможные слова (цепочки ячеек), из которых можно составить слова.
-
Требуется составить такой список слов, чтобы при переносе его на игровое поле ячейки, входящие в слова, не пересекались, а все ячейки игрового поля были заполнены.
Добавление новых методов.
Прежде чем приступить к реализации алгоритма нам нужно добавит несколько методов в класс WordPath
Добавим функцию fill_color(self, color)
, которая будет заполнять все ячейки слова заданным цветом и reset_color(self)
, которая будет возвращать цвет ячеек в состояние по умолчанию (DEFAULT_COLOR
).
class WordPath:
...
def fill_color(self, color):
""" Заполняет все ячейки слова заданным цветом """
for cell in self.cells:
cell.set_color(color)
def reset_color(self):
""" Присваивает ячейкам цвет по умолчанию """
for cell in self.cells:
cell.set_color(DEFAULT_COLOR)
Добавим метод is_free(self)
, который проверяет, что все ячейки слова (цепочки ячеек) могут быть помещены на свободные ячейки игрового поля.
class WordPath:
...
def is_free(self):
""" Проверяет, что все ячейки свободны """
return all(cell.color == DEFAULT_COLOR for cell in self.cells)
Описание алгоритма
Алгоритм должен найти такой набор слов, чтобы каждое слово занимало свободные ячейки на игровом поле, а все ячейки поля будут заняты . Он последовательно пробует различные комбинации слов, "раскрашивая" ячейки и откатываясь назад, если комбинация не подходит.
Сначала мы обрабатываем слова с большим количеством символов, так как они покрывают больше ячеек на игровой доске. Тем самым мы уменьшается количество слов, которые используются в следующей итерации, делая алгоритм быстрее.
def backtracking_fill(board, word_paths):
"""
Поиск полного покрытия игрового поля с помощью алгоритма поиска с возвратом. Возвращает итоговый список со словами или None. """
# Базовый случай # Проверяем, все ли ячейки заняты
if all(cell.color != DEFAULT_COLOR for row in board.grid for cell in row):
return []
# Для каждого доступного слова (word_path) в списке word_paths.
for i in range(len(word_paths)):
word_path = word_paths[i]
word_path.fill_color(WORD_COLORS[1]) # Слово добавляется на поле
# Отбираются только те слова, которые можно разместить на оставшихся свободных ячейках.
next_word_paths = [wp for wp in word_paths[i + 1:] if wp.is_free()]
# Рекурсивный вызов
result = backtracking_fill(board, next_word_paths)
# Проверка результата, если текущий выбор слова оказался неправильным
if result is None:
word_path.reset_color() # Слово убирается с поля
continue # Переходим к следующему слову
# решение найдено result = [word_path] + result
word_path.reset_color() # Слово убирается с поля
return result
# Проверили все слова в списке, но ни одно не подошло
return None
Проверка работы кода.
Для перебора цветов выводимых букв мы будем использовать функцию cycle() модуля itertools, которая используется для циклического перебора элементов в последовательности. Она создаёт итератор, который будет повторять элементы переданной ему последовательности бесконечно.
Добавим следующий код в начало файла:
from itertools import cycle
from colorama import init, Fore, Style
init()
# Цвет для неиспользованной ячейки
DEFAULT_COLOR = Fore.BLACK
# Список цветов для найденных слов
WORD_COLORS = [Fore.RED, Fore.GREEN, Fore.YELLOW, Fore.BLUE, Fore.MAGENTA, Fore.CYAN]
# Итератор для циклического перебора цветов
COLOR_CYCLE = cycle(WORD_COLORS)
Тестовый пример для заполнения игрового поля:
# Тестовый пример
if __name__ == '__main__':
test_board = [
"РИЛО",
"КАВТ",
"ЭРАЙ",
"ХОЛА"
]
# Создание и отображение игрового поля
board = Board(test_board)
print('Игровое поле:')
board.display()
words = get_words(board)
# Сортируем слова в порядке убывания их длины
words = [word for word in sorted(words, key=lambda x: (-len(x.get_word()), x.get_word()))]
# Ищем решение
solution = backtracking_fill(board, words)
if solution: # Если решение найдено
# Выводим результат print('nИгровое поле можно заполнить следующими словами:')
for word_path in solution:
color = next(COLOR_CYCLE)
print(color + word_path.get_word() + Style.RESET_ALL)
word_path.fill_color(color) # Окрашиваем найденное решение
print("nРешение:")
board.display()
else:
print("nИгровое поле заполнить не удалось.")
Результат работы программы:

Теперь, вы можете проверит работу программы на реальных данных. Полный код это части можно посмотреть здесь
Программа была проверена на следующих данных:
test_board = [
"еразалс",
"тдалвоо",
"яьещирк",
"хратром",
"инукесб",
"пдарави",
"елагило"
]
Результат запуска программы:
Игровое поле:
Е Р А З А Л С
Т Д А Л В О О
Я Ь Е Щ И Р К
Х Р А Т Р О М
И Н У К Е С Б
П Д А Р А В И
Е Л А Г И Л О
Игровое поле заполнить не удалось.
Список слов, полученных в результате работы программы:
Всего слов: 55
архипелаг, сокровище, лазарет, секунда, разлад, ворище, ладья, раунд, раунд, нукер, секта, свара, тромб, окрол, град, ваза, игра, лига, зало, трек, сорт, осек, игра, овал, кров, лори, море, ваер, ромб, ромб, раз, лад, кун, дар, лаг, тау, арк, зав, лаз, орт, арк, вар, вал, ива, ров, лов, сор, мор, аил, ива, рол, сор, мор, сом, сок
Если их перенести в игру, то можем увидеть следующий результат:

Незаполненные ячейки складываются в слово "РАВИОЛИ". В словаре русских этого слова не оказалось. Мы можем добавить это слово в словарь, но это не дает нам гарантии, что мы не столкнемся с подобной ситуацией в будущем. Это приводит нас к необходимости добавления в программу интерактивного заполнения игрового поля.
Интерактивный режим
В интерактивном режиме мы планируем поочередно выводить игровом поле с подходящим словом . Каждое слово будет окрашено в новый цвет. После вывода игрового пользователю будет задан вопрос, подходит это слово для решения головоломки или нет. Если нет, то программа удалит с поля не подходящее слово и перейдет к следующему. Если слово подходит для решения, то тогда оно остаётся на экране, и будет предложено следующее подходящее слово в другом цвете. Это может продолжаться до тех пор пока головоломка будет решена или список подходящих слов не исчерпается.
Код функции заполнения игрового поля в ручном режиме manual_fill_mode()
:
def manual_fill_mode(board, word_paths):
i = 0 # Начинаем с первого слова
color = next(COLOR_CYCLE) # Устанавливаем новый цвет букв
# Пока список слов не будет пустым или указатель меньше длины списка
while word_paths and i < len(word_paths):
word_path = word_paths[i] # Выводим слово для проверки
word_path.fill_color(color) # Добавляем слово на поле
# Выводим заголовок со словом и печатаем игровое поле
print(f'nСлово: {color + word_path.get_word().upper() + Style.RESET_ALL}')
board.display()
# Запрос на совпадении слова
result = input("nСлово подходит (y/n): ").strip().lower()
if result[0] in ('y', 'д'):
color = next(COLOR_CYCLE) # Переходим к следующему цвету
# Отбираются только те слова, которые можно разместить на оставшихся свободных ячейках.
word_paths = [wp for wp in word_paths[1:] if wp.is_free()]
i = 0 # Сбрасываем счетчик
# Если список подходящих слов пуст
if not word_paths:
print('nНет подходящих слов для заполнения')
return None
else:
word_path.reset_color() # Убираем слово с поля
i += 1 # переходим к следующему слову в списке
word_path.reset_color() # убираем слово с поля
# Вывод игрового поля
print('nИтоговое поле:')
board.display()
Для задействования игрового режима изменим код основной программы
вместо последних строчек кода:
...
else:
print("nИгровое поле заполнить не удалось.")
добавим следующий код:
...
else:
result = input(
"nИгровое поле заполнить не удалось. Продолжить в интерактивном режиме? (y/n): ").strip().lower()
if result[0] in ('y', 'д'):
manual_fill_mode(board, words)
Программа была проверена на следующих данных:
test_board = [
"еразалс",
"тдалвоо",
"яьещирк",
"хратром",
"инукесб",
"пдарави",
"елагило"
]
Вывод программы:
Игровое поле:
Е Р А З А Л С
Т Д А Л В О О
Я Ь Е Щ И Р К
Х Р А Т Р О М
И Н У К Е С Б
П Д А Р А В И
Е Л А Г И Л О
Игровое поле заполнить не удалось. Продолжить в интерактивном режиме? (y/n):
После ввода символа 'y'
, был выведен следующий текст

После ввода символа 'y'
-

Ниже приведен заключительный скриншот работы программы:

Таким образом, мы получили игровое поле, в котором, были отражены все слова, кроме одного, которое отсутствовало в словаре. Это слово можно угадать. Правда авторы головоломки могут подбросить не одно а несколько слов, которые отсутствуют в нашем словаре. Но и в этом случае, пользователям программы нужно будет сосредоточится только на проблемных словах, вместо того, что ты отгадывать все слова.
Вторая цель программы: Программа должна предлагать варианты заполнения игрового поля, выделяя слова разными цветами. так же оказалась решенной.
Теперь, вы можете проверит работу программы на реальных данных. Полный код это части можно посмотреть здесь
Заключение
В этой статье мы разобрали, как можно автоматизировать решение головоломки Fillwords на Python. Мы пошагово реализовали программу, начиная с создания игровых структур и алгоритма поиска слов, и заканчивая поиском полного заполнения поля с использованием поиска с возвратом (backtracking).
Основные результаты, которых мы достигли:
-
Разработали классы
Cell
иBoard
, позволяющие удобно работать с игровым полем. -
Разработали класс
WordPath
и реализовали алгоритм поиска слов, который учитывает соединения букв и проверяет их в словаре. -
Реализовали алгоритм автоматического заполнения поля, который находит решение головоломки.
-
Добавили интерактивный режим, позволяющий пользователю самостоятельно определять порядок заполнения игрового поля.
Что можно сделать в будущем?
Автоматизация взаимодействия с игрой
Следующий шаг в развитии проекта — создание системы, которая сможет самостоятельно решать головоломку Fillwords в реальной игре. Для этого потребуется:
-
Сделать снимок экрана игрового поля — программа делает скриншот экрана и определяет область с игровым полем.
-
Распознавание букв — с помощью OCR (например,
Tesseract OCR
) программа считывает буквы и заносит их в игровое полеBoard
. -
Взаимодействие с игрой — программа автоматически соединяет ячейки на экране, вводя найденные слова. Это можно реализовать с помощью инструментов автоматизации (
pyautogui
). -
Анализ отклика игры — программа следит за тем, приняло ли приложение слово, и отмечает использованные слова.
-
Обратная связь c пользователем — если игровое поле невозможно полностью заполнить, программа предупредит игрока и предложит возможные варианты решения.
Мы надеемся, что этот материал окажется полезным как для разработчиков, изучающих алгоритмы и обработку текстов, так и для игроков, желающих улучшить свои навыки в Fillwords.
Источник кода: GitHub
Попробуйте запустить код, протестируйте его на реальных данных и делитесь своими решениями!
Автор: rustamgiz