I am working on a solution to the problem explained below. I am using brute force, I have reached the point where solutions are prohibitive, so I need to optimize more (if possible). Of course, it will be even better if there is a better way to solve the problem (not brute force).
Is there anything I can do to improve my solution, or reference I can look into (similar problems, etc)?
We start with a rectangular board. Each cell can be in N states, and the initial state for each cell is random (0 <= state < N) for each cell. We also have a number of shapes, all fit inside the board. Every shape is continuous.
Each shape must be placed once (and only once) in the board. When a shape is placed, each cell that belongs to the shape will have its value increased by 1. If the board value in any cell reaches N, it is changed to 0.
The goal is to find the positions each shape must be placed so that the final board has all cells with value 0. There is always at least one solution. Let's suppose the problem is generated by starting from the finished board and applying random shapes in random positions.
The board size, number of states N and number of shapes are the setup of the game, and keep increasing (at different rates) for each 'level'.
What I am doing currently
I am able to solve the problem up to a certain size by just using brute force. I have a few optimisations in place. I have reached a point where the solution is prohibitive, so I would like to improve my logic.
First thing I am doing is order the shape from larger to smaller, the smaller will be moved in the internal iterations. The assumption (which I haven't proved, but tested to be faster) is that it's better to move the smaller shapes more, since they have a higher chance to generate a solution.
Secondly, for repeated shapes, I avoid checking all the permutations, since they yield the same result. I also only check one set of positions when a pair of same shapes overlap (since all overlaps yield the same result).
One final optimisation that I think will help a lot, but I am still implementing is: at each shape in the sequence, count the total of cells in the shapes that remain to be moved. This number, minus the total cell flips needed to get a finished board, must be a multiple of N. If not, it's no point brute forcing the remaining shapes positions, and we must re-position a shape in an external loop.
I am interested in any other tips on how to optimize this. Known algorithms, even a good naming for this set of problem, that I can use to research more would be great.