title: Representing map constraints as a ADT
body: <p>Here's a toy problem:</p>
  
  <p>A (roguelike) 2D map consists of square cells which each have a material (rock or air).</p>
  
  <p>Each cell has four boundaries (N, S, E and W). Each boundary is shared by two cells.</p>
  
  <p>A boundary can optionally contain a "wall feature" only if one side is rock and the other air.</p>
  
  <p>(Wall features could be levers, pictures, buttons, etc.)</p>
  
  <p>What Algebraic Data Type design could have a place to store a wall feature only when one side is rock and the other air? i.e. the data structure cannot represent a wall feature on a boundary between two air cells or two rock cells.</p>
  
  <p>One approach I've tried is XORing a chess-board pattern over the cell values, reversing changes and non-changed.</p>
  
  <p>I keep getting myself in knots over the fact there are multiple equivalent routes between cells - SSW is the same as SWS (the 1D version of this question is trivial).  </p>
  
  <p>(I recognise that the ADT representation will not be particularly 'queriable'.)</p>
  
  <hr>
  
  <p>Update with Failed Attempt:</p>
  
  <p>Call the East boundaries E and the South boundaries S.  Let each boundary be either <code>Same</code> or <code>Diff Feature</code>.  The problem with this approach is that it lets inconsistent routes exist, such as:</p>
  
  <pre><code>E&lt;0,0&gt; Same
  S&lt;1,0&gt; Same
  S&lt;0,0&gt; Same
  E&lt;0,1&gt; Diff
  </code></pre>
  
  <p>Is there a mathematical name for saying that different routes must aggregate to the same total?</p>
  
  <p>You could say that Same was 1 and Diff was -1 and that product along every route between any two cells must be equal (either 1 or -1).  </p>