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

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

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