Question

1. The sliding-tile puzzle consists of three black tiles, three white tiles, and an empty space in the configuration shown in this table.

B

B

B

W

W

W

The puzzle has two legal moves with associated costs:

1. A tile may move into an adjacent empty location. This has a cost of 1.
2. A tile can hop over one or two other tiles into the empty position. This has a cost equal to the number of tiles jumped over.

The goal is to have all the white tiles to the left of all the black tiles. The position of the blank is not important.

a: Estimate/calculate a branching factor of the space and justify your estimation

b: How many total states need to be searched for a path of 12?

c: Propose two heuristics for solving this problem and analyze them with respect to admissibility, monotonicity, and informedness.

Answer 1

a. According to the rules given in the problem statement you can mobe 'backwards' though it may be you need not to solve it, in which case it would be a smart idea to re write the rules. However, as they are, the rules allow loops, so you’re in a graph search. There will be six opening moves, but there can be fewer later. There are only a finite number of distinct states. I can figure you can put the blank anywhere (7 choices), then you can distribute the 3 whites anywhere in the remaining six spots (C(6,3) or “six choose three” positions). (The whites are indistinguishable, so they can be arranged (6*5*4) / 3! ways. We have so far 7*5*4 choices. The remaining indistinguishable blacks are forced into the remaining 3 spots and were’re done with 140 different states in the graph. Another way to think about it is ALL arrangements i.e. divided by the number of indistinguishable arrangements of the white and black squares, or which is 7!/(3! + 3!)

b. For a path of 12 the total states that are to be tested are 6

c. Here are some possible h(n) functions:

1. the number of W characters to the the right of a B character in the string

2. the sum of the distance between the position of each W tile and the rightmost B tile. For both of these, the tile can move n spaces with cost <= n which means that they underestimate the minimum possible cost to reach a goal state. Both are monotonic and thus admissible.