Syjgin
Newbie | Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Не могу найти информацию по алгоритму поиска решения головоломки пентамино - на вход поступает законченная фигура в виде текстового файла из нолей и единиц, на выходе нужно разбить эту фигуру на части заданными деталями. В общих чертах, кажется, нужно следующее: сделать рекурсию до тех пор, пока неразбитая часть не равна одной из элементарных фигур, а если она не равна, то, начиная с, допустим, левого верхнего угла подставлять любую фигуру, затем: если она не подходит, переходим к следующей, если подходит, начинаем разбивать то, что получилось в результате. Если в конце концов получается фигура, не соответствующая ни одной из элементарных, идем на шаг назад и ставим другую фигуру(нужно хранить id фигуры, примененной на прошлом шаге). Только кажется, что такой перебор с возратом может никогда не найти нужное решение. Кажется, должен быть стандартный алгоритм, который нужно адаптировать к этому случаю. Никто не знает, какой? |
