data structures- back tracking

back tracking

1. BACKTRACKING,GENERAL METHOD , 8 QUEEN’S PROBLEM S.Nandhini II – Msc(CS&IT ) Nadar Saraswathi College Of Arts And Science Theni.

2. BACKTRACKING General method Problems searching for a set of solutions or Which require an optimal solution can be solved using the backtracking method. To apply the backtracking method, the solution must be expressible as an n- tuple (x1…..xn). Where xi are chosen from finite set si. The solution vector must satisfy the criterion function p(x1…….xn).

3. Backtracking algorithm EXAMPLE: Find path through maze Start at beginning of maze If at exit ,return true Else for each step from current location Recursively Find path Return with first successfull step Return false if all steps fail

4. RECURSIVE BACKTRACKING Pseudo code for recursive backtracking algorithms If at a solution return success for(every possible choice from current state/node) Make that choice and take one step along path Use recursive to solve the problem for the new node/state If the recursive call succeeds report the success to the next high level Back out of the current choice to restore the state at the beginning of the loop. Report failure

5. Backtracking algorithm

6. 8 queen’s problem The 8 queens problem puzzle is the problem of placing eight chess queens an on 8. 8 chessboard so that no two queens attack each other. Thus a solution requires that no two queens share the same row, column , diagonal. The eight queens puzzle is an example of the more general n-queens problem of placing n queens on an n n chessboard.

7. Where solution exist for all natural numbers n with the exception of 1,2 and 3 The solution possibilities are discovered only up to 23 queen.

8. 8 queen’s Algorithm All solutions to the n-queens problem A lgorithm 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 NQueens9(k+1.n); } } }

9. 8 queen’s problem

10. Formulation: Status Any arrangement of 0 to 8 queens on the board Initial state 0 queens on the board Successor function Add a queen in any square Goal test 8 queens on the board ,none attacked

11. EXAMPLE 8 Queens 1 2 3 4 5 (8,5,4,3,2)=1649

12. 1 2 3 4 5 6 (8,5,3,1,2,1)=769

13. THANK YOU