N-queens.pptx

N-queens problem in advanced algorthms uses backtracking aproach.

1. The N-Queens problem Presented By: Anoop Chaudhary A S eminar on

2. Introduction to N-Queens Problem Constraints and Solution Space The Backtracking Approach Solution to 4-Queens Problem using backtracking Algorithm for N-Queens Problems Time complexity of N-Queens algorithm Advantages of using backtracking Contents: 2

3. What is a queen ? A queen is one of six different chess pieces. It can move any distance available vertically, horizontally or diagonally on the 8 x 8 grid of chessboard. 3 Figure 1: Movement of a Queen on a Chessboard

4. Introduction to N-Queens Problem 4 Place n queens on an n x n chessboard such that no two queens attack each other. One solution to each n-queens problem for n=4,6 and 8 4-queens 6 -queens 8 -queens

5. History 5 1848: Problem proposed by Max Bezzel. 1850: Friedrich Gauss claims Q(8)=92 1874: Dr. Glaisher prove Gauss’s claim 1874: Paul proves that Q(n)>0 for all n>=4 20 th Century : Problem became a benchmark for combinatorial optimization N-Queen problem is generalized form of 8-Queens problem

6. Assumption: Queen i is to be placed on row i . Hence, all solutions to the N-queens problem can be represented as n- tuples (x 1 , …, x n ), where x i is the column on which queen i is placed. Explicit Constraints: x i are chosen from set S i ={1, …, n} and 1<= i <=n. So the Solution space consists of n n n- tuples . Implicit Constraints: No two x i ’s can be same Now, the solution space reduced to n! No two queens can be on the same diagonal. Constraints of N-Queens Problem 6 (2, 4, 1, 3)

7. The Solution Space of N-Queens Problem 7 The solution space for the N-Queens problem can be represented using a State Space Tree – The root of the tree represents 0 choices. Nodes at depth 1 represent first choice. Nodes at depth 2 represents the second choice, and so on till depth n. Edges from depth i to i+1 are labeled with the values of x i. In this tree a path from a root to a leaf represents a candidate solution and All the candidate solutions define the solution space.

8. Example: 4-Queens Problem 8 State Space Tree:

9. The Backtracking Approach 9 Backtracking is a standard method to find solutions for a particular kind of problems known as “ Constraint-Satisfaction-Problems ”. Backtracking is finding the solution of a problem whereby the solution depends on the previous steps taken. Thus the general steps of backtracking are : Start with a sub-solution (partial candidate) Check if partial candidate will lead to the solution or not. If not, then come back and change the partial candidate and continue again. Backtracking can be seen as a form of intelligent depth-first search (DFS).

10. Example: 4-Queens Problem Q Q . . Q Q Q . . . . Q Q . Q Q Q Q . . . . Q Q . . . Q Q Q Q . . Q a b c d e f g h 10

11. State Space tree, generated during backtracking 11 *  The B denotes the dead node.

12. Algorithm for N-Queens Problems Place ( k,  i ) {         for  j  ←  1  to  k - 1   do // Check if two queens in same column or in same diagonal       if ( x [ j ] ==  i )  or  ( Abs  x [ j ]) -  i )  ==  (Abs ( j - k ) ) then return false;        return true;   }    Returns true if a queen can be placed in k th row and i th column. Otherwise returns false. x [] is a global array whose first ( k-1 ) values have been set. Abs( r ) returns the absolute value of r . 12

13. Algorithm for N-Queens Problems NQueens( k, n )  {       for   i  ←  1   to   n     do   {         if  Place ( k,  i )  then {            x [ k ]  ←   i ;          if  ( k ==n )   then   write  ( x [1 : n] );           else   NQueens( k + 1, n );       }    } }    13

14. Complexity 14 Time complexity of N queens algorithm :  For finding a single solution where the first queen Q has been assigned the first column and can be put on N positions, the second queen has been assigned the second column and would choose from N-1 possible positions and so on; the time complexity is O ( N ) * ( N - 1 ) * ( N - 2 ) * … 1 ). i.e The worst-case time complexity is O(N!) . Thus, for finding all the solutions to the N Queens problem the time complexity runs in  polynomial time .

15. Advantages of using backtracking 15 Ability to find and count all the possible solutions rather than just one. Parallel version of algorithm can increase speed several times.

16. References 16 “Computer Algorithms” by Ellis Horowitz, Sartaz Sahni and Rajashekharan printed by Computer Science Press. The n-Queens Problem, Article in “ The American Mathematical Monthly”  101(7)- August 1994, DOI: 10.2307/2974691 http://mathcenter.oxford.emory.edu/site/cs171/nQueensProblemAndBacktracking/

17. Thank You