1
$\begingroup$

I am currently studying the textbook Artificial Intelligence: A Modern Approach, 4th Edition, by Russell and Norvig. Chapter 3 Solving Problems by Searching says the following:

Another type of grid world is the sokoban puzzle, in which the agent's goal is to push a number of boxes, scattered about the grid, to designated storage locations. There can be at most one box per cell. When an agent moves forward into a cell containing a box and there is an empty cell on the other side of the box, then both the box and the agent move forward. The agent can't push a box into another box or a wall. For a world with $n$ non-obstacle cells and $b$ boxes, there are $n \times n! / (b!(n - b)!)$ states; for example on an $8 \times 8$ grid with a dozen boxes, there are over 200 trillion states.

I understand the combinatorial reasoning for why we get $n! / (b!(n - b)!)$ (the binomial coefficient), since we are looking for the number of ways we can choose (with replacement) $b$ boxes from a world with $n$ non-obstacle cells. But I don't understand where the $n$ factor in $n \times n! / (b!(n - b)!)$ comes from. What is the combinatorial reasoning for this $n$ factor?

$\endgroup$

1 Answer 1

1
$\begingroup$

Part of the state of the world is the location of the agent. Since there are $n$ cells, this variable has $n$ possible values, producing the factor of $n$.

Actually, there may be a mistake in Russell and Norvig's formula. After we have chosen the location of the agent, there are only $n - 1$ possible locations for the $b$ boxes, giving us $(n - 1)! / (b! (n - b - 1)!)$ choices for where to put all of the boxes. So, the number of states is $n \times (n - 1)!/(b!(n - b - 1)!)$, which simplifies to $n! / (b! (n - b - 1)!)$. (This is the trinomial coefficient $n \choose 1, b$.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.