Trying to calculate the state space of a board with 5 numbers on

Question

I have a 5x5 board with 1..5 numbers in the top row of the board.

Every number can ultimately end up in any position so long as it is not on top of another number.

Every number can move one up,down,left or right in a single move, however I don't believe this makes a difference to the state space since ultimately every number can end up anywhere given an unlimited amount of moves.

Because every number can ultimately be anywhere at any point except on top of another number I'm assuming that a number can be in 1/21 positions at any one time? i.e. the board space (25) minus the numbers that it cannot be ontop of (4).

My original calculation was ((n*n)-(n-1))^n because I was trying to take into account that a number could not be ontop of another number however I found the following calculation:

I found this on a wiki page as a way of calculating the state space of a go game board.

Each space can have 6 different possible vales (1..5 and empty) and the board has 25 squares, so the equation would be (n+1)^(n*n) = 6^25 = 2.843x10^19

Is this correct? Does the fact that a single number can only be in 21 spaces out of the 25 at any single moment not affect it?

If it's incorrect could you please inform me why or/and offer a working solution.

Thanks a lot! :)

Answer 1

Is this correct? Does the fact that a single number can only be in 21 spaces out of the 25 at any single moment not affect it?

No, it's not correct. The difference to a Go board is that you only have 5 numbers and thus always 20 of the 25 places are empty, and each non-empty state can appear only once.

So there are 25 `choose` 5 possibilities for the five places where the numbers are, and the five numbers can be arranged in 5! ways on these five places.

Thus you have a total state space of

25!/20! = 21*22*23*24*25 = 6375600

states.

Answer 2

I think the answer you're looking for is (25 choose 5)*5!

This would be the equivalent of choosing any five spaces on the board and then all combinations that numbers could be arranged in them. This might not be taking into account overlap though.