Report

Data Structures and Algorithms (CS210/ESO207/ESO211) Lecture 12 • Application of Stack and Queues • • Shortest route in a grid with obstacles 8 queen’s problem 1 Problem 1 Shortest route in a grid with obstacles 2 Shortest route in a grid From a cell in the grid, we can move to any of its neighboring cell in one step. From top left corner, find shortest route to each cell avoiding obstacles. 3 The input grid is given as a Boolean matrix G such that G[i,j] = 0 if (i,j) is an obstacle, and 1 otherwise. 3 Step 1: Realizing the nontriviality of the problem 4 Shortest route in a grid nontriviality of the problem Definition: Distance of a cell c from another cell c’ is the length (number of steps) of the shortest route between c and c’. We shall design algorithm for computing distance of each cell from the start-cell. As an exercise, you should extend it to a data structure for retrieving shortest route. 5 Get inspiration from nature Did you ever notice the way ripples on the surface of water travel in the presence of obstacles ? The ripples travels along the shortest route ? 6 Shortest route in a grid nontriviality of the problem How to find the shortest route to in the grid ? Create a ripple at the start cell and trace the path it takes to 7 Shortest route in a grid propagation of a ripple from the start cell 8 Shortest route in a grid ripple reaches cells at distance 1 after step 1 9 Shortest route in a grid ripple reaches cells at distance 2 after step 2 10 Shortest route in a grid ripple reaches cells at distance 3 after step 3 11 Shortest route in a grid ripple reaches cells at distance 8 after step 8 Watch the next few slides carefully. 12 Shortest route in a grid ripple reaches cells at distance 9 after step 9 13 Shortest route in a grid ripple reaches cells at distance 10 after step 10 14 Shortest route in a grid ripple reaches cells at distance 11 after step 11 15 Shortest route in a grid ripple reaches cells at distance 12 after step 12 16 Shortest route in a grid ripple reaches cells at distance 13 after step 13 17 Shortest route in a grid ripple reaches cells at distance 14 after step 14 18 Shortest route in a grid ripple reaches cells at distance 15 after step 15 19 Step 2: Designing algorithm for distances in grid (using an insight into propagation of ripple) 20 Shortest route in a grid A snapshot of ripple after i steps : the cells of the grid at distance i from the starting cell. 21 Shortest route in a grid A snapshot of the ripple after i+1 steps + Can We generate + from ? 22 How can we generate + from ? Observation: Each cell of + is a neighbor of a cell in . But every neighbor of may be a cell of − or a cell of + . Question: How to distinguish between a cell of − from + ? Key idea: Suppose we initialize Distance[c] of each cell as ∞ in the start of the algorithm; and set Distance[c] appropriately whenever the algorithm visits (ripple reaches) c. Then just after our algorithm has visited , for every neighbor b of a cell in , • If b is in − , Distance[b] = ??some number less than • If b is in + , Distance[b] = ?? ∞ Now can you use the above idea to design an algorithm to generate + from ? 23 Algorithm to compute + if we know Compute-next-layer(G, ) { CreateEmptyList(+ ); For each cell c in For each neighbor b of c which is not an obstacle { if (Distance[b] = ∞) { Insert(b, + ); Distance[b] i+1 ; } } return + ; } 24 The first (not so elegant) algorithm (to compute distance to all cells in the grid) Distance-to-all-cells(G, 0 ) It can be as high as O( ) { {0 }; For(i = 0 to ?? ) + Compute-next-layer(G, ); } The algorithm is not elegant because of • ?? • So many temporary lists that get created. 25 How to transform the algorithm to an elegant algorithm ? Key points we have observed: • We can compute cells at distance i+1 if we know all cells up to distance i. • Therefore, we need a mechanism to enumerate the cells of the grid in non-decreasing order of distances from the start cell. How to design such a mechanism ? 26 Keep a queue Q Q + 27 An elegant algorithm (to compute distance to all cells in the grid) Distance-to-all-cells(G, 0 ) CreateEmptyQueue(Q); Distance(0 ) 0; Enqueue(0 ,Q); While( Not IsEmptyQueue(Q) ?? ) { c Dequeue(Q); For each neighbor b of c which is not an obstacle { if (Distance(b) = ∞) Distance(c) { Distance(b) ?? +1 ; Enqueue(b,??Q); ; } } } 28 Proof of correctness of algorithm Question: What is to be proved ? Answer: At the end of the algorithm, Distance[c]= the distance of cell c from the starting cell in the grid. Question: How to prove ? Answer: By the principle of mathematical induction on the distance from the starting cell. Inductive assertion: P(i): The algorithm correctly computes distance to all vertices at distance i from the starting cell. As an exercise, try to prove P(i) by induction on i. 29 Problem 2 Placing 8 queens safely on a chess board It was explained on the black board. However, for a better understanding, the slides are also provided here. 30 8 queen problem Find a way to place 8 queens on a chess board so that no two of them attack each other. 31 First some notations and definitions are provided in order • to have a better insight into the problem. • to describe the idea underlying the algorithm compactly. • to describe the algorithm in a formal manner. 32 A Configuration of 8 queens on chess board where each row has exactly one queen 1 2 3 4 5 6 7 8 Q 8 Q 7 Q 6 Q 5 Q 4 Q 3 2 Q 1 Q Each configuration can be specified by a vector <1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 > where is the column number of the queen placed in ith row. For example, the above configuration can be represented by <1,1,3,4,6,4,8,7> 33 Configuration of 8 queens on chess board where each row has exactly one queen <1,1,3,4,6,4,8,7> Most significant digit Least significant digit Lexicographic ordering: We can define a lexicographic ordering among all configurations. For example, <1,5,2,8,9,9,6,7> appears before <2,1,1,1,1,1,1,2>. Definition: A configuration of 8 queens is a safe configuration if no two queens in the configuration attack each other. Aim: To compute a safe configuration of 8 queens on a chess board. 34 To compute a safe configuration of 8 queens A trivial solution: Enumerate all configurations of 8 queens in lexicographic ordering and then search this enumeration for a safe configuration. A clever approach: also searches for a safe configuration by exploring configurations lexicographically but in a conservative manner as follows. • Searches for a safe configuration in an incremental fashion : placing queens one by one and cautiously. • As soon as it is realized that a partial configuration is currently unsafe or will only lead to unsafe configurations, it stops, backtracks, and tries the next potential partial configuration. (See animation on the following slide to get an idea) 35 A clever approach to search for safe configuration An overview 1 2 3 4 5 8 6 7 8 Place queen of the 1st row in 1st column. • It is unsafe to place second queen at 1st column or 2nd column of 2nd row. No need to generate configurations <1,1,*,*,*,*,*,*> or <1,2,*,*,*,*,*,*>. 7 6 5 4 Q 3 Q 2 1 Q So we proceed with <1,3,*,*,*,*,*,*>. • All configurations with <1,3,k,*,*,*,*,*> are unsafe for k<5. No need to generate these unsafe configurations. So we proceed with <1,3,5,*,*,*,*,*>. … and so on … 36 A clever approach to search for safe configuration An overview of general step Let <1 , 2 , … , , ∗, ∗, ∗> be a safe configuration of first i queens. Because we are enumerating configurations in lexicographic order 1 2 3 4 5 6 8 7 + 6 5 4 3 2 1 7 8 We try to place queen + in the leftmost safe position in i+1th row. If such a position exists, we place + and proceed to (i+2)th row. If no safe position exists in i+1th row, safe then <1 , 2 , … , , ∗, ∗, ∗> is unsafe. To search for the next lexicographic configuration which will be safe, we search for the next leftmost safe position for in ith row. 37 Implementation of the clever approach An important terminology: Given a partial configuration of i queens placed on first i rows of the chess, • A queen is said to be safe if it is not attacked by any other queen lying in any row below it. • A queen is said to be unsafe if it is attacked by at least one queen lying in any row below it. • A queen is uncertain if it is not known yet whether it is safe or unsafe. Representation of a partial configuration: Each queen in a partial configuration will be specified by a triplet <r,c,Flag>, where r and c are the row and column of the cell where the queen is placed. Flag is a variable which takes one of the values from {safe, unsafe, uncertain } as explained above. 38 Implementation of the clever approach A snapshot of the algorithm At each stage, our algorithm will maintain a partial configuration <1 , 2 , … , , +1 , ∗, ∗, ∗> where • The first i queens are safe. • The queen at i+1th place will be safe/unsafe/ uncertain See the following slide for a visual description of a partial configuration at any stage of our algorithm. 39 Implementation of the clever approach A snapshot of the algorithm safe/ Unsafe/ uncertain + + safe A step taken by our algorithm will depend upon the status of Flag of + . Our approach of enumerating configurations in lexicographic order hints at using a suitable data structure effectively. Can you guess it ? stack S For queens 40 A single step of the algorithm Let the stack have + queens at present. We take out + . (Answer the following questions to get a good understanding of the algo) • If + is uncertain: what should be done ? We determine if it is attacked by any existing queen and change its status as safe or unsafe accordingly, and push it back into stack. • If + is safe: what should be done ? If + = , we are done; otherwise, push + back into the stack and place a queen in the 1st column of ( + ) th row and mark it uncertain. • If + is unsafe: what should be done ? We can shift + to the next available column. But if it was already in 8th column, we mark unsafe. 41 Finally, The following slide has a simple and elegant implementation of the clever approach we discussed… 42 An elegant algorithm for 8 queens problem CreateEmptyStack(S); Push((1,1,safe), S); While (Not IsEmptyStack(S)) do { (r,c,flag) Top(S); Pop(S); 3 Cases: { Flag is uncertain : If ((r,c) does not attack any existing queen) Push((r,c,safe), S); else Push((r,c,unsafe), S); Flag is safe : If (r = 8) { // we reached a safe configuration of 8 queens print the solution and empty the stack S; } else { Push((r,c,safe), S); Push((r+1,1,uncertain), S)}; Flag is unsafe : If (c = 8) { (r’,c’,flag’) Top(S); Pop(S); Push((r’,c’,unsafe), S); } else Push((r,c+1, uncertain), S); } 43 Homework exercises 1. 2. 3. 4. 5. Now that you know the clever algorithm, give reason for pursuing lexicographic approach in the search of a safe configuration by it. Extend the algorithm for computing a safe configuration for n queens on n by n chess board for any n. The current algorithm finds just one safe configuration. Modify it to enumerate all safe configurations. If you love programming, implement the clever algorithm and trivial algorithm and see if the clever algorithm is indeed mush faster than the trivial algorithm. We have given an iterative implementation of the clever algorithm. Can you design a recursive implementation as well ? Which of them will be faster in practical implementation, and why ? 44