Backtracking-N Queens Problem-Graph Coloring-Hamiltonian cycle

Analysis & Design of Algorithms
Backtracking
N-Queens Problem
Hamiltonian circuit
Graph coloring
A presentation on unit Backtracking from the ADA subject of Engineering.

1. ANALYSIS AND DESIGN OF ALGORITHM BACKTRACKING

2. Backtracking N-Queens’ Problem Gra ph Coloring   Hamiltonian Circuits

3. Backtracking Ba cktracking  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 ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution. What is meant by possible solutions and how these are differentiated from the impossible ones are issues specific to the problem being solved. function backtrack(current depth) if solution is valid return / print the solution else for each element from A[ ] source array let X[current depth] ß element if possible candidate (current depth + 1) backtrack(current depth + 1) end if end for end if end function

4. Backtracking Technique Backtracking is used to solve problems in which a feasible solution is needed rather than an optimal one, such as the solution to a maze or an arrangement of squares in the 15-puzzle. Backtracking problems are typically a sequence of items (or objects) chosen from a set of alternatives that satisfy some criterion. 13 9 5 7 8 1 2 3 4 10 6 14 15 11 12 6 10 14 15

5. Backtracking Implementation Backtracking is a modified depth-first search of the solution-space tree. In the case of the maze the start location is the root of a tree, that branches at each point in the maze where there is a choice of direction.

6. N-QUEENS’ PROBLEM

7. Backtracking Backtracking is a technique used to solve problems with a large search space, by systematically trying and eliminating possibilities. A standard example of backtracking would be going through a maze. At some point in a maze, you might have two options of which direction to go: Junction Portion A Portion B

8. Backtracking Junction Portion B Portion A One strategy would be to try going through Portion A of the maze. If you get stuck before you find your way out, then you "backtrack" to the junction. At this point in time you know that Portion A will NOT lead you out of the maze, so you then start searching in Portion B

9. Backtracking Clearly, at a single junction you could have even more than 2 choices. The backtracking strategy says to try each choice, one after the other, if you ever get stuck, "backtrack" to the junction and try the next choice. If you try all choices and never found a way out, then there IS no solution to the maze. Junction B C A

10. Backtracking – Eight Queens Problem Find an arrangement of 8 queens on a single chess board such that no two queens are attacking one another. In chess, queens can move all the way down any row, column or diagonal (so long as no pieces are in the way). Due to the first two restrictions, it's clear that each row and column of the board will have exactly one queen.

11. Eight Queens Problem The backtracking strategy is as follows: Place a queen on the first available square in row 1 . Move onto the next row, placing a queen on the first available square there (that doesn't conflict with the previously placed queens). Continue in this fashion until either: you have solved the problem, or you get stuck. When you get stuck, remove the queens that got you there, until you get to a row where there is another valid square to try. Q Q Q Q Q Q Continue…

12. Eight Queens Problem When we carry out backtracking, an easy way to visualize what is going on is a tree that shows all the different possibilities that have been tried. On the board we will show a visual representation of solving the 4 Queens problem (placing 4 queens on a 4x4 board where no two attack one another).

13. Eight Queens Problem The neat thing about coding up backtracking, is that it can be done recursively, without having to do all the bookkeeping at once. Instead, the stack or recursive calls does most of the bookkeeping (ie, keeping track of which queens we've placed, and which combinations we've tried so far, etc.)

14. void solveItRec ( int perm[], int location, struct onesquare usedList []) { if (location == SIZE) { printSol (perm); } for ( int i =0; i <SIZE; i ++) { if ( usedList [ i ] == false) { if (!conflict(perm, location, i )) { perm[location] = i ; usedList [ i ] = true; solveItRec (perm, location+1, usedList ); usedList [ i ] = false; } } } } perm[] - stores a valid permutation of queens from index 0 to location-1. location – the column we are placing the next queen usedList [] – keeps track of the rows in which the queens have already been placed. Found a solution to the problem, so print it! Loop through possible rows to place this queen. Only try this row if it hasn’t been used Check if this position conflicts with any previous queens on the diagonal mark the queen in this row mark the row as used solve the next column location recursively un-mark the row as used, so we can get ALL possible valid solutions.

15. 8 queens problem - Analysis Another possible brute-force algorithm is generate the permutations of the numbers 1 through 8 (of which there are 8! = 40,320), and uses the elements of each permutation as indices to place a queen on each row. Then it rejects those boards with diagonal attacking positions. The backtracking algorithm, is a slight improvement on the permutation method, constructs the search tree by considering one row of the board at a time, eliminating most non-solution board positions at a very early stage in their construction. Because it rejects row and diagonal attacks even on incomplete boards, it examines only 15,720 possible queen placements. A further improvement which examines only 5,508 possible queen placements is to combine the permutation based method with the early pruning method: The permutations are generated depth-first, and the search space is pruned if the partial permutation produces a diagonal attack

16. GRAPH COLORING Analysis & Design of Algorithms

17. What is Graph Coloring ? Graph Coloring is an assignment of colors to the vertices of a graph such that no two adjacent vertices have the same color that too by using the minimum number of colors . The smallest number of colors needed to color a graph  G   is called its  chromatic number , and is often denoted χ( G ).

18. SOLUTION Unfortunately, there is no efficient algorithm available for coloring a graph with minimum number of colors but  there are approximate algorithms to solve the problem such as the Greedy Algorithm & Backtracking Algorithm,  The basic Greedy Algorithm to assign colors It doesn’t guarantee to use minimum colors , but it guarantees an upper bound on the number of colors . The basic algorithm never uses more than d+1 colors where d is the maximum degree of a vertex in the given graph .

19. Greedy Algorithm The greedy algorithm considers the vertices in a specific order v1,v2,v3... & assigns to “ ith ” vertice ,the smallest available color not used by “ ith ” vertice’s neighbours among v1,v2...v(ith-1), adding a fresh color if needed. The quality of the ordering depends on the chosen ordering .There exists an ordering that leads to a greedy coloring with the optimal number of χ( G ) colors .

20. Using Backtracking Given an undirected graph and a number m, the solution is to color the graph with at most m colors such that no two adjacent vertices of the graph are colored with same color . In this algorithm , the graph is represented by its boolean adjacency matrix G[1:n,1:n]. Here K is the index of the next vertex to color .

21. Backtracking Algorithm mColoring (k) { repeat { NextValue (k); // ASSIGN A COLOR if (x[k]=0) then return; //NO COLOR POSSIBLE if(k=n) then //AT MOST M COLORS USED TO COLOR N VERTICES write(x[1:n]); else mColoring (k+1); }until (false); } NextValue (k) { repeat { x[k]=(x[k+1) mod (m+1); //NEXT HIGGEST COLOR if(x[k]=0) then return ; //ALL COLORS USED for j=1 to n do { if((G[ k,j ]!=0) and (x[k]=x[j])) //CHECK IF ADJACENT COLOR IS DIFFERENT then break; } if(j=n+1) then return; //NEW COLOR FOUND }until(false); //FIND ANOTHER COLOR }

22. Applications #Helps in a no. Of scheduling problems #Register allocation #Pattern matching #Sports scheduling #Designing seating plans #Designing Time-Table #Solving sudoku #etc.

23. Example Graph coloring with greedy algorithm

24. Graph coloring with backtracking

25. HAMILTONIAN CIRCUIT

26. HAMILTONIAN CYCLE Definitions: - A Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian path that is a cycle. A Hamiltonian cycle is a cycle that visits each vertex exactly once (except for the vertex that is both the start and end, which is visited twice). A graph that contains a Hamiltonian cycle is called a Hamiltonian graph. Examples:- The graph of every platonic solid is a Hamiltonian graph. Every complete graph with more than two vertices is a Hamiltonian graph.

27. HAMILTONIAN CYCLE ALGORITHM EXAMPLE

28. ALGORITHM FOR HAMILTONIAN CYCLE FOR NEXT VERTEX Algorithm NextValue (k) /* x[1:k-1] is a path of k-1 distinct vertices. If x[k] = 0, then no vertex has as yet been assigned to x[k]. After execution, x[k] is assigned to the next highest numbered vertex which does not already appear in x[1:k-1] and is connected by an edge to x[k-1]. Otherwise x[k]=0. If k=n, then in addition x[k] is connected to x[1 ].*/ { repeat { x[k] =(x[k]+1) mod (n+1);//Next Vertex. if (x[k]=0) then return; if(G[x[k-1],x[k]]!=0) then { //Is there an edge? for j=1 to k-1 do if(x[j]=x[k]) then break ; // check for distinctness if(j=k) then //If true, then the vertex is distinct. if((k<n) or ((k=n) and G[x[n],x[1]]!=0)) then return ; } }until(false); }

29. ALGORITHM FOR HAMILTONIAN CYCLE FOR FINDING ALL HAMILTONIAN CYCLE Algorithm Hamiltonian(k) //This algorithm uses the recursive formulation of backtracking to find all the //Hamiltonian cycles of a graph. The graph is stored as an adjacency matrix //G[1:n,1:n]. All cycles begin at node 1. { repeat { // Generate values for x[k ]. NextValue (k); //Assign a legal next value to x[k ]. if(x[k]=0) then return; if(k=n) then write(x[1:n]); else Hamiltonian(k+1); }until(false); }

30. PREPARED BY:- B-TECH CSE BATCH-2 15013088 15013089 15013090 15013091 1 5013092