I'M looking for an algorithm (preferably polynomial) for the following problem:
- an M x N grid, where each square can be either empty or occupied
- a list of items
- a list of constraints
the grid, such that all items are placed and the constraints aren't violated.
Each item is a 1d block of length k. Different items may have different length, and there may be several items with the same length. Items can't ovelap each other.
Example 1: Given 1 x 5 grid and 2 items of lengths 1, 2 respectively. The following solutions are acceptable:
and so forth.
Example 2: Given 3 x 5 grid and 2 items of lengths 1, 2 respectively. The following solutions are acceptable:
a. Isolation - items may not touch each other. e.g. the following solutions is illegal:
However this is a legal solution:
i.e. touching diagonals are legal.
b. Facing - 2 items must be placed one in front of the other. e.g.
What I did so far is to find a solution for a simpler problem, where the grid is 1d and the only possible constraint is Isolation. I solved it by representing it as a search problem, and using A* with the heuristic: sum of lengths of items not placed yet. The problem is that it suffers from state explosion which will only deteriorate in higher dimensions.