You're suggesting using 2 bits to store the height of the column, plus 3 bits to store the presence of holes, for a total of 5 bits per column. Exactly how you got from that to a figure of "2^23" I don't know. That's actually (2^5)^10 = 2^50 possible column combinations.

Why not just use 4 bits to represent the whole column? That's (2^4)^10 = 2^40, exactly where we started.

In fact, look at rows instead. With 10 columns and 4 rows there are, to be more precise, (2^10 - 1)^4 possible states.

And the majority of which have "floating" (disconnected) sections which, while reachable with the rules of Tetris, cannot be reached without making at least one line.

In case you didn't read the article, Tetris has been solved for width 10 height 4: the AI wins. The same is true for width 10 height 5. We need to go further.