Copyright (c) 2014 Bart Massey

This is a simple polyomino solver in C using depth-first search. I thought it would be nice for playing The Talos Principle and existing solutions seemed fiddly and complicated.

The program should compile pretty easily on most anything.

Polyominoer takes two arguments:

• First is a rectangular board dimension to be filled, in the format rowsxcolumns, e.g. 4x2. The max board size is currently pretty limited. While this would be easy to change, the search is also currently pretty inefficient; some efficiency improvements would be easy also.

  Of course, the board size in the current implementation should be the number of tiles times four, or it is impossible to tile.

• Next is a tile string. Each character in the tile string represents a polyomino to be tiled. The tile name characters are as follows:

         I) ####
  
             ##
         5) ##
  
            ##
         2)  ##
  
         T) ###
             #
  
              #
         L) ###
  
         P) ###
              #
  
         O) ##
            ##
  

  The names were chosen to be as mnemonic as possible. Note that the board is untileable unless the number of T tiles is even (because of a parity consideration): this is checked up front.

An example usage is:

        polyominoer 4x7 LP22TTI

which currently produces for me the output:

        bbcceee
        bddccea
        bfddaaa
        fffgggg

A larger example:

        polyominoer 6x8 OOI22TTLLPPP

with current output:

        aabbcccc
        aabbddde
        fffkhdee
        flkkhhhe
        llkgijjj
        lgggiiij

The output has each piece given a letter, in the order that they were specified in the tile string.

The code is not currently commented, which is kind of sad and reasonably easy to fix.

The program is currently limited to tetrominoes, since Tetris pieces are all I currently need, which is also kind of sad and reasonably easy to fix.

The current search has minimal pruning. It is currently highly sensitive to the ordering of the tile string. Running the example above as

        polyominoer 6x8 TTLLPPP22IOO

currently requires 1.5 minutes on my machine. This should be fixed, probably by completely restructuring the search, but I'm lazy. A good general rule is to specify pieces from most to least rotational asymmetries. The number of asymmetries for the various pieces (perhaps obviously) is:

        1) O
        2) I52
        4) TLP

This program is licensed under the "MIT License". Please see the file COPYING in the source distribution of this software for license terms.