#include <assert.h>
#include <bitset>
#include <iomanip>          // std::setw
#include <iostream>
#include <set>
#include <vector>
#include <stddef.h>         // ptrdiff_t
#include <stdlib.h>         // EXIT_SUCCESS, EXIT_FAILURE
using namespace std;

typedef ptrdiff_t   Size;

template< class Number >
inline Number square( Number x ) { return x*x; }

struct Side{ enum Enum { enumBegin, right = 0, up, left, down, enumEnd }; };
inline void operator++( Side::Enum& s ) { s = Side::Enum( s + 1 ); }

struct ConnectorKind{ enum Enum { enumBegin, female = 0, male, enumEnd }; };

template< class Elem >
class Matrix
{
private:
    vector<Elem>    elem_;
    Size            sizeOfSide_;

    Size indexOf( Size x, Size y ) const
    {
        return y*sizeOfSide_ + x;
    }

public:
    Matrix( Size size )
        : elem_( size*size )
        , sizeOfSide_( size )
    {}
    
    Elem const& at( Size x, Size y ) const
    {
        return elem_.at( indexOf( x, y ) );
    }
    
    Elem& at( Size x, Size y )
    {
        return elem_.at( indexOf( x, y ) );
    }
};

class Piece
{
private:
    int     id_;

public:
    int id() const { return id_; }

    ConnectorKind::Enum connectorKindAt( Side::Enum side ) const
    {
        int const bitnum = (0?0
            : side == Side::left?       0
            : side == Side::up?         1
            : side == Side::right?      2
            : side == Side::down?       3
            : 0
            );
        bool const  isMale  = !!(id_ & (1 << bitnum));
        return ConnectorKind::Enum( isMale );
    }
    
    Piece( int id )
        : id_( id )
    {
        assert( 0 <= id_ );
        assert( id_ < 16 );
    }
};

class BoardPosition
{
private:
    Size        x_;
    Size        y_;

public:
    enum{ sideLength = 4 };
    
    int const x() const { return x_; }
    int const y() const { return y_; }
    
    BoardPosition atSide( Side::Enum side ) const
    {
        switch( side )
        {
        case Side::right:   return BoardPosition( x_ + 1, y_ );
        case Side::up:      return BoardPosition( x_, y_ - 1 );
        case Side::left:    return BoardPosition( x_ - 1, y_ );
        case Side::down:    return BoardPosition( x_, y_ + 1 );
        default:
            assert( false );
            return BoardPosition();
        }
    }

    BoardPosition next() const
    {
        return (
            x_ == sideLength - 1
            ? BoardPosition( 0, y_ + 1 )
            : BoardPosition( x_ + 1, y_ )
            );
    }
    
    BoardPosition prev() const
    {
        return (
            x_ == 0
            ? BoardPosition( sideLength - 1, y_ - 1 )
            : BoardPosition( x_ - 1, y_ )
            );
    }
    
    bool isInBoard() const
    {
        return (0 <= x_ && x_ < sideLength) && (0 <= y_ && y_ < sideLength);
    }

    BoardPosition(): x_( -1 ), y_( -1 ) { assert( !isInBoard() ); }
    
    BoardPosition( Size x, Size y )
        : x_( x )
        , y_( y )
    {}
};

class Board
{
private:
    Matrix<Piece const*>    positions_;
 
public:
    enum{ sideLength = BoardPosition::sideLength };

    static Piece const* piece( int id )
    {
        static Piece const thePieces[] =
        { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
        
        return (id < 0? static_cast<Piece const*>( 0 ) : &thePieces[id]);
    }

    Piece const* at( BoardPosition const& pos ) const
    {
        return positions_.at( pos.x(), pos.y() );
    }
    
    Piece const*& at( BoardPosition const& pos )
    {
        return positions_.at( pos.x(), pos.y() );
    }

    Board(): positions_( sideLength ) {}
};


class Solver
{
private:
    typedef bitset<16>  PieceSet;

    Board               board_;
    PieceSet            unplaced_;
    bool                isSolved_;

    bool isUnplaced( int pieceIndex ) const
    {
        return unplaced_[pieceIndex];
    }

    bool place( BoardPosition const& pos, int pieceId )
    {
        Piece const thisPiece( pieceId );

        if( pos.y() > 0 )
        {
            BoardPosition const         checkPos    = pos.atSide( Side::up );
            ConnectorKind::Enum const   thisKind    = thisPiece.connectorKindAt( Side::up );
            ConnectorKind::Enum const   otherKind   = board_.at( checkPos )->connectorKindAt( Side::down );
            
            if( thisKind == otherKind )
            {
                return false;
            }
        }

        if( pos.x() > 0 )
        {
            BoardPosition const         checkPos    = pos.atSide( Side::left );
            ConnectorKind::Enum const   thisKind    = thisPiece.connectorKindAt( Side::left );
            ConnectorKind::Enum const   otherKind   = board_.at( checkPos )->connectorKindAt( Side::right );
            
            if( thisKind == otherKind )
            {
                return false;
            }
        }
        
        board_.at( pos ) = Board::piece( pieceId );
        assert( board_.at( pos )->id() == pieceId );
        unplaced_[pieceId] = false;
        return true;
    }

    void unplace( BoardPosition const& pos )
    {
        unplaced_[board_.at( pos )->id()] = true;
        board_.at( pos ) = 0;
    }

    bool solve( BoardPosition const& pos )
    {
        if( !pos.isInBoard() ) {  return true; }

        for( int pieceId = 0;  pieceId < 16;  ++pieceId )
        {
            if( isUnplaced( pieceId ) )
            {
                if( place( pos, pieceId ) )
                {
                    if( solve( pos.next() ) )
                    {
                        return true;
                    }
                    unplace( pos );
                }
            }
        }
        return false;
    }

public:
    Board const& board() const { return board_; }

    bool succeeded() const { return isSolved_; }

    Solver()
        : unplaced_( (1 << 16) - 1 )
    {
        isSolved_ = solve( BoardPosition( 0, 0 ) );
    }
};

bool solve( Board& board )
{
    Solver  solver;
    
    if( solver.succeeded() )
    {
        board = solver.board();
        return true;
    }
    return false;
}

int main()
{
    Board   board;
    
    bool const solved   = solve( board );
    
    if( !solved )
    {
        cerr << "!Sorry, found no solution." << endl;
        return EXIT_FAILURE;
    }
    else
    {
        for( int y = 0;  y < Board::sideLength;  ++y )
        {
            for( int x = 0;  x < Board::sideLength;  ++x )
            {
                cout << setw( 4 ) << board.at( BoardPosition( x, y ) )->id();
            }
            cout << endl;
        }
    }
    return EXIT_SUCCESS;
}

Line 40: error: stddef.h: No such file or directory