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

S>1) Имеется попрямоугольное поле из клеток размером, скажем, m*n. В некоторых клетках расположены числа. Все числа, кроме единиц, имеют пары, и эти пары соединяются линией;
S>2) Количество клеток в линии вместе с концевыми равно числам на её концах;
S>3) Клетки, содержащие единицы, являются папой самим себе и представляют линию длиной в одну клетку;
S>4) Клетки, соединяющие пары, могут преломляться по горизонтали и вертикали

Каждой клетке с числом k соответствует ромб из 4k-4 клеток, удалённых от неё на расстояние k-1. Среди них и нужно искать кандидатов в пару к ней.

S>5) Линии, соединяющие пары, не могут пересекаться и проходить через одну и ту же клетку.

После того, как найдены пары клеток, — решается задача, похожая на задачу о разводке печатной платы.

S>Требуется найти и закрасить все эти линии, чтобы получить картинку.

Это что, новая версия японского кроссворда? Или есть какое-то практическое применение?

S>Для 1-й, 2-х и 3-х клеток алгоритм, в принципе, понятен. Хотелось бы более или менее общий алгоритм для произвольного числа клеток.

Сдаётся мне, даже для поля, содержащего только числа 1 и 2, получается NP-полная задача. А именно, это задача о построении гамильтонова пути в графе.
Впрочем, надо тщательно поразмыслить.