# Estimating size of state space search problem

Im currently enrolled in an AI course and we are starting with state space search problems. My professor always seems to ask, given a certain problem, what is the estimate size of the state space? It's been 3 years since ive taken a course in discrete math which is the type of question I am asking.

How can I use things like branch factor and depth to estimate state space?

• Try drawing particular examples and see what you get. For example, if the branch factor is 2 then you have a binary tree. How many nodes does a binary tree of depth $d$ contain? And so on. Give it a few hours. – Yuval Filmus Feb 17 '17 at 8:17

## 1 Answer

So lets take an 8 queens problem. Intially the size of state is 64C8 where 64 is the number of squares in a chess board and 8 is the number of queens that can be placed.

Now lets say, you can only put one queen in each column so that's only 8 squares available. This reduces the branching factor from 64 to 8. Now the size of state is 8C8 only.

Now lets say, you can only use 2 queens instead of 8. This reduced the depth from 8 to 2. So in this case instead of being 8 queens , now it's going to be a 2 queens problem. So that changes the size of state from 8C8 to 8C2. Cheers man.