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 _________________.
3. Backtracking involves setting up a ____________ and eliminating obvious dead-end solutions based on that __________.
4. Backtracking together with __________ helps with particularly hard problems where enumeration (considering
every possibility) is not practical
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 _______________________.
9. Backtracking is an important tool for solving constraint satisfaction problems, such as:
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
12. Read the following excerpt that includes an algorithm for backtracking and fill in the blanks.
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
backtracking.
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])
print
# 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
printSolution(board)
return True
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
15. Fill in the blanks for the following excerpt
