For 5 by 5 boards, 414294790771 out of 847288609443 are legal (48.8965%).
6 by 6: 62567313302554383 out of 150094635296999121 (41.6852%).
Eric's rough estimate 4^n of the number of possible border configurations
seems to be a good one:
n true 4^n
2 17 16
3 61 64
4 219 256
5 827 1024
6 3287 4096
So 9 by 9 is feasible and maybe even 13 by 13 (on the order of 10^7). The
double precision did not suffice for even 6 by 6. My program will give
7 by 7 but probably not more.