Short answer: 4^(17*17) combinations to try, and each combination requires an expensive test before you can pass/fail it. Plug that number into Wolfram Alpha alongside things like "age of the universe" for some perspective on just how massive the search space is.

The search space a lot smaller, since you can cut many incorrect branches very early.

Yes, but as noted in the post mvzink linked, you can't cut it to the point that an exhaustive search is feasible.

This post explains the problem enough to give an intuitive understanding of why it's difficult: http://bit-player.org/2009/the-17x17-challenge