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
  2
  3
  4

• Continue to find the next solution.

  1 2 3 4 1         2         3         4

  1 2 3 4 1         2         3         4

  1 2 3 4 1         2         3         4

  1 2 3 4 1         2         3         4

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[1..i] the coins used, and i ≥ 0 the number of coins so far.
      -- post: prints coins used to make change