I have to put some objects in a matrix. The data of these objects is given in another matrix in which each line contains an object, and the first column represents its width, and the second its height. I want to know which is the smallest matrix that can contain all these objects, with the following rule: objects can't be adjacent to each other, except for diagonals. See the following example:
|1 3|
|1 2|
In this case, we need to populate the main matrix with two objects: one that is 1x3 units in the main matrix, and another that is 1x2. One possible example to fill it would be (not the smallest possible):
|x x x o|
|o o o x|
|o o o x|
|o o o o|
This following example is incorrect:
|x x x o|
|o x o o|
|o x o o|
|o o o o|
Because two objects collide. In this example, the answer would be the size of the smallest possible matrix in which all objects can fit; that is:
|x o o|
|x o x|
|x o x|
The answer would be 3. So I want a function that receives the first matrix ([[1,3], [1,2]]) and returns 3.
I've tried for some time to do this, but it seems impossible to me. I don't know much of matrixes beyond determinants, and I see no way in which what I know relates to this. I think the main problem is that the ship may create an exclusive area, but only if it is not in the corners (and two or more ships may share the same area). I made a program that would try all possibilities and choose the smallest one, but it takes forever to do it for the amount of data I have. So, I was wondering, is there another way, purely mathematical (without testing everything)?
The short answer is that you cannot (theoretically) do much better than brute force searching. While I do not have a proof, I would be extremely surprised if this problem is not NP-complete. Your problem is closely related to rectangle packing, a well studied problem.
Your best option would be to use a combinatorial search system, based on either SAT or Constraint Programming.These systems still do possibly exponential search, but have many tricks and heuristics to improve performance in practice.
I work on the minion constraint solver minion. How big are your biggest problems? I could give some guidance on how achievable they are.