Здравствуйте, Tan4ik, Вы писали:

К>>Каждой клетке с числом k соответствует ромб из 4k-4 клеток, удалённых от неё на расстояние k-1. Среди них и нужно искать кандидатов в пару к ней.
T>Ты не прав. Я могу и буквой П пойти. Условия "кратчайшности" расстояния не было.

Блин! Недочитал.

К>>Сдаётся мне, даже для поля, содержащего только числа 1 и 2, получается NP-полная задача. А именно, это задача о построении гамильтонова пути в графе.
К>>Впрочем, надо тщательно поразмыслить.
T>Я бы так не сказал.
T>Поллиномиальное решение для чисел 1 и 2:
T>Покрасим доску шахматной расскраской. Задача свелась к нахождению для каждой черной двойки пары из белых двоек. Это задача поиска совершенного паросочетания в двудольном графе, которая успешно решается за полиномиальное время (есть простой алгоритм за O(N^3) и более сложные за меньшую асимптотику)

А, точно. Почему-то я подумал в сторону не просто "замостить поле доминошками", но и чтобы это была "доминошная партия".

T>Я думаю в описанную схему можно включить и тройки... но когда появятся более большие числа... боюсь эффективного решения не найти.

Всё равно остался открытым вопрос о физическом смысле этой задачи. Может, там вовсе не нужно решать её...