Backtracking

DFSbtQ( X[1..i], row )   if row = 4 then print(X)   else       for column ∈ {1, 2, 3, 4 } do           if not conflicted(X, row+1, column)              X[row+1] ← column              DFSbtQ( X, row+1 )    return When conflicted next column is examined. When last column tried, backtrack. When all rows solved, print solution. conflicted( X, row, column ) --  pre: X[1..i] first i components of a solution --  post: True if X[i+1] conflicts at (row, column) with X[1..i]              False otherwise

Question

• What is the next partial solution after 8?

  	1	2	3	4
  1			Q
  2
  3
  4

• Continue to find the next solution.

  1 2 3 4 1     Q   2         3         4

  1 2 3 4 1     Q   2 Q       3         4

  1 2 3 4 1     Q   2 Q       3       Q 4

  1 2 3 4 1     Q   2 Q       3       Q 4   Q

Generic Backtracking Algorithm

DFSbt( X[1..i] ) --  pre: X[1..i] specifies first i components of a solution --  post: Solution X[1..i] --           Si+1 is solution i+1 if X[1..i] is a solution then print X[1..i] else    for each x ∈ Si+1 do       if x is consistent with X[1..i] and valid option for problem constraints then            X[i+1] ← x            DFSbt( X[1..i+1] )

• Give a backtracking algorithm to make change given:

  1. amount to change = 11

  2. coins to use for making change = {5, 2}

• Hint:

  change( amount,  X[1..i] )

      -- pre: amount ≥ 0 remaining to change, X the coins used and i ≥ 0 the number of coins so far
      -- post: prints coins used to make change

   Using the generic algorithm  for backtracking:

change( 11, [], 0) prints 4 coins using [5, 2, 2, 2]

change( amount,  X[1..i] )     -- pre: amount ≥ 0 remaining to change, X the coins used and i ≥ 0 the number of coins so far     -- post: prints coins used to make change     if amount = 0 then print X[1..i]     else        for coin ∈ { 5, 2 } do           if remainder ← X[i] - coin ≥ 0 then              X[i + 1] = coin              change( remainder, X[i+1] )