Here's a somewhat hacky, tricky-to-use modification to my dominoes program.

It allows you to search for gadgets with certain truth tables.


Say you want the following truth table:

Truth table with 3 variables:
xyz [is max possible, with given squares removed]
000 1 //no squares removed (max always possible)
001 1
010 1
011 1
100 1
101 0
110 0
111 0

The value of the truth table is 00011111 in binary, 15 in decimal.

So, we'll design a board template and call Board::FindTruthTable( 15 ).

Let's say we want to search a symmetrical design.  Our board template may look like this:


y****A****z
   IEBEI
   JFCFJ
   KGDGK
   LHxHL


Now, Board::FindTruthTable() will replace all capital letters ('A' to 'Z') with either ' ' or '*'.  All settings will be tried.  For the example above, 2^12 settings will be tried.  All the gadgets generated with the requested truth table will be printed out.






// Dominoes helper -- by Tom Sirgedas
// Freeware
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include <algorithm>
#include <map>
#include <sstream>

#define ARR_SIZE(x) int(sizeof(x)/sizeof((x)[0]))

using namespace std;

class Board
{
public:
   Board() {}
   Board( int sizeX, int sizeY ) { _m = vector<string>( sizeY, string( sizeX, ' ' ) ); }
   Board( const string& filename ) { Load( filename ); }
   void Clear() { _m.clear(); }
   void Load( const string& filename )
   {
      Clear();

      ifstream f( filename.c_str() );
      if ( f.fail() )
      {
         cerr << "Error loading '" << filename << "'." << endl;
         cerr << endl;
         cerr << "Syntax Example:  dominoes.exe mymap.txt" << endl;
         exit( 1 );
      }
      char buf[1024];
      int maxWidth = 0;
      while ( f.getline( buf, sizeof(buf) ) )
      {
         _m.push_back( buf );
         maxWidth = max( maxWidth, (int)_m.back().length() );
      }
      for ( int y = 0; y < SizeY(); y++ )
         _m[y] = _m[y] + string( maxWidth - _m[y].length(), ' ' );

      findTileVariables();
   }
   string Str() const
   {
      string ret;
      for ( int y = 0; y < SizeY(); y++ )
         ret += _m[y] + "\n";
      return ret;
   }
   int SizeX() const { return _m.size() ? _m[0].length() : 0; }
   int SizeY() const { return _m.size(); }
   const string& operator[]( int row ) const { return _m[row]; }
   string& operator[]( int row ) { return _m[row]; }

   int Max1x3Tiles() const;
   Board GenerateLayout() const;
   int NumVariables() const { return (int)_TileVariables.size(); }
   void SetVariables( int b ) // bitflags
   {
      int idx = NumVariables() - 1;
      for ( map<char,pair<int,int> >::iterator it = _TileVariables.begin(); it != _TileVariables.end(); it++, idx-- )
      {
         int x = (*it).second.first;
         int y = (*it).second.second;
         _m[y][x] = b & (1<<idx) ? ' ' : '*';
      }
   }
   string Num( int x ) const { stringstream ss; ss << x; return ss.str(); }
   int TruthTableInt() const
   {
      int ret = 0;
      Board board = *this;
      // for each row of the table...
      int maxTiles = Max1x3Tiles();
      for ( int b = 0; b < (1<<NumVariables()); b++ )
      {
         board.SetVariables( b );
         int maxTilesForTheseVariables = board.Max1x3Tiles();
         bool maxStillPossible = maxTilesForTheseVariables == maxTiles;
         ret += maxStillPossible << b;
      }
      return ret;
   }
   string TruthTable() const
   {
      if ( NumVariables() < 1 )
         return "No truth table (no variables found!)";
      if ( NumVariables() > 6 )
         return "Too many variables for truth table";

      int maxTiles = Max1x3Tiles();
      Board board = *this;

      string ret;
      ret += "Truth table with " + Num( NumVariables() ) + " variables:\n";
      for ( map<char,pair<int,int> >::const_iterator it = _TileVariables.begin(); it != _TileVariables.end(); it++ )
      {
         char c = (*it).first;
         ret += c;
      }
      ret += " [is max possible, with given squares removed]\n";

      // for each row of the table...
      for ( int b = 0; b < (1<<NumVariables()); b++ )
      {
         board.SetVariables( b );
         for ( int i = board.NumVariables()-1; i >= 0; i-- )
            ret += b & (1<<i) ? "1" : "0";
         int maxTilesForTheseVariables = board.Max1x3Tiles();
         bool maxStillPossible = maxTilesForTheseVariables == maxTiles;
         ret += string(" ") + ( maxStillPossible? "1" : "0" );
         if ( b == 0 )
            ret += " //no squares removed (max always possible)";
         ret += "\n";
      }
      return ret;
   }
   void FindTruthTable( int targetTruthTableInt ) const
   {
      int numDigits = 0;
      for ( int y = 0; y < SizeY(); y++ )
      for ( int x = 0; x < SizeX(); x++ )
         if ( isupper( _m[y][x] ) )
            numDigits = max(numDigits,_m[y][x] - 'A' + 1);

      for ( int b = 0; b < (1<<numDigits); b++ )
      {
         if ( b && (b%1000) == 0 )
            cout << b << "/" << (1<<numDigits) << endl;
         Board board = *this;
         for ( int y = 0; y < SizeY(); y++ )
         for ( int x = 0; x < SizeX(); x++ )
            if ( isupper( _m[y][x] ) )
               board._m[y][x] = b & (1<<(_m[y][x]-'A')) ? '*' : ' ';
         board.findTileVariables();

         //cout << board.TruthTableInt() << endl;
         //cout << board.Str() << board.TruthTableInt() << endl;
         if ( board.TruthTableInt() == targetTruthTableInt )
         {
            cout << board.Str() << endl;
            cout << board.TruthTable() << endl;
            cout << endl;
            cout << endl;
         }
      }
   }

private:
   void findTileVariables()
   {
      _TileVariables.clear();
      map<char, int> letterCount;

      for ( int y = 0; y < SizeY(); y++ )
      for ( int x = 0; x < SizeX(); x++ )
      {
         char c = _m[y][x];
         letterCount[c]++;
         _TileVariables[c] = pair<int,int>( x, y );
         if ( letterCount[c] > 1 )
            _TileVariables.erase( c );
      }
   }

private:
   vector<string> _m;
   map<char,pair<int,int> > _TileVariables; // advanced feature
};

class BitBoard
{
public:
   typedef long long RowType;
   struct ThreeRows
   {
      ThreeRows( RowType r0, RowType r1, RowType r2 ) : row0(r0), row1(r1), row2(r2) {}
      bool operator<( const ThreeRows& rhs ) const { return row0 != rhs.row0 ? row0 < rhs.row0
                                                          : row1 != rhs.row1 ? row1 < rhs.row1
                                                          :                    row2 < rhs.row2; }
      RowType row0, row1, row2;
   };

   BitBoard( const Board& b )
   {
      Init( b );
   }
   RowType toRowType( const string& row )
   {
      RowType r = 0;
      for ( int x = 0; x < (int) row.length(); x++ )
         r += RowType( row[x] != ' ' ) << x;
      return r;
   }
   void Init( const Board& board )
   {
      _SizeX = board.SizeX();
      if ( board.SizeX() > 64-3 )
         return;
      if ( board.SizeY() > 64-3 )
         return;

      for ( int y = 0; y < board.SizeY(); y++ )
         _m.push_back( toRowType( board[y] ) );
   }

   int max1x3Tiles()
   {
      for ( int y = 0; y < ARR_SIZE( _Cache ); y++ )
      for ( int x = 0; x < ARR_SIZE( _Cache[y] ); x++ )
         _Cache[y][x].clear();
      return max1x3Tiles( 0, 0, row(0), row(1), row(2) );
   }
   Board generateLayout()
   {
      Board outputBoard( _SizeX, _m.size() );
      max1x3TilesPrint( 0, 0, row(0), row(1), row(2), outputBoard, 'A' );
      return outputBoard;
   }

private:
   // recursive memoized function to find maximum layout starting at (x,y) (and going left-to-right, top-to-bottom)
   // with the current and next two rows overridden to be (row0,row1,row2)
   int max1x3Tiles( int x, int y, RowType row0, RowType row1, RowType row2 )
   {
      row0 &= ~((1LL<<x)-1); // clear out the part of the row we passed by already

      // return cached result if found
      ThreeRows tr(row0,row1,row2);
      if ( _Cache[y][x].count(tr) )
         return _Cache[y][x][tr];

      if ( x >= _SizeX )
         return max1x3Tiles( 0, y+1, row1, row2, row(y+3) ); // next row
      if ( y >= (int)_m.size() )
         return 0; // done

      // option 1. don't cover (x,y)
      int bestScore = max1x3Tiles( x+1, y, row0, row1, row2 );

      // option 2. cover (x,y) horizontally
      RowType horz = 7LL << x; // e.g. 000011100 in binary
      bool canPlaceHorz = !( horz & ~row0 );
      if ( canPlaceHorz )
         bestScore = max( bestScore, 1+max1x3Tiles( x+3, y, row0 & ~horz, row1, row2 ) );

      // option 3. cover (x,y) vertically
      RowType vert = 1LL << x;
      bool canPlaceVert = !( vert & ~row0 ) && !( vert & ~row1 ) && !( vert & ~row2 );
      if ( canPlaceVert )
         bestScore = max( bestScore, 1+max1x3Tiles( x+1, y, row0 & ~vert, row1 & ~vert, row2 & ~vert ) );

      return _Cache[y][x][tr] = bestScore;
   }

   // code to generate an actual maximum tile layout (uses a lot of duplicated code:()
   int max1x3TilesPrint( int x, int y, RowType row0, RowType row1, RowType row2, Board& outputBoard, char curLetter )
   {
      row0 &= ~((1LL<<x)-1); // clear out the part of the row we passed by already

      if ( x >= _SizeX )
         return max1x3TilesPrint( 0, y+1, row1, row2, row(y+3), outputBoard, curLetter ); // next row
      if ( y >= (int)_m.size() )
         return 0; // done
      bool currentTileIsEmpty = !((1LL<<x)&row0);
      if ( currentTileIsEmpty )
         return max1x3TilesPrint( x+1, y, row0, row1, row2, outputBoard, curLetter );

      // option 1. don't cover (x,y)
      int option1Score = max1x3Tiles( x+1, y, row0, row1, row2 );
      int option2Score = -1;
      int option3Score = -1;

      // option 2. cover (x,y) horizontally
      RowType horz = 7LL << x; // e.g. 000011100 in binary
      bool canPlaceHorz = !( horz & ~row0 );
      if ( canPlaceHorz )
         option2Score = 1+max1x3Tiles( x+3, y, row0 & ~horz, row1, row2 );

      // option 3. cover (x,y) vertically
      RowType vert = 1LL << x;
      bool canPlaceVert = !( vert & ~row0 ) && !( vert & ~row1 ) && !( vert & ~row2 );
      if ( canPlaceVert )
         option3Score = 1+max1x3Tiles( x+1, y, row0 & ~vert, row1 & ~vert, row2 & ~vert );

      int bestOption = option1Score > option2Score && option1Score > option3Score ? 1
                     : option2Score >= option3Score ? 2 : 3;

      if ( bestOption == 1 )
      {
         outputBoard[y][x] = '*';
         max1x3TilesPrint( x+1, y, row0, row1, row2, outputBoard, curLetter );
      }
      if ( bestOption == 2 )
      {
         outputBoard[y][x+0] = curLetter;
         outputBoard[y][x+1] = curLetter;
         outputBoard[y][x+2] = curLetter;
         max1x3TilesPrint( x+3, y, row0 & ~horz, row1, row2, outputBoard, curLetter+1 );
      }
      if ( bestOption == 3 )
      {
         outputBoard[y+0][x] = curLetter;
         outputBoard[y+1][x] = curLetter;
         outputBoard[y+2][x] = curLetter;
         max1x3TilesPrint( x+1, y, row0 & ~vert, row1 & ~vert, row2 & ~vert, outputBoard, curLetter+1 );
      }
      return max(option1Score,max(option2Score,option3Score));
   }

private:
   RowType row( int y ) const { return y < (int)_m.size() ? _m[y] : 0; }
private:
   vector<RowType> _m;
   int _SizeX;
   map<ThreeRows, int> _Cache[64][64];
};


int Board::Max1x3Tiles() const
{
   return BitBoard( *this ).max1x3Tiles();
}

Board Board::GenerateLayout() const
{
   return BitBoard( *this ).generateLayout();
}

int main(int argc, char *argv[])
{
   string mapFile = "map.txt";
   if ( argc == 2 )
      mapFile = argv[1];
   Board board( mapFile );
   //cout << "Input map: " << endl;
   //cout << board.Str() << endl;
   //cout << "maximum tiles = " << board.Max1x3Tiles() << endl;
   //cout << "One possible layout: " << endl;
   //cout << board.GenerateLayout().Str() << endl;
   //cout << board.TruthTable() << endl;
   //cout << board.TruthTableInt() << endl;
   board.FindTruthTable( 15 );
   return 0;
}