A friend of mine is attempting to make a webpage that has a game for a 2×2 grid that is similar to the old North, South, East, West game. I cannot for the life of me figure this out.
Essentially, the game would do this. A player starts on coordinate (0,0) and moves around the grid. This grid coordinate would be white while the rest are black. Here is a diagram:
$$
\begin{align}
&WB \\ &BB
\end{align}
$$
Once a the player moves, things change. When a player moves from a square, that square becomes yellow. Here is a new diagram to illustrate this (moving from (0,0) to (0,1)):
$$
\begin{align}
&YW \\ &BB
\end{align}
$$
Once a player uncovers a square, the square cannot be black again. Also, the coordinate (0,0) can never be black (since the player starts there). There can only be one white square at any given time.
My friend (and now I) wants to know how the number of permutations/combinations of outcomes of the colors of the squares. I have tried, but I just cannot seem to understand how this would work. The best I could come up with was:
$$
\begin{align}
&4^2-1 = 15
\end{align}
$$
I derived this from the fact that each box can only be one of two colors at any given time and the first box cannot be one of those colors (black). Is there a better way to approach this? Is there a more general way that will work for different sized grids (3×3, 4×4, and etc)?
Best Answer
If I have understood the rules of your game, the configuration of the board, depends on the particular movements that make the player. I'll number the squares like this:
$$\begin{align} &12 \\ &34 \end{align}$$
The following paths yield different color configurations of the board: 1, 12, 13, 121, 124, 131, 134, 1213, 1242, 1312, 1343. That makes $11$. These paths don't cover the whole board, that is, there are black squares left.
If you pass through every square, every square is yellow, except one that is white. There are $4$ possibilities for the square that is white. So there are $15$ possibilities.
I have assumed that diagonal movements are not allowed.
For a $n\times n$ board, the problem seems very difficult, because the yellow squares must form a connected set. I don't know how to count connected sets in a board.