maximise the special elements in the matrix

Question

Below is a problem statement:

There is a matrix of size m*n and all numbers from 1 to m*n occupy a place in it. Now, an element is called special if(recursive definition)

-it is the top left corner element(at position (0,0)) 
-an element at (x,y) is special if its neighbour is an element (m,n) such that (m,n) is    
 special and the element at (x,y) is greater than the element at(m,n) and all of the (m,n)'s neighbours.

A neighbour to a cell is the cell which shares an edge with it. Therefore, an internal cell has 4 neighbours, edge cell has 3 neighbours and corner cell has 2 neighbours.

The problem states that only a few(maybe 0) cells in the matrix have been filled. The rest are to be filled in such a way that all numbers from 1 to m*n are used and we maximise the number of special elements. Also, if multiple answers are possible, the lexicographically smallest matrix would be considered as the answer.

A matrix is lexicographically smaller that the other if the string of its row-major view is lexicographically smaller than the other.

Test case 1: //2 X 3 matrix
2 ? ? 
? ? 3 

Solution 1:
2 1 4 
5 6 3 

Test case 2: //6 X 6 matrix
? ? ? ? ? ? 
? ? ? ? ? ? 
? ? ? ? ? ? 
? ? ? ? ? ? 
? ? ? ? ? ? 
? ? ? ? ? ? 

Solution 2:
 1  2  3 13 14 15 
 4  6  8 10 11 16 
 5  7  9 12 19 17 
28 26 24 22 20 18 
29 27 25 23 21 36 
30 31 32 33 34 35

My logic: The special elements in the matrix are always contiguous. So, we have to find out the longest such path formed by joining special elements which are contiguous. Also, before placing an element at a neighbouring cell (x,y) of a special element(m,n), we first fill out all the neighbours(except (x,y)) of the special element(m,n) and then choose a value greater than all of them to fill (x,y).

I don't know how to proceed forward and how to include the lexicographically smallest condition. Please help.

Thanks in advance.

Answer 1

The best solution is to find an algorithm to solve the problem, and prove it correct. Lacking that, there are some more options.

Backtracking

This is a combinatorial problem, which you can solve with backtracking. The key points you need to successfully implement a backtracking algorithm to solve the problem are:

1. Find a good heuristic for the next step
2. Find a good early stopping heuristic, branch and bound

I would solve it like this:

• Find all possible places where the next special element can be placed. There won't be many such places, as you pointed out already.
• Select all possible combinations of values that can be used to add the next special value, regardless of next steps in the backtracking. Keep track of which numbers are still to be placed and which are "usual" and special values on every step (either by using recursion or by creating a tailored data model). The rest of the matrix can be left empty (or 0), to be filled further in the backtracking. Sort the possibilities so that they provide for lexicographically smaller solutions first. Try out all viable possibilities.
• If no special values are left to place, fill the empty spots in the matrix in lexicographic order, which was also a requirement.

Early stopping can be done when you're placing the k th special value i, so that you will never be able to do better than your current best solution. Of course you must also stop with a branch when no more special values can be added. Creating an initial solution like you proposed would be a good start, and allow for much more branch cutting than with a cold start.

Or maybe with a little guesswork...

Maybe backtracking will be too slow, even if optimized, because it tries to find all possible solutions. An alternative is to use a heuristic algorithm, like genetic algorithms, tabu search, variable neighborhood search, simulated annealing, ...

Such algorithms may find a viable solution quickly, but on the downside, that solution may not be the optimal one.