Reverse the 3 white and 3 black tiles problem in AI

In the 3 white and 3 black tiles problem, there are 7 tiles, 3 are white and 3 are black and there is a white space in the middle. All the black tiles are placed left and all the white tiles are placed right. Each of the white or black tiles can move to the blank space and they can hope over one or two tiles to reach the blank space.

1. Analyze the state-space of the problem.
2. Propose a heuristic for this problem to move all the white tiles left to all the while tiles, the position of the blank space is not important.

Initial State

Goal State

AI Assumptions

• Heuristics for Black Tile = tile-distance to the first white tile to its right
• Heuristics for White Tile = tile-distance to the first black tile to its left * -1
• We will run the script as long as we will have a non zero value for a tile.
• If any black tile does not contain any white tile to its left then that tile will have Zero Heuristics
• If any white tile does not contain any black tile to its right then that tile will have Zero Heuristics
• We will have a selector value initially set as White.
• For each iteration, we will change the value to black and white and so no.
• Depending on the selector we will choose that colored tile with the highest tile says, Tile X.
• X will be moved to the blank space.
• If the tile jumps to its next tile the cost:= 1 if hop one tile then cost:= 2 if jumps 2 tiles then cost:= 3.

3 white and 3 black tiles problem Algorithm

Selector:= white	
Foreach black tile b
     do h(b):= tile-distance to the first white tile to its right
Foreach white tile w
     do h(w):= tile-distance to the first black tile to its left * -1

While any tile has a non-zero h value
   Do
        If selector:= white then,
            Select the while-tile with the highest h value, say X
            If the h(X):= 0 and it does not have the blank space to its left then,
                Select another while-tile with the next-highest h value, say X
            Selector := black
        Else
            Select the black-tile with the highest h value, say X
            If the h(X):= 0 and it does not have the blank space to its left then,
                Select another black-tile with the next-highest h value, say X
            Selector:= white

       If X and the blank space is in 2-tiles distance then,
           Move X to the blank space and record the cost

       Foreach black tile b
           do h(b):= tile-distance to the first white tile to its right
       Foreach white tile w
           do h(w):= tile-distance to the first black tile to its left * -1
End while

Steps:

Step 1: Selector: Null – INITIAL STATE

cost = 0

Step 2: Selector: W

cost = 1

Step 3: Selector: B

cost = 3

Step 4: Selector: W

cost = 2

Step 5: Selector: B

cost = 1

Step 6: Selector: W

cost = 3

Step 7: Selector: B

cost = 2

Step 8: Selector: W

cost = 3

Step 9: Selector: B

cost = 2

Step 10: Selector: W

cost = 3

Step 11: Selector: B

cost = 1

Step 12: Selector: W

cost = 2

Step 13: Selector: B

cost = 1

Step 14: Selector: W

cost = 2

Step 15: Selector: B

cost = 1

Step 16: Selector: W

cost = 2