The 8-Queens Problem Consider a chessboard of size 4x4.Since no two queens can be put in the same row,each queen is in a different row.Since there are four positions in each row,there are 44 possible configurations. Each possible configuration can be described by a vector with four components x=(xi,x,为，4)： For example,the vector(2,3,4,1)corresponds to a configuration
The 8-Queens Problem ◼ Consider a chessboard of size 44. Since no two queens can be put in the same row, each queen is in a different row. Since there are four positions in each row, there are 44 possible configurations. ◼ Each possible configuration can be described by a vector with four components x=(x1 , x2 , x3 , x4 ). ◼ For example, the vector (2, 3, 4, 1) corresponds to a configuration
The 8-Queens Problem Input:none; Output:A vector x[1...4]corresponding to the solution of the 4-queens problem. 1.for k-1 to 4 2.←-0； 3.end for; 4.flagk-false; 5.k-1; 6.while 1 7. while3 8. M月←-閃+1； 9. if xis a legal placement then set fag-true and exit from the two while loops; 10. else if xis partial then 1; 11. end while; 12. M月←-0； 13.k-k1; 14.end while; 15.if flag then output x 16.else output"no solution";
The 8-Queens Problem ◼ Input: none; ◼ Output: A vector x[1…4] corresponding to the solution of the 4-queens problem. 1. for k1 to 4 2. x[k]0; 3. end for; 4. flagfalse; 5. k1; 6. while k1 7. while x[k]3 8. x[k]x[k]+1; 9. if x is a legal placement then set flagtrue and exit from the two while loops; 10. else if x is partial then kk+1; 11. end while; 12. x[k]0; 13. kk-1; 14. end while; 15. if flag then output x; 16. else output “no solution”;
The General Backtracking Method The general backtracking algorithm can be described as a systematic search method that can be applied to a class of search problems whose solution consists of a vector (Xi,2,...X)satisfying some predefined constraints.Here,/is dependent on the problem formulation.In 3-Coloring and the 8-queens problems,/was fixed. ■ In some problems,/may vary from one solution to another
The General Backtracking Method ◼ The general backtracking algorithm can be described as a systematic search method that can be applied to a class of search problems whose solution consists of a vector (x1 , x2 , … xi ) satisfying some predefined constraints. Here, i is dependent on the problem formulation. In 3-Coloring and the 8-queens problems, i was fixed. ◼ In some problems, i may vary from one solution to another
The General Backtracking Method Consider a variant of the PARTITION problem defined as follows.Given a set of n integers =,2,..., and an integer y,find a subset Yof Xwhose sum is equal to y. For instance if X=10,20,30,40,50,60},and y=60, then there are three solutions of different lengths: {10,20,30},{20,40,and{60}. Actually,this problem can be formulated in another way so that the solution is a boolean vector of length n in the obvious way.The above three solutions may be expressed by the boolean vectors {1,1,1,0,0, 0},{0,1,0,1,0,0},and{0,0,0,0,0,1
The General Backtracking Method ◼ Consider a variant of the PARTITION problem defined as follows. Given a set of n integers X={x1 , x2 , …, xn} and an integer y, find a subset Y of X whose sum is equal to y. ◼ For instance if X={10, 20, 30, 40, 50, 60}, and y=60, then there are three solutions of different lengths: {10, 20, 30}, {20, 40}, and {60}. ◼ Actually, this problem can be formulated in another way so that the solution is a boolean vector of length n in the obvious way. The above three solutions may be expressed by the boolean vectors {1, 1, 1, 0, 0, 0}, {0, 1, 0, 1, 0, 0}, and {0, 0, 0, 0, 0, 1}
The General Backtracking Method In backtracking,each x,in the solution vector belongs to a finite linearly ordered set X.Thus,the backtracking algorithm considers the elements of the cartesian product Xixx...X,in lexicographic order. Initially,the algorithm starts with the empty vector.It then chooses the least element of X1 as xi.If (xi)is a partial solution,then algorithm proceeds by choosing the least element of x as x.If (i,x)is a partial solution,then the least element of X3 is included; otherwise is set to the next element in In general,suppose that the algorithm has detected the partial'solution(i,为，.…，X).It then considers the vector v=(,2,...,1).We have the following cases:
The General Backtracking Method ◼ In backtracking, each xi in the solution vector belongs to a finite linearly ordered set Xi . Thus, the backtracking algorithm considers the elements of the cartesian product X1X2…Xn in lexicographic order. ◼ Initially, the algorithm starts with the empty vector. It then chooses the least element of X1 as x1 . If (x1 ) is a partial solution, then algorithm proceeds by choosing the least element of X2 as x2 . If (x1 , x2 ) is a partial solution, then the least element of X3 is included; otherwise x2 is set to the next element in X2 . ◼ In general, suppose that the algorithm has detected the partial solution (x1 , x2 , …, xj ). It then considers the vector v=(x1 , x2 , …, xj , xj+1). We have the following cases: