For games in general, one measure of complexity is branching factor. It means average number of possible actions or states at each turn. It is knowable.
"Solvability" would mean number of turns to solve the game. It is known for some puzzles and can be found by brute force, otherwise you need to figure out a proof.
"Solvability" would mean number of turns to solve the game. It is known for some puzzles and can be found by brute force, otherwise you need to figure out a proof.