It seems like it would be way easier to think about it the opposite way... pick a space, start enumerating the possible connections it can have to its neighbors recursively, with a simple algorithm that won't pick already picked neighbors, and then read the bit string off the result. That's easily done by starting with all 1s, and then setting to 0 the bit corresponding to the choice you just made.

Either direction is of course the same in theory, of course.

More excitingly than that, you may be able to contribute to OEIS now, if you can work yourself out a few more terms: https://oeis.org/search?q=1%2C1%2C28%2C12600&sort=&language=...