A F1008 Pages: 4

0 1 8 1 4
1 0 12 4 9
W=|8 12 0 7 3
1 4 7 0 2
49 3 2 0,

18 a) State and Explain N Queens Problem. Write the backtracking algorithm for solving N
Queens problem.
b) Show the state space tree for 4 Queens problem. Show the steps in solving 4 Queens
problem using backtracking method to print all the solutions.
19 a) Explain Branch and Bound method for solving Travelling Salesman Problem.
b) Solve Travelling Salesman problem for the following graph using Branch and Bound

Technique.

20 a) Define NP- Hard and NP — Complete Problems.
b) What are the steps used to show a given problem is NP-Complete?

c) Write notes on polynomial time reducibility. Give Examples.

oh ‏بد‎ oR

Page 4 of 4

(5)

(5)

(5)
(5)

(2)
(4)
(4)