First, let's discuss what technique this first program uses, for it's not a trivial implementation, and the final, fast program is a development of that.

I'm representing each row as a single integer fingerprint whose seven base 100 digits are 10, 1 or 0 depending on the contents of the cell. This way, you can tell if each column has exactly two 0, two 1 and three 2 values by adding the seven fingerprints representing the rows and see if you get 2222_222222_2222 as the result. I'd of course precompute all possible rows (all permutations of two 0, two 1, and three 2), and then the program only has to iterate on all combinations of five different of these, check if the columns are right and if there are no two identical columns. (We only need to check each combination, not each variation, per the note above.)

The next version of the program runs about four times faster. Instead of trying all possible rows for the last row, I compute the only numbers to make the distribution of each column right by subtracting the fingerprints of the six rows from 2222_222222_222, then check if that's a possible row and not identical to one of the rows above.

The most important optimization of the final solution is the following. I don't iterate on all combinations of four rows and compute the last one. Instead, I first do a fast loop where I iterate on all possible combinations of the last two rows, and store these in a hash keyed by the sum of the two fingerprints. (There can be more than one pairs of rows for each such key, but never more than a few of them.) Then, I iterate on all possible combinations of the middle three rows, compute the sum of fingerprints the last two rows need to give, and look up what possible last two rows can complete the table. I lose something by this method, for now I need to check whether the sixth row is lexicographically greater than the fifth row (the middle three rows and the last two rows themselves are already sorted lexicographically), and throw away some potential solutions where this is false. This, however, is nothing compared to how much speed I gain by having to loop only three levels deep instead of four levels like above.

The final optimization concerns how I check whether the table has two identical <s>rows</s> columns, for I always have to do this in all solutions above. For this, I make a secondary fingerprint for each row. This is an integer of 21 bits: each bit corresponds to a pair of column indices in the table, and each bit is set in a fingerprint if those two cells in the row have an equal value. These numbers have the property that the bitwise and of the fingerprints of the seven rows are zero if an only if there are no two identical columns in the table. With these values precomputed for all possible rows, we can do the check very fast.

#!perl

use warnings; use strict;
use IO::Handle;
use Time::HiRes "time";

sub aeq {
    my($a, $b) = @_;
    @$a == @$b or die;
    for (0 .. @$a - 1) {
        $$a[$_] == $$b[$_] or return;
    }
    return 1;
}

my @poss;
{
    my @pos = (0, 0, 0, 0, 0, 0, 0);
    while (1) {
        my $k = @pos;
        while (0 <= $k && 2 <= $pos[--$k]) { $pos[$k] = 0; }
        -1 == $k and last;
        $pos[$k]++; 
        my @freq = (0)x3;
        $freq[$_]++ for @pos;
        aeq(\@freq, [2, 2, 3]) or next;
        push @poss, [@pos];
    }
}
#warn 0+@poss; # 210

sub key {
    0 + join "", map { ("10", "01", "00")[$_] } @_;
}
sub ckey {
    7 == @_ or die;
    my $r = 0;
    for my $x (1 .. 6) {
        for my $y (0 .. $x - 1) {
            $r <<= 1;
            $r += $_[$x] == $_[$y];
        }
    }
    0 + $r;
}

my $INF = *DATA;
my $num_inp = 0 + <$INF>;
for (1 .. $num_inp) {
    my $begin_time = time;
    my @r0 = <$INF> =~ /[012]/g;
    my @r1 = <$INF> =~ /[012]/g;
    my $s2 = key(@r0) + key(@r1);
    my $cs2 = ckey(@r0) & ckey(@r1);
    my @posr = grep { !aeq(\@r0, $_) && !aeq(\@r1, $_) } @poss;
    @posr == @poss - 2 or do {
        print STDERR "i ", join(" ", @r0), "\n  ", join(" ", @r1), "\n
+";
        print STDERR "w 0\n";
        print "0\n";
        flush STDOUT;
        next;
    };
    my @posk = map { key @$_ } @posr;
    my @posck = map { ckey @$_ } @posr;
    # most a feladat olyan az $m2 < $m3 < $m4 < $m5 < $m6 indexek össz
+eszámolása, amelyekre
    # $posk[$mi] összege plusz $s2 egyenlő 222222_2222_2222, 
    # és $posck[$mi] bitwise and-je and $cs2 egyenlő & 0.
    my %sx_lookup;
    for my $m5 (3 .. @posr - 2) {
        for my $m6 ($m5 + 1 .. @posr - 1) {
            my $sx = 222222_2222_2222 - $s2 - $posk[$m5] - $posk[$m6];
            my $csx = $cs2 & $posck[$m5] & $posck[$m6];
            push @{$sx_lookup{0 + $sx}}, [$m5, $m6, $csx];
        }
    }
    my($T) = (0);
    print STDERR "i ", join(" ", @r0), "\n  ", join(" ", @r1), "\n";
    for my $m2 (0 .. @posr - 5) {
        for my $m3 ($m2 + 1 .. @posr - 4) {
        for my $m4 ($m3 + 1 .. @posr - 3) {
            my $sx = $posk[$m2] + $posk[$m3] + $posk[$m4];
            my $csb = $posck[$m2] & $posck[$m3] & $posck[$m4];
            for my $rec (@{$sx_lookup{0 + $sx}}) {
                my($m5, $m6, $csx) = @$rec;
                $m4 < $m5 or next;
                my $cs = $csb & $csx;
                0 == $cs or next;
                $T++;
            }
        }}
        print STDERR "."; 
    }
    my $R = $T * (5*4*3*2*1);
    print $R, "\n";
    flush STDOUT;
    print STDERR "\no $T $R\n";
    printf STDERR "t %.2f sec\n", time - $begin_time;
}

__DATA__
10
2 1 0 0 2 2 1
0 2 2 1 1 0 2
2 0 0 2 2 1 1
2 0 1 2 2 1 0
2 1 0 1 2 0 2
2 2 1 1 2 0 0
2 1 0 1 2 2 0
1 2 0 2 1 2 0
0 2 0 1 2 1 2
1 2 0 2 1 0 2
2 0 0 1 2 2 1
2 1 1 0 2 2 0
1 2 2 0 0 2 1
2 0 1 0 1 2 2
2 2 1 1 0 2 0
1 0 2 1 2 0 2
2 0 1 1 2 0 2
0 1 2 2 0 1 2
0 2 2 0 1 2 1
1 0 1 2 2 2 0
[download]

0 0 1 1 2 2 2
0 0 1 2 1 2 2

0 0 1 1 2 2 2
0 0 2 2 1 1 2

0 0 1 1 2 2 2
0 1 0 1 2 2 2

0 0 1 1 2 2 2
0 1 0 2 1 2 2

0 0 1 1 2 2 2
0 1 1 2 0 2 2

0 0 1 1 2 2 2
0 1 2 2 0 1 2

0 0 1 1 2 2 2
0 2 0 2 1 1 2

0 0 1 1 2 2 2
0 2 1 2 0 1 2

0 0 1 1 2 2 2
0 2 2 2 0 1 1

0 0 1 1 2 2 2
1 1 0 0 2 2 2

0 0 1 1 2 2 2
1 1 0 2 0 2 2

0 0 1 1 2 2 2
1 1 2 2 0 0 2

0 0 1 1 2 2 2
1 2 0 2 0 1 2

0 0 1 1 2 2 2
1 2 2 2 0 0 1
[download]