title: Programming Contest Question: Counting Polyominos
body: <p><strong>Please see my own answer, I think I did it!</strong></p>
  
  <hr>
  
  <p>Hi,</p>
  
  <p>An example question for a programming contest was to write a program that finds out how much polyominos are possible with a given number of stones.</p>
  
  <p>So for two stones (<code>n = 2</code>) there is only one polyominos:</p>
  
  <pre><code>XX
  </code></pre>
  
  <p>You might think this is a second solution:</p>
  
  <pre><code>X
  X
  </code></pre>
  
  <p>But it isn't. The polyominos are not unique if you can rotate them.</p>
  
  <p>So, for 4 stones (<code>n = 4</code>), there are 7 solutions:</p>
  
  <pre><code>X
  X   XX   X    X     X   X
  X   X    XX   X    XX   XX   XX
  X   X    X    XX   X     X   XX
  </code></pre>
  
  <p>The application has to be able to find the solution for <code>1 &lt;= n &lt;=10</code></p>
  
  <p>PS: Using the <a href="http://en.wikipedia.org/wiki/Polyomino#Enumeration_of_polyominoes" rel="noreferrer">list of polyominos on Wikipedia</a> isn't allowed ;)</p>
  
  <p>EDIT: Of course the question is: How to do this in Java, C/C++, C#</p>
  
  <hr>
  
  <p>I started this project in Java. But then I had to admit I didn't know how to build polyominos using an efficient algorithm.</p>
  
  <p>This is what I had so far:</p>
  
  <pre><code>import java.util.ArrayList;
  import java.util.List;
  
  
  public class Main
  {
  
      private int countPolyminos(int n)
      {
          hashes.clear();
          count = 0;
          boolean[][] matrix = new boolean[n][n];
          createPolyominos(matrix, n);
          return count;
      }
  
      private List&lt;Integer&gt; hashes = new ArrayList&lt;Integer&gt;();
      private int count;
  
      private void createPolyominos(boolean[][] matrix, int n)
      {
          if (n == 0)
          {
              boolean[][] cropped = cropMatrix(matrix); 
              int hash = hashMatrixOrientationIndependent(matrix);
              if (!hashes.contains(hash))
              {
                  count++;
                  hashes.add(hash);
              }
              return;
          }
      // Here is the real trouble!!
      // Then here something like; createPolyominos(matrix, n-1);
      // But, we need to keep in mind that the polyominos can have ramifications
      }
  
      public boolean[][] copy(boolean[][] matrix)
      {
          boolean[][] b = new boolean[matrix.length][matrix[0].length];
          for (int i = 0; i &lt; matrix.length; ++i)
          {
              System.arraycopy(matrix[i], 0, b, 0, matrix[i].length);
          }
          return b;
      }
  
      public boolean[][] cropMatrix(boolean[][] matrix)
      {
          int l = 0, t = 0, r = 0, b = 0;
          // Left
          left: for (int x = 0; x &lt; matrix.length; ++x)
          {
              for (int y = 0; y &lt; matrix[x].length; ++y)
              {
                  if (matrix[x][y])
                  {
                      break left;
                  }
              }
              l++;
          }
          // Right
          right: for (int x = matrix.length - 1; x &gt;= 0; --x)
          {
              for (int y = 0; y &lt; matrix[x].length; ++y)
              {
                  if (matrix[x][y])
                  {
                      break right;
                  }
              }
              r++;
          }
          // Top
          top: for (int y = 0; y &lt; matrix[0].length; ++y)
          {
              for (int x = 0; x &lt; matrix.length; ++x)
              {
                  if (matrix[x][y])
                  {
                      break top;
                  }
              }
              t++;
          }
          // Bottom
          bottom: for (int y = matrix[0].length; y &gt;= 0; --y)
          {
              for (int x = 0; x &lt; matrix.length; ++x)
              {
                  if (matrix[x][y])
                  {
                      break bottom;
                  }
              }
              b++;
          }
  
          // Perform the real crop
          boolean[][] cropped = new boolean[matrix.length - l - r][matrix[0].length - t - b];
          for (int x = l; x &lt; matrix.length - r; ++x)
          {
              System.arraycopy(matrix[x - l], t, cropped, 0, matrix[x].length - t - b);
          }
          return cropped;
      }
  
      public int hashMatrix(boolean[][] matrix)
      {
          int hash = 0;
          for (int x = 0; x &lt; matrix.length; ++x)
          {
              for (int y = 0; y &lt; matrix[x].length; ++y)
              {
                  hash += matrix[x][y] ? (((x + 7) &lt;&lt; 4) * ((y + 3) &lt;&lt; 6) * 31) : ((((x+5) &lt;&lt; 9) * (((y + x) + 18) &lt;&lt; 7) * 53));
              }
          }
          return hash;
      }
  
      public int hashMatrixOrientationIndependent(boolean[][] matrix)
      {
          int hash = 0;
          hash += hashMatrix(matrix);
          for (int i = 0; i &lt; 3; ++i)
          {
              matrix = rotateMatrixLeft(matrix);
              hash += hashMatrix(matrix);
          }
          return hash;
      }
  
      public boolean[][] rotateMatrixRight(boolean[][] matrix)
      {
          /* W and H are already swapped */
          int w = matrix.length;
          int h = matrix[0].length;
          boolean[][] ret = new boolean[h][w];
          for (int i = 0; i &lt; h; ++i)
          {
              for (int j = 0; j &lt; w; ++j)
              {
                  ret[i][j] = matrix[w - j - 1][i];
              }
          }
          return ret;
      }
  
      public boolean[][] rotateMatrixLeft(boolean[][] matrix)
      {
          /* W and H are already swapped */
          int w = matrix.length;
          int h = matrix[0].length;
          boolean[][] ret = new boolean[h][w];
          for (int i = 0; i &lt; h; ++i)
          {
              for (int j = 0; j &lt; w; ++j)
              {
                  ret[i][j] = matrix[j][h - i - 1];
              }
          }
          return ret;
      }
  
  }
  </code></pre>