Задача построения слова из трех букв ТСА — это головоломка. Она решена, если получена одна из комбинаций «САТ» или «АСТ».
Для решения этой задачи используется простой поисковый алгоритм generate-and-test (генерация нового состояния из исходного и проверка — не получены ли целевые слова «САТ» или «АСТ»).
Поисковый алгоритм отстоит из двух шагов:
1. Сгенерировать новое состояние, модифицируя предыдущее - с помощью добавления только одной буквы.
2. Проверить, не является ли образовавшееся состояние конечным (целевым).
При этом возможны два варианта или метода поиска: поиск в глубину и поиск в ширину. Эти методы исключают бесполезный повторный выбор одних и тех же вершин графа