Есть поле букв, которое состоит из шестигранников, необходимо перебрать...

Всем добра!
Никак не могу найти оптимального решения для моей задачи.

Есть поле букв, только состоит не из квадратов, а из шестигранников. Картинка.
Задача перебрать все возможные варианты, т.е. найти все возможные слова.
Простой перебор - слишком медленно.



Редактировалось 1 раз(а). Последний 15.07.2009 00:50.

Имеется ли ввиду, что слова должны получаться последовательным прохождением полей, начиная с произвольной точки и возможны ли циклы (повторы проходимых полей)?

Конечно, любая задача на перечисление сводится к этому самому перечислению. Единственное, над чем стоит думать, это: 1) как устранить повторы маршрутов , 2) как устранить повторы слов (у Вас имется одинаковые буквы, записанные в разных клетках) , 3) как не пропустить ничего.
Тот факт, что у Вас не произвольный граф, а , скажем так, "гексагональный", имеет значение только для выбора наглядного упорядочения клеток, что позволяет строить маршруты без повторов и без пропусков. Для обеспечения отсутсвия в списке совпадающих слов, видимо, оптимальным является выписывание их в лексикографическом порядке (правда. вставка новых слов внутрь уже построенной последовательности потребует постоянной перестройки ряда (сдвиг на единицу вправо). Но ничего не поделаешь.

Оригинальное замечание про "ход конем" в детских задачках штука оригинальная, но совершенно не уместна в тех ситуациях, когда задание состоит не в поиске хода конем, а в выписывании всех возможных ходов (и не только конем). Впрочем, г-н Eastern.man это, вероятно, о чем-то таком догадался:

Цитата

В Вашем случае задача несколько иная, но всё же стоит думать о том, нельзя ли перечислять не маршруты, а что-нибудь другое.

Но по условию перечислять нужно именно МАРШРУТЫ = СЛОВА.
Конечно, условие можно представить и в иной форме, но суть не изменится, т.к. задача все-таки о выписывании всех возможных путей в графе, совмещенной с некоторым правилом отождествления. И думать придется именно об этом. Настоящая задача имеет наглядную форму, на нее и рассчитывайте.

Действительно, в процессе работы могут возникнуть идеи "оптимизации", но это не в обсуждении, а в процессе работы. Так что нужно взять некоторый алгоритм выписывания и начинать выписывать, а в процессе работы могут придти и идеи.