How can I optimize my brute-force solution to this problem?

Question

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)?

The problem

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.

Extra details

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.

Answer 1

Integer linear programming

Your problem can be formulated in the following way: we are given vectors $v_{i,j} \in (\mathbb{Z}/N\mathbb{Z})^d$, where the board has $d$ cells, and the goal is, given a vector $c \in (\mathbb{Z}/N\mathbb{Z})^d$, find a function $f$ so that $\sum_i v_{i,f(j)}=c$. This problem could then be solved by integer linear programming. This is related to a $d$-dimensional subset-sum problem, so you might also be able to find other algorithms for multi-dimensional subset-sum and try them out as well.

How do we formulate it in that way? If the grid has $d$ cells, we can think of a shape as a $d$-vector of 0's and 1's, with 1's in the cells covered by the shape. Each shape can be placed in a number of different positions, yielding different vectors. $v_{i,j}$ corresponds to the $j$th place where shape $i$ can be placed. $c$ corresponds to the the numbers originally in the grid (well, the negation of those numbers, modulo $N$). All arithmetic is done modulo $N$.

Slightly smarter brute force

Alternatively, here is a way to improve brute force a little bit, by trading memory for time. Suppose you have $k$ shapes. Start by enumerating all ways to place the first $k/2$ shapes onto an empty board of all zeros, and store all resulting positions in a hashtable or sorted list. Then, enumerate all ways to place the last $k/2$ shapes onto the starting position, and look up each of the resulting positions in the hashtable or sorted list. If you find any match, then that yields a solution. This will let you push brute force a bit further -- potentially to about twice as many shapes -- if you have an unlimited amount of memory. There are a lot of details involved in optimizing this to the max, but it's an idea you could consider if you brute force gets you close but falls a little bit short. It is still an exponential-time algorithm so it will still hit a limit.