DEPARTMENT OF COMPUTER ENGINEERING

Module 5
Question Bank

1. What is N Queen Problem? Show the solution for 8 Queen problem

N - Queens problem is to place n - queens in such a manner on an n x n chessboard that no queens

attack each other by being in the same row, column or diagonal.

It can be seen that for n =1, the problem has a trivial solution, and no solution exists for
n =2 and n =3. So first we will consider the 4 queens problem and then generate it to n -
queens problem.

Given a 4 x 4 chessboard and number the rows and column of the chessboard 1 through 4.

Since, we have to place 4 queens such as q1 q2 q3 and q4 on the chessboard, such that no
two queens attack each other. In such a conditional each queen must be placed on a
different row, i.e., we put queen "i" on row "i."

Now, we place queen q1 in the very first acceptable position (1, 1). Next, we put queen q2 so
that both these queens do not attack each other. We find that if we place q2 in column 1 and 2,
then the dead end is encountered. Thus the first acceptable position for q2 in column 3, i.e. (2,
3) but then no position is left for placing queen 'q3' safely. So we backtrack one step and place
the queen 'q2' in (2, 4), the next best possible solution. Then we obtain the position for
placing 'q3' which is
(3, 2). But later this position also leads to a dead end, and no place is found where 'q4' can be
placed safely. Then we have to backtrack till 'q1' and place it to (1, 2) and then all other
queens are placed safely by moving q2 to (2, 4), q3 to (3, 1) and q4 to (4, 3). That is, we get the
solution (2, 4, 1, 3). This is one possible solution for the 4-
queens problem. For another possible solution, the whole method is repeated for all partial
solutions. The other solutions for 4 - queens problems is (3, 1, 4, 2) i.e.
2. Write and explain sum of subset algorithm for n=5,W={2,7,8,9,15}, M=17

3.
 Write a short note on: N Queen Problem with example

4. Give the algorithm for the N-Queen problem and give any 2 solutions to the 8 queen
problem.
5. Explain backtracking with the N Queen Problem.
6. Define chromatic number of graph. Explain graph coloring algorithm.
7. Solve the following sum of subset problem and draw portion of state space tree.
W=(5,7,10,12,15,18,20) and m=35
Find all subsets of of w that sum to m.

8. Write a short note on: Branch and bound strategy

Branch and bound algorithms are used to find the optimal solution for combinatory,
 discrete, and general mathematical optimization problems.

A branch and bound algorithm provide an optimal solution to an NP Hard problem by

exploring the entire search space. Through the exploration of the entire search space, a
branch and bound algorithm identify possible candidates for solutions step-by-step.

Different search techniques in branch and bound:

The Branch algorithms incorporate different search techniques to traverse a state space
tree. Different search techniques used in B&B are listed below:

1. LC search
2. BFS
3. DFS
1. LC search (Least Cost Search):
It uses a heuristic cost function to compute the bound values at each node. Nodes are
added to the list of live nodes as soon as they get generated.
The node with the least value of a cost function selected as a next E node.

[Link](Breadth First Search):

It is also known as a FIFO search.
It maintains the list of live nodes in first-in-first-out order i.e, in a queue, The live nodes are
searched in the FIFO order to make them next E nodes.
3. DFS (Depth First Search):
It is also known as a LIFO search.
It maintains the list of live nodes in last-in-first-out order i.e. in a stack. The live nodes
are searched in the LIFO order to make them next E nodes.

Basic Concepts of Branch and Bound:

▸ Generation of a state space tree:

As in the case of backtracking, B&B generates a state space tree to efficiently search
the solution space of a given problem instance.
In B&B, all children of an E-node in a state space tree are produced before any live
node gets converted in an E-node. Thus, the E-node remains an E-node until i
becomes a dead node.

• Evaluation of a candidate solution:

Unlike backtracking, B&B needs additional factors evaluate a candidate solution:

1. A way to assign a bound on the best values of the given criterion functions to
each node in a state space tree: It is produced by the addition of further
components to the partial solution given by that node.
2. The best values of a given criterion function obtained so far: It describes the
upper bound for the maximization problem and the lower bound for the
minimization problem.
• A feasible solution is defined by the problem states that satisfy all the given
constraints.
• An optimal solution is a feasible solution, which produces the best value of a
 given objective function.
• Bounding function :
It optimizes the search for a solution vector in the solution space of a given problem
instance.

It is a heuristic function that evaluates the lower and upper bounds on the possible solutions
at each node. The bound values are used to search the partial solutions leading to an optimal
solution. If a node does not produce a solution better than the best solution obtained thus far,
then it is abandoned without further exploration.

The algorithm then branches to another path to get a better solution. The desired solution to
the problem is the value of the best solution produced so far.

▸ The reasons to dismiss a search path at the current node : (i) The bound value of the node
is lower than the upper bound in the case of the maximization problem and higher than the
lower bound in the case of the minimization problem. (i.e. the bound value of the ade is not
better than the value of the best solution obtained until that node).

(ii) The node represents infeasible solutions, de violation of the constraints of

the problem.

(iii) The node represents a subset of a feasible solution containing a single point. In this
case, if the latest solution is better than the best solution obtained so far the best solution
is modified to the value of a feasible solution at that node.
9. Write an algorithm for sum of subsets. Solve the following.
M=30 W=(5,10,12,13,15,18)

10. Write a short note on:8 queen problem