I'M looking for an algorithm (preferably polynomial) for the following problem:Input:- an M x N grid, where each square can be either empty or occupied- a list of items- a list of constraints  Output: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:111001011011010and so forth. Example 2:Given 3 x 5 grid and 2 items of lengths 1, 2 respectively. The following solutions are acceptable:001101000000000110001000000000etc.Possible constraints:a. Isolation - items may not touch each other. e.g. the following solutions is illegal:Example 1:11100Example 2:110001000000000However this is a legal solution:011001000000000i.e. touching diagonals are legal.b. Facing - 2 items must be placed one in front of the other. e.g.110000000011000  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.
Placing 1d items in a 2d grid with constraints
algorithms;search algorithms