Question

What is the state space size for a 2x2 Rubik’s cube? Explain your reasoning. Contrast the

state transition function of the 2x2 cube with the 8-puzzle. How many “tiles” the cube have?

How many states does each “tile” have?

Answer 1

1. State Space of 2x2 Rubik’s Cube is 7! X 3⁶ or 3,674,160 possible configurations.

To prove this imagine fixing one corner cubic by holding it with the fingers of one hand, and applying moves by rotating any of the three faces not involving the fixed cubic. With these 6 basic moves– clockwise and counterclockwise quarter turns of 3 faces– it is possible to realize all possible cube states, consisting of permutations and orientations of the 7 non-fixed cubic.

2. Given a 3×3 board with 8 tiles and one empty space. The objective is to place the numbers on tiles to match final configuration using the empty space. We can slide four adjacent (left, right, above and below) tiles into the empty space.

Set of all configurations of a given problem i.e. all states that can be reached from the initial state. Assume that moving one tile in any direction will have 1 unit cost so ideal state function is

c(x) = f(x) + h(x) where

f(x) is the length of the path from root to x and

h(x) is the number of non-blank tiles not in their goal position. There are at least h(x) moves to transform state x to a goal state.

3. A 2x2 Rubik’s cube has 8 pieces, all corner pieces, and a total of 24 tiles.
4. Each Tile has 4 states.