Если мы возьмём любую цепочку, проходящую через все точки (например, змейку или спираль), и разрежем её на куски всеми возможными способами, а потом часть кусков ещё и развернём, у нас уже получится примерно 2^(N^2)/3 вариантов. Уже при N=7 перечислить их нереально (при N=6 их всего 10 миллиардов - это не так много). Но поскольку исходных цепочек (проходящих через все точки) много, а кроме того, не все конфигурации можно получить разрезанием одной цепочки, вариантов будет ещё больше.
Алгоритмы - как рекурсия, так и перебор состояний клеток - не очень сложные. В обоих случаях нужно искать разбиение на неориентированные цепочки, а потом всеми способами задавать их направление.
В случае перебора состояний (он проще) делаем так. Замечаем, что у каждой клетки есть 10 возможных состояний - 4 для конца цепочки (направления, куда из этой клетки цепочка идёт), 4 для клетки, где цепочка поворачивает, и 2 для клетки, через которую она проходит прямо. Кроме того, есть ограничения: цепочка не может упираться в стенку, и общее ребро двух соседних клеток либо пересекается цепочкой с каждой стороны, либо нет. Ну, и не должно быть циклов.
Алгоритм получается таким. Перебираете клетки матрицы по строкам. Для каждой очередной клетки смотрите состояние её соседей, и получаете список возможных состояний самой клетки - их не более трёх. В случае, если есть состояние, которое соединяет две соседние цепочки, надо пройтись по ним - проверить, не являются ли они концами одной цепочки (если да - получится цикл, а он запрещён). Теперь подставляем в клетку по очереди все допустимые состояния, и рекурсивно вызываем функцию перебора для следующей клетки. Когда дойдём до конца - фиксируем найденное разбиение.
