3
$\begingroup$

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.

example

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.

enter image description here

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.

$\endgroup$
8
  • 2
    $\begingroup$ Can the shapes be rotated or flipped? $\endgroup$
    – Neal Young
    Aug 16, 2020 at 22:38
  • 3
    $\begingroup$ This forum is for theoretical CS. A question that just asks how to optimize a brute-force exhaustive search might not be appropriate for this site. Maybe cs.stackexchange.com. Or maybe recast your question so that it might fit better. (i) Make the question ask for either a poly-time algorithm (for a general statement of your problem) or an NP-hardness proof. Or (ii) somehow relate it to SAT solvers or other constraint-programming research. Meanwhile, you might get something out of reading about how the Eternity Puzzle was solved. $\endgroup$
    – Neal Young
    Aug 17, 2020 at 0:44
  • 2
    $\begingroup$ Almost surely your problem is NP-complete, even when N=2 and the number of 1's in the initial position equals the total area of the pieces (so the pieces have to exactly cover the 1's). I'm sure you can show this by a reduction from a problem called Bounded Tiling. See e.g. Savelsbergh, Martin WP, and Peter van Emde Boas. BOUNDED TILING, an alternative to SATISFIABILITY?. Centrum voor Wiskunde en Informatica, 1984.. $\endgroup$
    – Neal Young
    Aug 17, 2020 at 12:22
  • $\begingroup$ If indeed you are interested in random instances, the problem might be easier, depending on the input distribution. If you are, then I suggest editing your post to define the input distribution exactly -- describe exactly how the set of pieces that define your instance are randomly generated, and exactly how they are randomly placed. $\endgroup$
    – Neal Young
    Aug 17, 2020 at 12:26
  • 1
    $\begingroup$ Thanks @NealYoung, you gave me a lot to go on. I will see if I can improve this, or post in another site once I progress more. $\endgroup$
    – RSinohara
    Aug 17, 2020 at 18:06

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ I have a question that will probably show my tenuous grasp on LP: since we are not optimising, but reaching a specific stage (and we know the state is feasible), does it need to be solved as an -integer- linear program? $\endgroup$
    – RSinohara
    Aug 18, 2020 at 14:21
  • $\begingroup$ And the fact that there cannot be a solution where the positions are not integers? $\endgroup$
    – RSinohara
    Aug 18, 2020 at 14:29
  • $\begingroup$ @RSinohara, yup, it needs to be an integer linear solution; fractional solutions to the linear program don't translate into solutions to your original problem (for instance, you can't add 1/3 of a shape). Also, I edited my answer to add a bonus algorithm. $\endgroup$
    – D.W.
    Aug 18, 2020 at 19:02
  • $\begingroup$ Can you elaborate on how you would do arithmetic mod N in your integer linear program? I can see one way, but I'm curious what you have in mind. Thanks. $\endgroup$
    – Neal Young
    Aug 19, 2020 at 0:53
  • $\begingroup$ @NealYoung, it's ugly: I'd model $x \equiv y \pmod N$ as $x=y+kN$ where $k$ is a new integer variable. $\endgroup$
    – D.W.
    Aug 19, 2020 at 2:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.