Поиск решения:
Для классических обходов в глубину / ширину нам надо представить данную задачу как "дойти из А в Б". Для этого предлагаю рассматривать следующее решение:
1. Пронумеруем цвета. Пусть будет 1- Синий, 2 - Желтый ... 5 - Зеленый.
2. Для каждого цвета выбираем "точку начала" и "точку финиша".
3. Теперь за точку А берем начало 1го цвета, за точку Б берем финиш последнего.
4. Условимся, что из клетки можно сделать ход по следующим правилам:
* Из точки начала делается ход только в пустые точки или в точку финиша этого же цвета.
* Из обычной точки делается ход только в пустые точки или в точку финиша этого же цвета.
* Из Финиша мы "телепортируемся" в точку начала следующего цвета. При телепорте текущий цвет меняется.
* Если мы достигли точки Б (и обошли все точки поля), то обход закончен, решение найдено.
5. На каждом шаге красим точку текущим цветом.
6. Обходим получившийся граф в глубину или ширину классическими методами (я бы сделал рекурсивный обход в глубину).
Генерация карты:
Вариант 1 - ставим точки случайным образом и ищем решение. Нашли решение? Вот и новая карта.
Вариант 2 - обходим все поле 1 линией со случайными поворотами. В точке начала - начало 1го цвета. В точке конца - финиш последнего цвета. Выбираем 4 места (чтобы получить 5 отрезков) на данной линии (с расстоянием между ними не менее 2х клеток), ставим по 2 маркера в выбранных местах: конец предыдущего цвета (по обходу) и начало следующего.
Что гуглить: теорию графов, алгоритмы поиска пути.
P.S. кто захочет поиграть - ключевые слова для поиска "Flow".
