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).