ISE 390 -- Programming Challenges -- Week 7 Notes This Weeks Goals: To review the principles of backtracking and exhaustive search. To introduce this week's problems on backtracking. Business: Email me a *single* attachment of a Unix shar or tar file with all your programs to date. Feel free to add a README with any explanation you want. I'd like to receive this by the first class after break. Backtracking Backtracking is a systematic way to go through all the possible configurations of a search space. In the general case, we assume our solution is a vector \$v=(a_{1}, a_{2},..., a_{n})\$ where each element \$a_i\$ is selected from a finite ordered set \$S_{i}\$, We build from a partial solution of length \$k\$ \$v = (a_{1}, a_{2},..., a_{k})\$ and try to extend it by adding another element. After extending it, we will test whether what we have so far is still possible as a partial solution. If it is still a candidate solution, great. If not, we delete \$a_{k}\$ and try the next element from \$S_k\$. In pseudocode, this is: Compute \$S_{1}\$, the set of candidate first elements of \$v\$. \$k = 1\$ While \$k > 0\$ do While \$S_{k} \neq \emptyset\$ do (*advance*) \$a_{k}\$ = an element in \$S_{k}\$ \$S_{k} \leftarrow S_{k} - {a_{k}}\$ if (\$a_{1}, a_{2},..., a_{k}\$) is solution, print! \$k = k + 1\$ compute \$S_{k}\$, the candidate \$k\$th elements given \$v\$ \$k = k - 1\$ (*backtrack*) Recursive Backtracking Recursion can be used for elegant and easy backtracking implementation: Backtrack(a, k) if a is a solution, print(a) else { \$k = k +1\$ compute \$S_{k}\$ while \$S_{k} \neq \emptyset\$ do \$a_{k}\$ = an element in \$S_{k}\$ \$S_{k}\$ = \$S_{k} - a_{k}\$ Backtrack(a, k) } Backtracking can easily be used to iterate through all subsets or permutations of a set. Backtracking ensures correctness by enumerating all possibilities. For backtracking to be efficient, we must prune the search space. Constructing all Subsets To construct all \$2^n\$ subsets, set up an array/vector of \$n\$ cells, where the value of \$a_i\$ is either true or false, signifying whether the \$i\$th item is or is not in the subset. To use the notation of the general backtrack algorithm, \$S_k = (true, false)\$, and \$v\$ is a solution whenever \$k \geq n\$. What order will this generate the subsets of \$\{1,2,3\}\$? (1) --- (1,2) --- (1,2,3)* --- (1,2,-)* --- (1,-) --- (1,-,3)* --- (1,-,-)* --- (1,-) --- (1) --- (-) --- (-,2) --- (-,2,3)* --- (-,2,-)* --- (-,-) --- (-,-,3)* --- (-,-,-)* --- (-,-) --- (-) --- () Constructing all Permutations To construct all \$n!\$ permutations, set up an array/vector of \$n\$ cells, where the value of \$a_i\$ is an integer from \$1\$ to \$n\$ which has not appeared thus far in the vector, corresponding to the \$i\$th element of the permutation. To use the notation of the general backtrack algorithm, \$S_k = (1,\ldots,n) - v\$, and \$v\$ is a solution whenever \$k \geq n\$. (1) --- (1,2) --- (1,2,3)* --- (1,2) --- (1) --- (1,3) --- (1,3,2)* --- (1,3) --- (1) --- () --- (2) --- (2,1) --- (2,1,3)* --- (2,1) --- (2) --- (2,3) --- (2,3,1)* --- (2,3) --- () (2) --- () --- (3) --- (3,1) --- (3,1,2)* --- (3,1) --- (3) --- (3,2) --- (3,2,1)* --- (3,2) --- (3) --- () The \$n\$-Queens Problem The first use of pruning to deal with the combinatorial explosion was by the king who rewarded the fellow who discovered chess! In the eight Queens, we prune whenever one queen threatens another. Assigned Problems: 148 -- Find all sets of words which give an anagram of a sentence. Efficiency is critical for such a potentially large search. 165 -- What set of k stamp denominations will maximize the range of values 1 .. n(h,k) you can reach with at most h stamps per letter? 167 -- Interesting variation of the 8-queens problem. 195 -- Construct all permutations of a multiset. Efficiency matters, so constructing all permutations, sorting them and throwing away duplicates is probably too slow. Consider permutations of aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa. 386 -- This problem is very similar to one of the war stories in "The Algorithm Design Manual". Look for an O(n^2) solution instead of O(n^4).