/* takuzu.cpp -- Counting number of Takuzu   Copyright (C) 2015 Frans Faase

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

GNU General Public License:
   http://www.iwriteiam.nl/GNU.txt

Details:
   http://www.iwriteiam.nl/D1512.html#14

*/
#include <stdio.h>
#include <time.h>

#define SIZE 10

long nr_rows;
int row[SIZE];

class Tree
{
public:
    Tree() : zero(0), one(0), row_count(0), col_count(0) {}
    Tree* zero;
    Tree* one;
    int row_count;
    int col_count;
};

Tree *trees = 0;

void findrow(int p, int zeros, int ones)
{
    if (zeros == 0 && ones == 0)
    {
        Tree **rtree = &trees;
        for (int i = 0; i < SIZE; i++)
        {
            if (*rtree == 0)
                *rtree = new Tree();
            rtree = row[i] == 0 ? &(*rtree)->zero : &(*rtree)->one;
             
            printf("%d",row[i]);
        }
        *rtree = new Tree();
        printf("\n");
        nr_rows++;
        return;
    }
    if (zeros > 0 && (p < 2 || row[p-1] != 0 || row[p-2] != 0))
    {
        row[p] = 0;
        findrow(p+1, zeros-1, ones);
    }
    if (ones > 0 && (p < 2 || row[p-1] != 1 || row[p-2] != 1))
    {
        row[p] = 1;
        findrow(p+1, zeros, ones-1);
    }
}

double count = 0;

int sol[SIZE][SIZE];
Tree* row_tree[SIZE][SIZE];
Tree* col_tree[SIZE][SIZE];

void solve()
{
    int i = 0;
    int j = 0;
    sol[0][0] = 0;
    bool go = true;
    while (go)
    {
        bool zero = sol[i][j] == 0;
        Tree* row_tree_ij = zero ? row_tree[i][j]->zero : row_tree[i][j]->one;
        Tree* col_tree_ij = zero ? col_tree[i][j]->zero : col_tree[i][j]->one;
        if (row_tree_ij != 0 && col_tree_ij != 0)
        {
            bool unique = true;
            if (i < SIZE-1)
            {
                row_tree[i+1][j] = row_tree_ij;
                if (i == SIZE-2)
                {
                    if (++row_tree_ij->row_count > 1)
                        unique = false;
                }
            }
                
            if (j < SIZE-1)
            {
                col_tree[i][j+1] = col_tree_ij;
                if (j == SIZE-2)
                {
                    if (++col_tree_ij->col_count > 1)
                        unique = false;
                }
            }
            if (unique)
            {
                if (++i == SIZE)
                {
                    i = 0;
                    if (++j == SIZE)
                    {
                        count++;
                        static clock_t s = clock();
                        static clock_t ct = clock();
                        if (ct < clock())
                        {
                            ct = clock() + 6000;
                            double secs = (clock() - s)/1000.0;
                            printf("%10.1lf %20.0lf  (%10.3lf)\n", secs, count, count/secs);
                        }
                        --j;
                        i = SIZE-1;
                    }
                    else
                    {
                        sol[i][j] = 0;
                        continue;
                    }
                }
                else
                {
                    sol[i][j] = 0;
                    continue;
                }
            }
        }
        for (;;)
        {
            bool zero = sol[i][j] == 0;
            Tree* row_tree_ij = zero ? row_tree[i][j]->zero : row_tree[i][j]->one;
            Tree* col_tree_ij = zero ? col_tree[i][j]->zero : col_tree[i][j]->one;
            if (row_tree_ij != 0 && col_tree_ij != 0)
            {
                if (i == SIZE-2)
                    --row_tree_ij->row_count;
                if (j == SIZE-2)
                    --col_tree_ij->col_count;
            }
            if (zero)
            {
                sol[i][j] = 1;
                break;
            }
            if (i == 0)
            {
                if (j == 0)
                {
                    go = false;
                    break;
                }
                j--;
                i = SIZE-1;
            }
            else
                i--;
        }
    }
}

int main(int argc, char *argv[])
{
    findrow(0, SIZE/2, SIZE/2);
    printf("Rows = %d\n", nr_rows);
    for (int i = 0; i < SIZE; i++)
        col_tree[i][0] = trees;
    for (int j = 0; j < SIZE; j++)
        row_tree[0][j] = trees;
    solve();
    printf("count = %20.0lf\n", count);
    return 0;
}