Алгоритм Х или что общего между деревянной головоломкой и танцующим Линком?

[stanishevsky]

Всеобщее молчание и в закладках уже у 20 человек — и добавить нечего, и полезно, и красиво. Спасибо!

[p53]

Пожалуйста :-)

[erlioniel]

Отличная статья, спасибо.

[Dimchansky]

Кстати, может кому-то понадобится, я тоже недавно накидал имплементацию алгоритма x на C# с использованием пляшущих ссылок и эвристикой, которую предлагает Кнут в своей работе.

[Dimchansky]

Посмотрел на Ваш код, вы без эвристики столбцы выбираете. Кнут советует выбирать столбец с минимальным количеством единиц, чтобы минимизировать ветвления.

[p53]

При всём уважении, мне кажется, вы не очень внимательно его смотрели.

/* select column with mininimal number of elements */
Col *select_col(){
  int min = cptr->length;
  Col *col = cptr->right, *mc = cptr;
  while(col != cptr){
    if(col->length < min){
      mc = col;
      min = col->length;
    }
    col = col->right;
  }
  return mc;
}

[Dimchansky]

Да, прошу прощения, не внимательно посмотрел routineX(), выего оттуда вынесли в select_col(), потому бегло посмотрев не увидел.

[Sirion]

Танцующие ссылки — интересно. Алгоритм — банальный перебор с возвратом.

[Mrrl]

Хороший алгоритм. Я попробовал реализовать его на битовых масках, а не на списках. Итог — 180 строк, 12 секунд (на i7, 2.9 GHz).
Код здесь.
Интересно, что будет, если фигуры разные. Это должна получиться матрица примерно 150*24000? (дополнительные 25 столбцов — на идентификаторы фигур). Боюсь, что работать будет уже не так быстро…

[p53]

Важно не только количество строк, но и как быстро они уходят (мы здесь считаем, что удалять строки проще, чем перебирать варианты). Если всего фигур n, то каждая итерация будет удалять ~1/n часть строк. В частности с двумерными пентаминошками задачи по заполнению фигуры разными доминошками считаются быстрее, чем одинаковыми. Матрица в первом случае больше, зато дерево решений не так ветвится.

[Mrrl]

Написал сборку параллелепипеда 4*5*7 из 28 пентакубиков (всех, кроме отрезка 5*1*1). Первые решения программа нашла мгновенно, но всё дерево перебирает не быстро (уже есть 20000 решений и счёт продолжается...) Так что дерево очень даже ветвится.
Интересный эффект — алгоритм сам выбирает, что делать на очередном шаге — попытаться заполнить какую-нибудь клетку возможными способами, или выбрать какую-нибудь фигуру и перебрать все возможные её расположения. Я его этому не учил…

[sanhces7]

Торт!

[RusMikle]

Чертовски интересно, особенно если фигуры будут неправильной формы и трёхмерные. Дух захватывает от перспектив быстрого решения подобных задач. Если есть ссылки на подобные решения был бы очень благодарен.

[Mrrl]

Например, вот. Но там несколько менее совершенный алгоритм.