title: Modelling Conway's game of life in integer linear programming?
body: <p>I'm trying to model <a href="https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life" rel="nofollow">Conway's game of life</a> rules using integer linear programming, however I'm stuck with one of the rules.</p>
  
  <p>I consider a <em>finite</em> <code>n x n</code> grid. Each cell in the grid is associated with a variable <code>X(i,j)</code> whose value is <code>0</code> if the cell is dead and <code>1</code> if it is alive.</p>
  
  <p>I'm particularly interested in <em>still lifes</em>, i.e. configurations that, according to the rules, don't change from an instant to the next.</p>
  
  <p>To find them I'm imposing the constraints on the number of neighbours for each cell. So, for an alive cell to remain still it must have <code>2</code> or <code>3</code> neighbours, and this is easily expressible:</p>
  
  <pre><code>2(1-X(i,j)) + Σ(i,j) &gt;= 2
  
  -5(1 - X(i,j)) + Σ(i,j) &lt;= 3
  </code></pre>
  
  <p>Where <code>Σ(i, j)</code> is the sum over the neighbours of <code>(i, j)</code> (assume outside of the grid the values are all <code>0</code>s).</p>
  
  <p>If <code>X(i,j) == 0</code> then the first addend guarantees that the the constraints are trivially satisfied. When <code>X(i, j) == 1</code> the constraints guarantee that we have a still life.</p>
  
  <p>The problem is the other rule: for a dead cell to remain dead it must have any number of neighbours different from <code>3</code>.
  However, AFAIK you cannot use <code>!=</code> in a constraint.</p>
  
  <p>The closest I've come is:</p>
  
  <pre><code>X(i, j) + |Σ(i, j) - 3| &gt; 0
  </code></pre>
  
  <p>Which does express what I want, but the problem is that I don't think the absolute value can be used in that way (only absolute values of single variables can be expressed. Or is there a way to express this particular situation?).</p>
  
  <p>I wonder, is there a standard way to express the <code>!=</code>?
  I was thinking that maybe I should use multiple inequalities instead of a single one (e.g. for every possible triple/quadruple of neighbours...), but I cannot think of any sensible way to achieve that.</p>
  
  <p>Or maybe there is some way of abusing the optimization function to penalize this situation and thus, obtaining an optimum would yield a correct solution (or state that it's impossible, depending on the value).</p>
  
  <p>Is anyone able to express that constraint using a <em>linear</em> inequality and the variables <code>X(i, j)</code> (plus, eventually, some new variables)?</p>