Implementation of N-queens problem using backtracking technique.

Experiment No: AI-

TITLE: - Implementation of N-queens using backtracking/Branch –Bound  

Problem Statement: - Implement constraint satisfaction problem for N-Queens

Objective:

·        To study about Constraint satisfaction problem.

·        To study about algorithm for N-queen based on backtracking.

Requirements (Hw/Sw): PC, Linux OS

 

Theory:

 

1. Eight queens’ puzzle

                                   The eight queens’ puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n-queens problem of placing n queens on an n×n chessboard, where solutions exist for all natural numbers n with the exception of n=2 and n=3.The problem can be quite computationally expensive as there are 4,426,165,368 (i.e., 64C8) possible arrangements of eight queens on an 8×8 board, but only 92 solutions. It is possible to use shortcuts that reduce computational requirements or rules of thumb that avoids brute-force computational techniques. For example, just by applying a simple rule that constrains each queen to a single column (or row), though still considered brute force, it is possible to reduce the number of possibilities to just 16,777,216 (that is, 88) possible combinations. Generating permutations further reduces the possibilities to just 40,320 (that is, 8!), which are then checked for diagonal attacks.

2. Backtracking :

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution.

3. Branch & Bound

A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm.

                   The algorithm depends on efficient estimation of the lower and upper bounds of regions/branches of the search space. If no bounds are available, the algorithm degenerates to an exhaustive search.

·        Where backtracking uses a depth-first search with pruning, the branch and bound algorithm

Uses a breadth-first search with pruning Branch and bound uses a queue as an auxiliary data structure

·        Starting by considering the root node and applying a lower-bounding and upper bounding

Procedure to it, If the bounds match, then an optimal solution has been found and the algorithm is finished, If they do not match, then algorithm runs on the child nodes

·        In many types of problems, branch and bound is faster than branching, due to the use of a breadth-first search instead of a depth-first search

·        The worst case scenario is the same, as it will still visit every node in the tree

Steps for Problem Solving:-

 Placethe first queen in the left upper corner of the table.

 Save the attacked positions.

 Move to the next Queen

(which can only be placed to the next line).

 Search for valid position. If there is one go to step8.

 There isn’t a valid position for the Queen. Delete it (the x coordinate is 0).

 Move to the previous Queen.

 Go to step4.

 Place it to the first valid position.

 Save the attacked positions.

 If the Queen processed is the last stop otherwise go to step3.

General structure of a Solution using Backtracking

public ... backtrackSolve("problem N")

{

if ( "problem N" is a solved problem )

{

print "(solved) problem N"; // It's a solution !

return;

}

for ( each possible step S you can make in "problem N" )

{

if ( step S is a legal move )

{

Make step S;

backtrackSolve("problem N-1");

Take step S back;

}

}

}

Solving 8 queen problem by backtracking:

            The 8 queen problem is a case of more general set of problems namely “n queen problem”. The basic idea: How to place n queen on n by n board, so that they don’t attack each other. As we can expect the complexity of solving the problem increases with n. We will briefly introduce solution by backtracking. First let’s explain what is backtracking? The boar should be regarded as a set of constraints and the solution is simply satisfying all constraints. For example: Q1 attacks some positions, therefore Q2 has to comply with these constraints and take place, not directly attacked by Q1. Placing Q3 is harder, since we have to satisfy constraints of Q1 and Q2. Going the same way we may reach point, where the constraints make the placement of the next queen impossible. Therefore we need to relax the constraints and find new solution. To do this we are going backwards and finding new admissible solution. To keep everything in order we keep the simple rule: last placed, first displaced.

            In other words if we place successfully queen on the ith column but cannot find solution

for (i+1)th queen, then going backwards we will try to find other admissible solution for the ith queen first. This process is called backtrack Let’s discuss this with example. For the purpose of this handout we will find solution of 4 queen problem.

Algorithm:

- Start with one queen at the first column first row

- Continue with second queen from the second column first row

- Go up until find a permissible situation

- Continue with next queen

We place the first queen on A1:

Again with red we show the prohibited positions. It turned out that we cannot place the third queen on the third column (we have to have a queen for each column!). In other words we imposed a set of constraints in a way that we no longer can satisfy them in order to find a solution. Hence we need to revise the constraints or rearrange the board up to the state which we were stuck. Now we may ask a question what we have to change. Since the problem happened after placing Q2 we are trying first with this queen. OK we know that there were to possible places for Q2. B3 gives problem for the third queen, so there is only one position left – B4:

Now it is easy to see that Q2 goes to B4, Q3 goes to C1 and Q4 takes D3:

To find this solution we had to perform two backtracks. So what now? In order to find all solutions we use as you can guess – backtrack! Start again in reverse order we try to place Q4 somewhere up, which is not possible. We backtrack to Q3 and try to find admissible place different from C1. Again we need to backtrack. Q2 has no other choice and finally we reach Q1. We place Q1 on A3:

Continuing further we will reach the solution on the right. Is this distinct solution? No it is rotated first solution. In fact for 4x4 board there is only one unique solution. Placing Q1 on A4 has the same effect as placing it on A1. Hence we explored all solutions. How implement backtrack in code. Remember that we used backtrack when we cannot find admissible position for a queen in a column. Otherwise we go further with the next column until we place a queen on the last column.

Therefore your code must have

fragment:

int PlaceQueen(int board[8], int row)

If (Can place queen on ith column)

PlaceQueen(newboard, 0)

Else

PlaceQueen(oldboard,oldplace+1)

End

If you can place queen on ith column try to place a queen on the next one, or backtrack

and try to place a queen on position above the solution found for i-1 column.
                                 

Click Here To Download N-queen Program Java

Click Here to Download N-queen.cpp program

Algorithm:

Input:

Output:

Mathematical Modelling:

Conclusion: