Question

110Marks Question No. 4 Eight queens problem: place 8 queens on a chess board so that no two queens attack each other. -state: locations of 0 to 8 queens (with no two queens attacking each other) goal test: 8 queens placed on the board (with none attacked) operator: place a queen in the left-most empty column such that it is not attacked by any other queen (and does not attack any other queen) path cost: 0 Depth first search: i. Can this search be used on this problem? If not, why not? ii. Is this search complete for this problem? iii. Is this search optimal for this problem? 1. 2. Bidirectional search: i. Can this search be used on this problem? If not, why not? ii. Is this search complete for this problem? ii. Is this search optimal for this problem? Which searching algorithm best suits this problem? 3.

Answer 1

1.a.

Depth First Search is not applicable for Queens problem. Because the places are fixed before only and it is related to search and not fixing or deciding to place anything. DFS is related to graphical and here we won't deal with graphs.

Since we don't choose DFS, there is no question of 1.b and 1.c.

2.a.
Bidirectional search is also not applicable for our problem because, bidirectional search has predefined start and destination nodes, but in our 8 queens problem; we can't decide the position of 8th queen until and unless we fix our 7 queens before.

Since we don't choose Bidirectional search also , there is no question of 2.b and 2.c.

3.
Brute force and back-tracking are used ; preferably backtracking is used.

How back-tracking works:

1. Place a queen in first column;
2.place 2nd one in 2nd column at first possible place such that it is not attacked by 1st and vice versa.
3.Similarly remaining; if you are facing a problem at placing any queen, replace the before queen at second possible place; if still the problem continues go back-tracking the previous queens ......
4. Finally you will get the solution.

1
				1
	1
					1
		1
						1
			1
							1

The 1's in the 8x8 table above are the positions of 8 queens after applying back-tracking.

Hope this helps you :)