A difficult problem which no one haven't solve

[nghiank]

test

[Stefan Pochmann]

I recently analyzed a similar problem: How many boolean NxN matrices are there that don't contain the same value three times in a row (horizontally or vertically)?

Examples for n=4:

0010
0010
1101
0010
(good)

0001
0010
1101
0010
(bad because of the three 0's in the first row)


So far I've only attacked it with naive brute force (generate all matrices recursively and count). These are the results for the first few values of N:

2
16
102
2030
60232
3858082

[SnapDragon]

I tried a short DP algorithm (looking at the matrix as a string of length n^2, only the last 2n choices are relevant to any remaining choices.) Made it up to 11 before running out of memory. I'm not sure how you'd improve this. (I used doubles instead of BigInts, so the last answer's inexact )

size=1: 2
size=2: 16
size=3: 102
size=4: 2030
size=5: 60232
size=6: 3858082
size=7: 446672706
size=8: 101578277384
size=9: 43680343039806
size=10: 36133311325799776
size=11: 57061338836892852xxx

[SnapDragon]

Here's my code, if someone wants to tweak it.

Code: Select all

#include <cstdio>
#include <map>
using namespace std;
typedef signed long long i64;

int size;
map<i64, double> memo;
double nmat(i64 x) {
	double &ret = memo[x];
	if( ret != 0.0 ) return ret-1;
	ret = 1;
	int d = (x>>(2*size));
	if( d == size*size ) return (ret=2)-1;
	int b = (x&((1<<(2*size))-1)), b2 = ((x&((1<<(2*size-1))-1))<<1);
	if( (d < 2*size || (b&(1<<(2*size-1))) || (b&(1<<(size-1)))) &&
		(d%size < 2 || (b&3)) ) {
		ret += nmat(b2 + ((d+1)<<(2*size)));
	}
	if( (d < 2*size || !(b&(1<<(2*size-1))) || !(b&(1<<(size-1)))) &&
		(d%size < 2 || ((b&3) != 3)) ) {
		ret += nmat(b2+1 + ((d+1)<<(2*size)));
	}
	return ret-1;
}

main() {
	for( size = 1;; size++ ) {
		memo = map<i64, double>();
		printf( "size=%d: %30lf\n", size, nmat(0) );
	}
}

[nghiank]

test