Help with problem solving algorithm

It seems not difficult. I have 3 ideas:

1. The beginning of the walk can be either from the middle or from the corners of the array.
2. It is necessary to start in any case with an element with a large value, since you can always dial a number of length 9 digits, where the largest of the available digits should be at the beginning
3. The rest of the passage - the usual deep search

I did something like this

 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; } 

Checked like this

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

Conclusion

 987456321 

I think that in order to speed up, you can try to cut off the short paths (which do not give 9 digits) + the first 2-3 steps can generally not be considered the whole recursion, but just look at the neighboring peaks. Also a little wisely, you can get rid of the calculation of the multiplier at the end of the second function. But, on such a small matrix, these optimizations are like an elephant's pellet.

Let's go!

In total, we have 3 different routes, the rest can be obtained from them by rotating, mirroring the main diagonal and the direction of following (from 1 to 9 and from 9 to 1, see the picture).

From one cell you can get to 4 neighboring ones, it can be encoded with two bits (see picture: 00 - to the left, 01 - down, etc.), all you need to do is 8 steps, totaling one route is encoded with a 16-bit number.

I figured them out and signed them in the picture. For example, route 1452:

left (00) => left (00) => down (01) => down (01) => right (10) => right (10) => up (11) => left (00), total 0000 0101 1010 1100 = 1452

For route 1680, there will be 8, not 16 unique mappings (since the route is mapped to itself when rotated 180 degrees), but for the sake of simplicity we will generate all 16.

That is, there are 40 routes in total, we will bypass 48, I think this is not critical :)

What can you do about it?

Let's get the structure describing the position:

 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(); } } 

It also defines a method for moving to the next cell using the direction code.

Let's get a class describing the path, it's just a container for the characteristics:

 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; } } 

Now we need an iterator along the way, it will have 2 implementations: in the forward direction and in the opposite direction:

 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 } } 

We also need a position interpreter, which will impose the necessary transformations on the coordinates: mapping and rotation.

Base class:

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

Implementations for direct and mirror image:

 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); } 

As well as the implementation-decorator that accepts the display function:

 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)); } 

It will assume a rotating function and an interpreter for mirroring.

Great, we have everything we need, it remains to create the necessary instances and iterate on them:

 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(); } 

Done! This code displays 48 numbers, choose the maximum of them yourself.

Drive everything into one line, add a root vertex and you get a graph of 10 vertices. For each vertex, adjacency lists should be sorted in descending order of the value at the target vertex. On the resulting run, brute force will be used by analogy with 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(""))