Подсчитать количество способов замостить шахматную доску доминошками

//На шахматной доске,размером N*N клеток(2<=N<=8),подсчитать кол-во способов,
//которыми можно замостить данную доску стандартными доминошками.
#include <iostream>
#include <iomanip>
#include <ctime>
 
class T_doska
{    
    static const int  MASSIV_DIM    = 12;
    static const int  EMPTY_KLETKA  = MASSIV_DIM * MASSIV_DIM;    
 
    int               doska_dim_;    
    int               solution_count_;    
    int               domino_count_;
    int               nach_kletki_domino_[MASSIV_DIM * MASSIV_DIM / 2];    
    int               kletki_doski_[MASSIV_DIM][MASSIV_DIM];
public:
    T_doska(int dim) 
        : doska_dim_(dim), 
          solution_count_(0),
          domino_count_(0)          
    {        
        kletki_clear();
    }
    //---------------------------------------------------------------------------
    void  count_zamostit_domino()
    {
        clock_t    cstart        = clock();
        const int  PRINT_PERIOD  = 1000000;
        while(uspeshno_zamostil())
        {
            ++solution_count_;
            if(doska_dim_ <= 4)
            {
                print_kletki();
            }
            else
            {
                if(solution_count_ == PRINT_PERIOD)
                {
                    std::cout << "Уже подсчитано вариантов: "
                              << std::endl;
                }
                if(solution_count_ % PRINT_PERIOD == 0)
                {
                    std::cout << solution_count_                              
                              << std::endl;
                }            
            }            
        }
        clock_t  cend = clock();
        double sec = static_cast<double>(cend - cstart) / CLOCKS_PER_SEC;
        std::cout << std::endl
                  << "Время выполнения " 
                  << sec 
                  << " сек."
                  << std::endl;
 
        std::cout << "Всего получили "
                  << solution_count_
                  << " вариантов замощения доски "
                  << doska_dim_
                  << " x "
                  << doska_dim_
                  << " костями домино."
                  << std::endl;
    }
    //---------------------------------------------------------------------------
private:
    //---------------------------------------------------------------------------
    void  print_kletki()
    {
        std::cout << "Вариант № "
                  << solution_count_
                  << std::endl;
        for(int i = 0; i < doska_dim_; ++i)
        {
            for(int j = 0; j < doska_dim_; ++j)
            {
                std::cout << std::setw(4)
                          << kletki_doski_[i][j];
            }
            std::cout << std::endl
                      << std::endl;
        }    
    }
    //---------------------------------------------------------------------------
    inline int get_k(int i, int j)
    {
        return i * doska_dim_ + j + 1;
    }
    //---------------------------------------------------------------------------
    inline int get_i_from_k(int k)
    {
        return (k - 1)/ doska_dim_;
    }
    //---------------------------------------------------------------------------
    inline int get_j_from_k(int k)
    {
        return (k - 1) % doska_dim_;
    }
    //---------------------------------------------------------------------------
    bool  uspeshno_zamostil()
    {        
        int i;
        int j;        
        for(bool go_forward = (solution_count_ == 0); ; )
        {
            for(;go_forward;)
            {
                if(!get_first_empty_kletka(i, j)) return true;
                if(kletki_doski_[i][j + 1] == EMPTY_KLETKA)
                {                        
                    nach_kletki_domino_[domino_count_++] = get_k(i, j);
                    kletki_doski_[i][j + 1] = domino_count_;
                    kletki_doski_[i][j]     = domino_count_;
                }
                else if(kletki_doski_[i + 1][j] == EMPTY_KLETKA)
                {                        
                    nach_kletki_domino_[domino_count_++] = -get_k(i, j);
                    kletki_doski_[i + 1][j] = domino_count_;
                    kletki_doski_[i][j]     = domino_count_;                    
                }
                else
                {
                    go_forward = false;
                    break;
                }
            }//for(;go_forward;)                
            
            for(;!go_forward;)
            { 
                if(domino_count_ == 0) return false;                    
                int k_so_znakom = nach_kletki_domino_[domino_count_ - 1];                    
                nach_kletki_domino_[--domino_count_] = 0;
                int k = abs(k_so_znakom);
                i = get_i_from_k(k);
                j = get_j_from_k(k);
                if(k_so_znakom > 0)
                {
                    if(kletki_doski_[i + 1][j] == EMPTY_KLETKA)
                    { 
                        std::swap(kletki_doski_[i][j + 1], kletki_doski_[i + 1][j]);                            
                        nach_kletki_domino_[domino_count_++] = -k;
                        go_forward = true;
                        break;                        
                    }
                    else
                    {
                        kletki_doski_[i][j]      = EMPTY_KLETKA;
                        kletki_doski_[i][j + 1]  = EMPTY_KLETKA;                        
                    }
                }
                else
                {
                    kletki_doski_[i][j]      = EMPTY_KLETKA;
                    kletki_doski_[i + 1][j]  = EMPTY_KLETKA;
                }
            }//for(;!go_forward;)            
        }//for(;;)
    }
    //---------------------------------------------------------------------------    
    bool  get_first_empty_kletka
        (            
            int& i,         
            int& j
        )
    {
        int i_start = 0;
        int j_start = 0;        
        if(domino_count_ > 0)
        {            
            int k    = abs(nach_kletki_domino_[domino_count_ - 1]);
            i_start  = get_i_from_k(k);
            j_start  = get_j_from_k(k);
        }
        for(i = i_start; i < doska_dim_; ++i)
        {
            for(j = (i == i_start) ? j_start : 0; j < doska_dim_; ++j)
            {
                if(kletki_doski_[i][j] == EMPTY_KLETKA)
                {                   
                    return true;                
                }
            }
        }
        return false;
    }
    //---------------------------------------------------------------------------
    void  kletki_clear()
    {
        for(int i = 0; i < MASSIV_DIM; ++i)
        {
            for(int j = 0; j < MASSIV_DIM; ++j)
            {                
                kletki_doski_[i][j] = 0;
            }
        }    
 
        for(int i = 0; i < doska_dim_; ++i)
        {
            for(int j = 0; j < doska_dim_; ++j)
            {                
                kletki_doski_[i][j] = EMPTY_KLETKA;
            }
        }    
    }
    //---------------------------------------------------------------------------
};
 
int main()
{
    std::locale::global(std::locale(""));
    std::cout << "Введите длину стороны доски: ";
    int doska_dim;
    std::cin >> doska_dim;
    T_doska  doska(doska_dim);
    doska.count_zamostit_domino();
    return 0;
}