The 3-Coloring Problem Example: a b C d e
◼ Example: a The 3-Coloring Problem b c d e
The 3-Coloring Problem There are two important observations to be noted, which generalize to all backtracking algorithms: (1)The nodes are generated in a depth-first-search manner. (2)There is no need to store the whole search tree;we only need to store the path from the root to the current active node.In fact,no physical nodes are generated at all;the whole tree is implicit.We only need to keep track of the color assignment
The 3-Coloring Problem There are two important observations to be noted, which generalize to all backtracking algorithms: (1) The nodes are generated in a depth-first-search manner. (2) There is no need to store the whole search tree; we only need to store the path from the root to the current active node. In fact, no physical nodes are generated at all; the whole tree is implicit. We only need to keep track of the color assignment
The 3-Coloring Problem Recursive Algorithm Input:An undirected graph G=. Output:A 3-coloring d1...n]of the vertices of G,where each dil is 1,2,or 3. 1.for k-1to n 2.d←-0； 3.end for; 4.flagk-false; 5.graphcolor(1); 6.if fag then output c 7.else output "no solution"; graphcolor k) 1.for color作1to3 2.K←-color; 3.if cis a legal coloring then set fag<true and exit; 4. else if cis partial then graphcolor(k+1); 5,end for;
The 3-Coloring Problem Recursive Algorithm Input: An undirected graph G=(V, E). Output: A 3-coloring c[1…n] of the vertices of G, where each c[j] is 1, 2, or 3. 1. for k1 to n 2. c[k]0; 3. end for; 4. flagfalse; 5. graphcolor(1); 6. if flag then output c; 7. else output “no solution”; graphcolor(k) 1. for color=1 to 3 2. c[k]color; 3. if c is a legal coloring then set flag true and exit; 4. else if c is partial then graphcolor(k+1); 5. end for;
The 3-Coloring Problem Iterative Algorithm Input:An undirected graph G=,E). Output:A 3-coloring d1...]of the vertices of G where each di]is 1,2,or 3. 1.for k1 to n 2.d←-0； 3.end for; 4.fag-false; 5.k-1; 6.while 1 7. while d2 8. ①←+1； 9. if cis a legal coloring then set fag-true and exit from the two while loops; 10. else if cis partial then+1; 11. end while; 12. ←-0； 13. k-k1; 14.end while; 15.if fag then output c 16.else output "no solution";
The 3-Coloring Problem Iterative Algorithm Input: An undirected graph G=(V, E). Output: A 3-coloring c[1…n] of the vertices of G, where each c[j] is 1, 2, or 3. 1. for k1 to n 2. c[k]0; 3. end for; 4. flagfalse; 5. k1; 6. while k1 7. while c[k]2 8. c[k]c[k]+1; 9. if c is a legal coloring then set flagtrue and exit from the two while loops; 10. else if c is partial then kk+1; 11. end while; 12. c[k]0; 13. kk-1; 14. end while; 15. if flag then output c; 16. else output “no solution”;
The 8-Queens Problem How can we arrange 8 queens on an 8x8 chessboard so that no two queens can attack each other? Two queens can attack each other if they are in the same row,column or diagonal. The n-queens problem is defined similarly,where in this case we have n queens and an nxn chessboard for an arbitrary value of n1
The 8-Queens Problem ◼ How can we arrange 8 queens on an 88 chessboard so that no two queens can attack each other? ◼ Two queens can attack each other if they are in the same row, column or diagonal. ◼ The n-queens problem is defined similarly, where in this case we have n queens and an nn chessboard for an arbitrary value of n1