Why is the size of the search space 2057 in the 8-queen puzzle?
According to Peter Norvig in 2007, it comes from "... writing a program and counting the states." 

For the $n$-queens problem, it is not too hard to show that $(n!)^{(1/3)}$ is a lower bound on the size of state space. This can be calculated by considering the maximum number of squares in each column that might be threatened by queens from previous columns. For $n=8$, this evaluates to $34.29$.