<h1>Integer linear programming</h1>
<p>Your problem can be formulated in the following way: we are given vectors <span class="math-container">$v_{i,j} \in (\mathbb{Z}/N\mathbb{Z})^d$</span>, where the board has <span class="math-container">$d$</span> cells, and the goal is, given a vector <span class="math-container">$c \in (\mathbb{Z}/N\mathbb{Z})^d$</span>, find a function <span class="math-container">$f$</span> so that <span class="math-container">$\sum_i v_{i,f(j)}=c$</span>.  This problem could then be solved by integer linear programming.  This is related to a <span class="math-container">$d$</span>-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.</p>
<p>How do we formulate it in that way?  If the grid has <span class="math-container">$d$</span> cells, we can think of a shape as a <span class="math-container">$d$</span>-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.  <span class="math-container">$v_{i,j}$</span> corresponds to the <span class="math-container">$j$</span>th place where shape <span class="math-container">$i$</span> can be placed.  <span class="math-container">$c$</span> corresponds to the the numbers originally in the grid (well, the negation of those numbers, modulo <span class="math-container">$N$</span>).  All arithmetic is done modulo <span class="math-container">$N$</span>.</p>
<h1>Slightly smarter brute force</h1>
<p>Alternatively, here is a way to improve brute force a little bit, by trading memory for time.  Suppose you have <span class="math-container">$k$</span> shapes.  Start by enumerating all ways to place the first <span class="math-container">$k/2$</span> 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 <span class="math-container">$k/2$</span> 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.</p>

CC BY-SA 4.0
2020-08-18T14:21:31.073Z
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?
RSinohara
CC BY-SA 4.0
2020-08-18T14:29:30.843Z
And the fact that there cannot be a solution where the positions are not integers?
RSinohara
CC BY-SA 4.0
2020-08-18T19:02:22.957Z
@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.
D.W.
CC BY-SA 4.0
2020-08-19T00:53:02.473Z
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.
Neal Young
CC BY-SA 4.0
2020-08-19T02:38:27.570Z
@NealYoung, it's ugly: I'd model $x \equiv y \pmod N$ as $x=y+kN$ where $k$ is a new integer variable.
D.W.
CC BY-SA 4.0
2020-08-20T07:18:05.937Z
Nice. I will try solving the LP, thanks very much for the tips :)
RSinohara
CC BY-SA 4.0
2020-08-20T13:11:55.170Z
@D.W. The number of each shape is not a variable, it's always one. But I see now the positions could end up fractional for complementary shapes :/
RSinohara
CC BY-SA 4.0
2020-08-18T08:50:56.523Z
2020-08-18T19:06:15.120Z
2020-08-18T19:06:15.120Z
D.W.
<p>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).</p>
<p>Is there anything I can do to improve my solution, or reference I can look into (similar problems, etc)?</p>
<h2>The problem</h2>
<p>We start with a rectangular board. Each cell can be in N states, and the initial state for each cell is random (0 &lt;= state &lt; N) for each cell.
We also have a number of shapes, all fit inside the board. Every shape is continuous.</p>
<p><a href="https://i.sstatic.net/wTPWk.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/wTPWk.png" alt="example" /></a></p>
<p>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.</p>
<p>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.</p>
<p><a href="https://i.sstatic.net/aatFX.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/aatFX.png" alt="enter image description here" /></a></p>
<p>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'.</p>
<h2>What I am doing currently</h2>
<p>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.</p>
<p>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.</p>
<p>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).</p>
<p>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.</p>
<h2>Extra details</h2>
<p>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.</p>

CC BY-SA 4.0
2020-08-16T22:38:40.693Z
Can the shapes be rotated or flipped?
Neal Young
CC BY-SA 4.0
2020-08-17T00:44:56.767Z
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](https://en.wikipedia.org/wiki/Eternity_puzzle) was solved.
Neal Young
CC BY-SA 4.0
2020-08-17T12:22:38.227Z
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.](https://scholar.google.com/scholar?cluster=13408445163941264577&hl=en&as_sdt=1,22).
Neal Young
CC BY-SA 4.0
2020-08-17T12:26:32.923Z
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.
Neal Young
CC BY-SA 4.0
2020-08-17T18:06:30.787Z
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.
RSinohara
CC BY-SA 4.0
2020-08-18T00:48:57.980Z
One last comment -- you could formulate your problem as an integer linear program, and solve it using a commercial solver such as Gurobi, if you have access to one.  Otherwise you could try a public-domain solver such as GLPK or LPSolve.
Neal Young
CC BY-SA 4.0
2020-08-18T05:39:53.477Z
Wow, that is nice. I hadn't thought of that. I happen to be familiar with LP, so I think I can also give it a go!
RSinohara
CC BY-SA 4.0
2020-08-18T22:32:43.810Z
I would also try to model the problem using [MiniZinc](https://www.minizinc.org/) which is a very powerful constraint modeling language and check if the instances you cannot solve with your algorithm/implementation are handled easily by MiniZinc. Then I would try to add some optimizations and simmetry breaking constraints.
Marzio De Biasi
<ds.algorithms>
How can I optimize my brute-force solution to this problem?
RSinohara
# How can I optimize my brute-force solution to this problem?

(Asked by: username_0 on 2020-08-16)

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](https://i.sstatic.net/wTPWk.png)](https://i.sstatic.net/wTPWk.png)

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](https://i.sstatic.net/aatFX.png)](https://i.sstatic.net/aatFX.png)

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.

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: Can the shapes be rotated or flipped?  
> **username_1**: 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](https://en.wikipedia.org/wiki/Eternity_puzzle) was solved.  
> **username_1**: 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.](https://scholar.google.com/scholar?cluster=13408445163941264577&hl=en&as_sdt=1,22).  
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: One last comment -- you could formulate your problem as an integer linear program, and solve it using a commercial solver such as Gurobi, if you have access to one.  Otherwise you could try a public-domain solver such as GLPK or LPSolve.  
> **username_0**: Wow, that is nice. I hadn't thought of that. I happen to be familiar with LP, so I think I can also give it a go!  
> **username_2**: I would also try to model the problem using [MiniZinc](https://www.minizinc.org/) which is a very powerful constraint modeling language and check if the instances you cannot solve with your algorithm/implementation are handled easily by MiniZinc. Then I would try to add some optimizations and simmetry breaking constraints.  

---

## 1 answers

### Answer by username_3 on 2020-08-18. Score: 2

# 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.

> **Comments:**
> **username_0**: 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?  
> **username_0**: And the fact that there cannot be a solution where the positions are not integers?  
> **username_3**: @username_0, 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.  
> **username_1**: 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.  
> **username_3**: @NealYoung, it's ugly: I'd model $x \equiv y \pmod N$ as $x=y+kN$ where $k$ is a new integer variable.  
> **username_0**: Nice. I will try solving the LP, thanks very much for the tips :)  
> **username_0**: @username_3 The number of each shape is not a variable, it's always one. But I see now the positions could end up fractional for complementary shapes :/  

---

