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.

Question

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

Ans A):-

Ans B):-

Ans C):- h(n) = # of white tiles on the wrong side of each black tile

Breadth-first search is admissible, monotonic and very uninformed. Counting tiles out of the goal position is a simple useful heuristic that is admissible. A form of this heuristic would be to count all white tiles on the wrong side of each black tile.

For example for the following configuration, there are 3 Ws on the right side of 1st B, and 2 Ws on the right side of both the 2nd and 3rd Bs. Therefore h(n) = 3+2+2 = 7

B_WBBWW

Counting tiles out of place is not monotonic, but is more informed than breadth-first search. An easy way to prove that a heuristic is non-monotonic is to watch its value change as it goes along a search path.