Unit 6: Backtracking - Subjective Questions

Backtracking is a systematic problem-solving technique that constructs a solution incrementally and abandons a partial solution as soon as it determines that the partial solution cannot lead to a valid complete solution.

The general method is:

• Represent a solution as a sequence .
• Select a possible value for the next decision variable .
• Test whether the resulting partial solution is promising.
• If it is promising, continue to the next level.
• If it is not promising, discard that choice and try another value.
• When no value remains at a level, return to the preceding level. This action is called backtracking.
• Report the solution when all required decisions have been made successfully.

Backtracking is commonly modeled using a state-space tree, in which each node represents a partial solution and each edge represents a decision.

A state-space tree is a rooted tree representing all possible states that may be examined while solving a problem.

Its main components are:

• Root node: Represents the initial state with no decisions made.
• Internal node: Represents a partial solution.
• Edge: Represents a choice made to extend a partial solution.
• Level: Corresponds to the number of decisions already made.
• Leaf node: Represents either a complete solution or a dead end.
• Solution node: Represents a state satisfying all problem constraints.
• Non-promising node: Represents a partial solution that cannot produce a valid complete solution.

Backtracking performs a depth-first traversal of this tree. It prunes non-promising nodes rather than exploring all their descendants, thereby reducing unnecessary computation.

These concepts control the search performed by backtracking:

• A constraint is a condition that every valid solution must satisfy. Constraints may apply to individual choices or combinations of choices.
• A promising function examines a partial solution and determines whether it can still be extended into a valid complete solution.
• Pruning is the process of preventing the expansion of a node that the promising function identifies as non-promising.

For example, in the -queens problem, placing two queens in the same column or diagonal violates a constraint. The corresponding node is declared non-promising and its descendants are not generated.

A correct promising function must not reject any partial state that can lead to a valid solution. Effective pruning can greatly reduce the portion of the state-space tree that must be explored.

A general recursive backtracking algorithm can be written as follows:

Algorithm:

1. If the current partial solution is complete, report it.
2. Otherwise, generate each candidate for the next decision.
3. Add the candidate to the partial solution.
4. If the new state is promising, invoke the algorithm recursively.
5. Remove the candidate before trying the next choice.

A generic representation is:

BACKTRACK(k):
    if solution is complete:
        report solution
    else:
        for each candidate x at level k:
            choose x
            if promising(k):
                BACKTRACK(k + 1)
            undo choice x

The recursive call performs a depth-first exploration. The undo operation restores the previous state, allowing alternative candidates to be considered. The worst-case running time is often exponential because the algorithm may explore a large part of the state-space tree.

Comparison:

• Brute-force search generates and tests every possible complete candidate.
• Backtracking constructs candidates incrementally and rejects invalid partial candidates early.
• Brute force generally performs little or no pruning, whereas backtracking uses constraints and a promising function.
• Both methods can have the same exponential worst-case complexity, but backtracking is usually much faster in practice when pruning is effective.

If the search tree has branching factor and maximum depth , the worst-case number of examined nodes is

With a depth-first recursive implementation, the active search path has at most nodes. Thus, excluding stored output, the auxiliary space is typically plus the space needed to maintain candidates and problem-specific state.

Performance depends strongly on the order of choices and the effectiveness of the promising function.

The -queens problem asks us to place eight queens on an chessboard so that no two queens attack each other.

Place exactly one queen in each row and represent a placement by

where is the column occupied by the queen in row .

For every pair of rows and , where , the constraints are:

• Different columns: .
• Different diagonals: .

A state at level specifies the columns of queens in the first rows. A candidate column for row is promising only if it conflicts with none of the previously placed queens. The algorithm backtracks whenever no safe column is available for the current row.

Let denote the column selected for the queen in row . When placing the queen in row , it must be checked against every previously placed queen in row , where .

Two queens conflict when:

• They occupy the same column: .
• They occupy the same diagonal: .

Therefore, the placement at row is promising exactly when

for every satisfying .

A direct promising test examines at most earlier queens, so one test takes time. Alternatively, occupied columns and diagonals can be stored in sets or Boolean arrays, allowing a candidate to be checked in time.

Use an array , where stores the column of the queen placed in row .

Procedure:

1. Begin with row .
2. Try every column from to in row .
3. Set .
4. Check whether this queen conflicts with any queen in rows through .
5. If the placement is safe and , output the arrangement.
6. If it is safe and , recursively place a queen in row .
7. If no column is safe, return to row and try its next candidate.

The row-by-row formulation automatically prevents row conflicts. The promising test handles column and diagonal conflicts. The method can be stopped after finding one solution or continued to enumerate every solution.

Suppose queens have been safely placed in the first rows. The algorithm then examines columns in row .

• If a candidate column is occupied by an earlier queen, it is rejected.
• If the candidate lies on an occupied diagonal, it is also rejected.
• If a safe candidate is found, the queen is placed and the search moves to row .
• If every column in row is rejected, the partial placement is a dead end.
• The algorithm removes the queen from row , returns to that row, and tries its next unexamined safe column.
• If row also has no remaining candidate, it moves back again.

Thus, backtracking reverses the most recent choice that still has alternatives. Entire subtrees are skipped because every descendant of a conflicting partial placement would contain the same conflict.

With one queen assigned to each row, each row initially appears to have column choices. A loose upper bound on the search is therefore . Since no two queens may occupy the same column, the search can instead be viewed as examining permutations of columns, giving a more informative upper bound of complete arrangements.

Backtracking performs better than exhaustive permutation testing because it rejects a placement as soon as a column or diagonal conflict appears. Its actual running time depends on:

• The order in which columns are tried.
• The number of solutions requested.
• The efficiency of conflict detection.
• Additional techniques such as symmetry reduction.

The placement array and recursive call stack require auxiliary space. Boolean arrays for columns and the two diagonal directions also require space.

In graph coloring, colors are assigned to vertices so that adjacent vertices receive different colors.

For an undirected graph , the -coloring problem asks whether the vertices can be colored using at most colors such that

In a backtracking formulation:

• Vertices are considered one at a time.
• At level , a color is assigned to vertex .
• The candidates are the colors .
• A candidate is promising if it differs from the colors of every already-colored neighbor.
• If no color can be assigned, the algorithm returns to the preceding vertex and changes its color.

The algorithm succeeds if every vertex receives a valid color.

Let be the color assigned to vertex . After assigning a candidate color to , the state is promising if no previously colored adjacent vertex has the same color.

Using an adjacency matrix , the condition is

for every .

The promising function therefore:

• Examines each previously colored vertex .
• Checks whether is adjacent to .
• Rejects the candidate if adjacency exists and .
• Accepts the candidate if no such conflict is found.

With an adjacency matrix, one check takes time. With adjacency lists, only already-colored neighbors need to be inspected, which can be more efficient for sparse graphs.

Let the graph have vertices , and let represent the color of .

Algorithm:

1. Start with vertex .
2. For the current vertex , try each color from through .
3. Check the color against all already-colored neighbors of .
4. If no conflict occurs, assign the color and recursively process .
5. If all vertices have been colored, return success.
6. If no color works for , erase its assignment and return to .
7. Return failure if every possibility for the first vertex is exhausted.

The basic search has at most complete assignments, so its worst-case time is exponential. Pruning eliminates assignments containing an edge whose endpoints already have the same color.

• The decision problem asks whether a graph can be properly colored with at most a specified number of colors. Its answer is either yes or no.
• The optimization problem asks for a proper coloring that uses the minimum possible number of colors.
• The chromatic number, written , is the minimum number of colors required for a proper coloring of graph .

A backtracking decision algorithm for -coloring can help compute by testing different values of . For example, one may test increasing values until a feasible coloring is found. Alternatively, known lower and upper bounds can restrict the tested range.

The constraint in all cases is that adjacent vertices must have distinct colors; the difference lies in whether is fixed or must be minimized.

The correctness of graph-coloring backtracking does not depend on vertex order, but its practical running time can change greatly.

Useful strategies include:

• Highest-degree first: Color vertices with many neighbors early, exposing conflicts sooner.
• Most constrained first: Select the uncolored vertex having the fewest available colors.
• Saturation ordering: Prefer the vertex adjacent to the greatest number of distinctly colored vertices.
• Least-constraining color: Try the color that removes the fewest choices from neighboring vertices.

For dense graphs, an adjacency matrix provides constant-time adjacency queries but consumes space. For sparse graphs, adjacency lists use space and allow the promising function to examine only neighbors. Good ordering and efficient conflict tracking reduce the number and cost of explored states, although the worst-case complexity remains exponential.

A Hamiltonian cycle in a graph is a simple cycle that visits every vertex exactly once and returns to its starting vertex.

A Hamiltonian path visits every vertex exactly once but does not have to return to the starting vertex.

An Euler cycle traverses every edge exactly once and returns to its starting vertex. Its focus is therefore on edges rather than vertices.

Key differences are:

• Hamiltonian problems impose conditions on visits to vertices.
• Euler problems impose conditions on traversals of edges.
• A Hamiltonian cycle may leave some graph edges unused.
• An Euler cycle may revisit vertices while using every edge exactly once.

A connected graph has an Euler cycle precisely when every vertex has even degree, but no comparably simple general characterization is known for Hamiltonian cycles.

Fix a starting vertex and represent a possible Hamiltonian cycle as

At level , the state-space tree contains partial paths . A candidate vertex is promising when:

• It has not appeared among .
• It is adjacent to the preceding vertex .
• If , it is also adjacent to the starting vertex , so the path can close into a cycle.

Each child appends one unused vertex to the partial path. A node is pruned if it repeats a vertex, uses a nonexistent edge, or cannot close the final cycle. Fixing the first vertex removes equivalent cycles caused only by selecting a different starting point.

Let store the vertex sequence, and fix to an arbitrary starting vertex.

Recursive method:

1. At position , consider each vertex not already in .
2. Check whether the candidate is adjacent to .
3. If it is valid, assign it to .
4. If , recursively fill position .
5. If , also test whether is adjacent to .
6. If the closing edge exists, report the Hamiltonian cycle.
7. Otherwise, remove the candidate and try another vertex.
8. Return failure when all candidates have been exhausted.

The algorithm maintains a simple path throughout the search. It may stop after one cycle or continue to enumerate all Hamiltonian cycles.

After fixing the starting vertex, the algorithm may need to examine permutations of the remaining vertices. Consequently, a standard worst-case time bound is

At each state, adjacency and repetition checks also incur costs. An adjacency matrix permits an edge test in time, while a Boolean visited array permits an unused-vertex test in time.

The path array, visited array, and recursion stack each require space, so the auxiliary space is when output storage and graph representation are excluded.

Backtracking can be substantially faster than complete permutation testing because it immediately rejects a partial path when the next required edge does not exist. Nevertheless, dense or specially structured graphs can force exploration of a large fraction of the permutation tree.

All three problems build a solution incrementally, apply a promising test, and explore the resulting state-space tree depth first.

Differences in decisions and constraints:

• -queens: Level selects a column for the queen in row . The constraints prohibit equal columns and equal diagonals.
• Graph coloring: Level selects a color for vertex . Adjacent vertices must have different colors.
• Hamiltonian cycle: Level selects the next vertex in a path. Vertices cannot repeat, consecutive vertices must be adjacent, and the last vertex must connect to the first.

Their branching factors also differ. The -queens problem initially has up to choices per row, graph coloring has up to colors per vertex, and Hamiltonian-cycle search chooses among unused vertices. In every case, stronger pruning and good candidate ordering improve practical performance without removing the exponential worst case.