06 - Backtracking

 1. The classic textbook example of the use of backtracking is the eight queens puzzle, that asks for all arrangements of eight chess queens on a standard chessboard so that no queen attacks any other.



 2. The simplest approach of running through every possible combination of inputs can often be avoided through _________________.



  using the A* algorithm

  algorithmic heresy

 3. Backtracking involves setting up a ____________ and eliminating obvious dead-end solutions based on that __________.



  data structure - usually a stack or queue

  variable (or constant)

 4. Backtracking together with __________ helps with particularly hard problems where enumeration (considering every possibility) is not practical

  recursive iteration

  the A* algorithm



 5. A real life example of backtracking is similar to multiplechoice technique in tests where a pupil eliminates obviously wrong options to concentrate on the ones that are possible answers



 6. Backtracking can be applied only for problems which admit the concept of a "partial candidate solution" and a relatively quick test of whether it can possibly be completed to a valid solution



 7. Backtrackin would be very valuable and accurate for locating a given value in an unordered table



 8. Backtracking is often faster than brute force enumeration of all complete candidates, since it can _______________________.

  recursively call itself until the solution is found

   eliminate a large number of candidates with a single test.

  find a way to recursively eliminate a variable

  find any given path for a route with n elements in 'n' amount of time

 9. Backtracking is an important tool for solving constraint satisfaction problems, such as:

  All of the listed options are valid answers



  verbal arithmetic

 10. Backtracking is the basis of the so-called logic programming languages such as Icon, Planner and Prolog.



 11. Read the following excerpt and fill in the blanks
Conceptually, the partial candidates are represented as the nodes of a tree structure,
 the potential search tree. Each partial candidate is the parent of the candidates
 that differ from it by a single extension step; the leaves of the tree are the 
partial candidates that cannot be extended any further.

The backtracking algorithm traverses this search tree recursively, from the 

  root down, in depth-first order.

  root last, in post-order breadth-last order

  left most node first, in breadth-first order

  root first, in breadth-first order

 12. Read the following excerpt that includes an algorithm for backtracking and fill in the blanks.
If destination is reached
    print the solution matrix
   a) _____________________________________________?. 
   b) Move forward in the horizontal direction and recursively check if this 
       move leads to a solution. 
   c) If the move chosen in the above step doesn't lead to a solution
       then move down and check if this move leads to a solution. 
   d) If none of the above solutions works then unmark this cell as 0 
       (BACKTRACK) and return false.

  Mark all cells in solution matrix as 0

  Mark current cell in solution matrix as 0

  Mark all adjacent cells that have not been visited as 1

  Mark current cell in solution matrix as 1

 13. In the following excerpt (start of code) that describes the functionality of the function, fill in the blanks with the most appropriate statement for point no. 3.
1. This function solves the N Queen problem using 

2. It mainly uses solveNQUtil() to 
solve the problem. 

3. ___________________________________________________

4. Note that there may be more than one solution, this function 
prints one of the feasible solutions. 

global N 
N = 4
def printSolution(board): 
    for i in range(N): 
        for j in range(N): 
            print (board[i][j])
# A utility function to check if a queen can 
# be placed on board[row][col]. Note that this 
# function is called when "col" queens are 
# already placed in columns from 0 to col -1. 
# So we need to check only left side for 
# attacking queens 
def isSafe(board, row, col): 
    # Check this row on left side 
    for i in range(col): 
        if board[row][i] == 1: 
            return False
    # Check upper diagonal on left side 
    for i,j in zip(range(row,-1,-1), range(col,-1,-1)): 
        if board[i][j] == 1: 
            return False
    # Check lower diagonal on left side 
    for i,j in zip(range(row,N,1), range(col,-1,-1)): 
        if board[i][j] == 1: 
            return False
    return True
def solveNQUtil(board, col): 
    # base case: If all queens are placed 
    # then return true 
    if col >= N: 
        return True
    # Consider this column and try placing 
    # this queen in all rows one by one 
    for i in range(N): 
        if isSafe(board, i, col): 
            # Place this queen in board[i][col] 
            board[i][col] = 1
            # recur to place rest of the queens 
            if solveNQUtil(board, col+1) == True: 
                return True
            # If placing queen in board[i][col 
            # doesn't lead to a solution, then 
            # queen from board[i][col] 
            board[i][col] = 0
    # if the queen can not be placed in any row in 
    # this colum col  then return false 
    return False
def solveNQ(): 
    board = [ [0, 0, 0, 0], 
              [0, 0, 0, 0], 
              [0, 0, 0, 0], 
              [0, 0, 0, 0] 
    if solveNQUtil(board, 0) == False: 
        print("No solution found")
        return False
    return True

  It returns false if queens cannot be placed and also if they can be placed. This ensures consistency and is done in the form of 1s

  It returns true in all cases, and 1s are placed on the board to indicate if a queen can be placed

  It returns false if queens cannot be placed, otherwise returns true and placement of queens in the form of 1s

  It returns true of queens cannot be placed, otherwise returns false and placement of queens in the form of 0s

 14. In 1972, Edsger Dijkstra used this problem to illustrate the power of what he called structured programming. He published a highly detailed description of a ________ backtracking algorithm

  depth first

  root last

  breadth first

  root in-order

 15. Fill in the blanks for the following excerpt
Depth-first search (DFS) is an algorithm for traversing or searching tree or 
graph data structures. 

The algorithm starts at the _______(selecting some arbitrary node as the 
root node in the case of a graph) and explores as far as possible along 
each branch before _______________.

  right most leaf / backtracking

  right most node / backtracking

  left most leaf / delving depth first

  root node / backtracking