Помогите с алгоритмом решения задачи

Вроде выглядит не сложно. У меня есть 3 идеи:

1. Начало обхода может быть либо из серединки, либо из углов массива.
2. Начинать надо в любом случае с элемента с бОльшим значением, так как всегда можно набрать число длины 9 цифр, где в начале должна стоять самая большая из доступных цифр
3. Остальной проход - обычный поиск в глубину

У меня вышло как то так

int getMax(int[,] matrix)
{
    var max = 0;    
    var startElement = 0;
    startElement = Math.Max(startElement, matrix[0, 0]);
    startElement = Math.Max(startElement, matrix[2, 2]);
    startElement = Math.Max(startElement, matrix[0, 2]);
    startElement = Math.Max(startElement, matrix[2, 0]);
    startElement = Math.Max(startElement, matrix[1, 1]);    
    for (var i = 0; i < 3; i++) 
        for (var j = 0; j < 3; j++)     
            if (matrix[i, j] == startElement)
                max = Math.Max(getMax(matrix, i, j), max);
    return max;
}   
int getMax(int[,] matrix, int i, int j)
{
    if (i < 0 || i > 2 || j < 0 || j > 2) return 0; 
    var v = matrix[i, j];
    if (v == -1) return 0;
    matrix[i, j] = -1;
    var max = Math.Max(
        Math.Max(getMax(matrix, i + 1, j), getMax(matrix, i - 1, j)),
        Math.Max(getMax(matrix, i, j + 1), getMax(matrix, i, j - 1)));
    matrix[i, j] = v;
    var t = max;
    while (t > 0)
    {
        t = t / 10;
        v = v * 10;
    }   
    return v + max;
}

Проверял вот так

var matr = new int[,] { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
Console.WriteLine(getMax(matr));

Вывод

987456321

Думаю, чтобы ускорить, можно попытаться отсечь короткие пути (которые не дают 9 цифр) + первые 2-3 шага можно вообще всю рекурсию не считать, а только смотреть на соседние вершины. Также немного помудрив, можно избавиться от высчитывания множителя в конце второй функции. Но, на такой маленькой матрице эти оптимизации как слону дробина.

Погнали!

Всего по сути у нас есть 3 различных маршрута, остальные можно получить из них вращением, зеркальным отображением относительно главной диагонали и направлением следования (от 1 до 9 и от 9 до 1, см. картинку).

Из одной ячейки можно попасть в 4 соседних, это можно закодировать двумя битами (см. картинку: 00 — влево, 01 — вниз, и т. д.), всего надо сделать 8 шагов, итого один маршрут кодируется 16-битным числом.

Я их вычислил и подписал на картинке. Например, маршрут 1452:

влево (00) => влево (00) => вниз (01) => вниз (01) => вправо (10) => вправо (10) => вверх (11) => влево (00), итого 0000 0101 1010 1100 = 1452

Для маршрута 1680 будет 8, а не 16 уникальных отображений (т. к. маршрут отображается в себя при повороте на 180 градусов), но ради простоты будем генерировать все 16.

Т. е. всего существует 40 маршрутов, мы будем обходить 48, думаю это не критично :)

Что можно с этим сделать?

Заведем структуру, описывающую позицию:

struct Pos
{
    public int X { get; }
    public int Y { get; }
    public Pos(int x, int y)
    {
        X = x;
        Y = y;
    }
    public Pos Move(int code)
    {
        switch (code)
        {
            case 0: return new Pos(X + 1, Y);
            case 1: return new Pos(X, Y + 1);
            case 2: return new Pos(X - 1, Y);
            case 3: return new Pos(X, Y - 1);
        }
        throw new NotSupportedException();
    }
}

В ней также определен метод для перехода в соседнюю клетку по коду направления.

Заведем класс, описывающий путь, это просто контейнер для характеристик:

class WayDescription
{
    public int Way { get; }
    public Pos Start { get; }
    public Pos End { get; }
    public WayDescription(int way, Pos start, Pos end)
    {
        Way = way;
        Start = start;
        End = end;
    }
}

Теперь нам нужен итератор по пути, у него будет 2 реализации: в прямом направлении и в обратном:

abstract class StepEnumerable : IEnumerable<int>
{
    protected readonly WayDescription wd;
    public StepEnumerable(WayDescription wd) => this.wd = wd;
    public abstract Pos Start();
    protected abstract int Next();
    public IEnumerator<int> GetEnumerator()
    {
        for (int i = 0; i < 8; ++i)
            yield return Next();
    }
    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}
class ForwardStepEnumerable : StepEnumerable
{
    private int shift = 16;
    private readonly int way;
    public ForwardStepEnumerable(WayDescription wd) : base(wd) => way = wd.Way;
    public override Pos Start() => wd.Start;
    protected override int Next()
    {
        shift -= 2;
        return (way >> shift) % 4;
    }
}
class ReverseStepEnumerable : StepEnumerable
{
    private int way;
    public ReverseStepEnumerable(WayDescription wd) : base(wd) => way = wd.Way * 4;
    public override Pos Start() => wd.End;
    protected override int Next()
    {
        way /= 4;
        return (way + 2) % 4; // Циклический сдвиг, переводит 00 <=> 10 и 01 <=> 11
    }
}

Также нам потребуется интерпретатор позиции, который будет накладывать на координаты нужные нам преобразования: отображение и вращение.

Базовый класс:

abstract class PosInterpreter
{
    public abstract Pos Translate(Pos pos);
}

Реализации для прямого и зеркального отображения:

class StraightPosInterpreter : PosInterpreter
{
    public override Pos Translate(Pos pos) => pos;
}
class MirrorPosInterpreter : PosInterpreter
{
    public override Pos Translate(Pos pos) => new Pos(pos.Y, pos.X);
}

А также реализация-декоратор, принимающая функцию отображения:

class FuncPosInterpreter : PosInterpreter
{
    private readonly PosInterpreter posInterpreter;
    private readonly Func<Pos, Pos> func;
    public FuncPosInterpreter(PosInterpreter posInterpreter, Func<Pos, Pos> func)
    {
        this.posInterpreter = posInterpreter;
        this.func = func;
    }
    public override Pos Translate(Pos pos) => func(posInterpreter.Translate(pos));
}

Она будет принимать вращающую функцию и интерпретатор для зеркального отображения.

Отлично, всё что нужно у нас есть, осталось создать нужные экземпляры и проитерировать по ним:

static void Main()
{
    // 3 пути
    WayDescription[] wayDescs =
    {
        new WayDescription(1452, new Pos(0, 0), new Pos(1, 1)),
        new WayDescription(1465, new Pos(0, 0), new Pos(0, 2)),
        new WayDescription(1680, new Pos(0, 0), new Pos(2, 2))
    };
    // 2 фабрики итераторов пути
    var stepEnumerableFactories = new Func<WayDescription, StepEnumerable>[]
    {
        wd => new ForwardStepEnumerable(wd),
        wd => new ReverseStepEnumerable(wd)
    };
    // 2 интерпретатора позиции (прямой и зеркальный)
    var smPosInterps = new PosInterpreter[]
    {
        new StraightPosInterpreter(),
        new MirrorPosInterpreter()
    };
    // 4 функции для вращательного отображения координат
    var posFuncs = new Func<Pos, Pos>[]
    {
        pos => pos,
        pos => new Pos(2 - pos.Y, pos.X), // 90 градусов
        pos => new Pos(2 - pos.X, 2 - pos.Y), // 180
        pos => new Pos(pos.Y, 2 - pos.X) // 270
    };
    // Входной массив
    int[,] array = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
    foreach (var wd in wayDescs)
    {
        foreach (var sef in stepEnumerableFactories)
        {
            foreach (var pi in smPosInterps)
            {
                foreach (var f in posFuncs)
                {
                    // Создаем интерпретатор позиции над
                    //  указанным интерпретатором зеркального отображения
                    //  и с указанной функцией вращения
                    var posInterp = new FuncPosInterpreter(pi, f);
                    // Создаем итератор по пути
                    var se = sef(wd);
                    // Начальная позиция
                    var pos = se.Start();
                    // Транслированная начальная позиция
                    var tPos = posInterp.Translate(pos);
                    int x = array[tPos.Y, tPos.X];
                    // Итерируем по шагам пути
                    foreach (var s in se)
                    {
                        // Координаты после шага
                        pos = pos.Move(s);
                        tPos = posInterp.Translate(pos);
                        x = 10 * x + array[tPos.Y, tPos.X];
                    }
                    Console.WriteLine(x);
                }
            }
        }
    }
    Console.ReadLine();
}

Готово! Этот код выводит 48 чисел, максимальное из них выберете самостоятельно.

Загнать всё в одну строку, добавить корневую вершину и получится граф из 10 вершин. Для каждой вершины списки смежности отсортировать в порядке убывания стоящего в целевой вершине значения. На получившемся запустить обыкновенный перебор по аналогии с dfs.

var g = [ 
  [1, 3, 5, 7, 9], 
  [2, 4], 
  [1, 3, 5], 
  [2, 6], 
  [1, 5, 7], 
  [2, 4, 6, 8], 
  [3, 5, 9], 
  [4, 8], 
  [5, 7, 9], 
  [6, 8], 
] 
 
var a = [3, 2, 6, 4, 8, 9, 1, 5, 7] 
var used = [], path = [] 
 
function go(v) { 
  if (path.length === 9) return true 
 
  for (var u of g[v]) { 
    if (!used[u]) { 
      path.push(u) 
      used[u] = true 
      if (go(u)) return true 
      used[u] = false 
      path.pop() 
    } 
  } 
} 
 
for (var x of g) x.sort((x, y) => a[y-1] - a[x-1]) 
go(0) 
 
console.log(path.map(x => a[x-1]).join(""))