Backtracking with Dynamic Programming

Approach 2 for Palindrome Partitioning.

Backtracking with dynamic programming combines the exhaustive search of backtracking with dynamic programming’s memoization to avoid repeated work. This improves performance for many backtracking problems.

Java example for N Queens:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int[][] board = new int[N][N];
Boolean[][] allowed = new Boolean[N][N]; 

int solveNQueens(int row) {
  if (row == N) {
    return 1; // Found solution
  }

  int solutions = 0;
  for (int col = 0; col < N; col++) {
    if (allowed[row][col]) {
      placeQueen(row, col);
      solutions += solveNQueens(row+1); 
      removeQueen(row, col);
    }
  }
  return solutions; 
}

void placeQueen(int row, int col) {
  // Update allowed matrix
  allowed[row][col] = false;
  // Update allowed in other rows/cols/diags  
}

C++ example for Sudoku:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
int solveSudoku(int board[9][9], int row, int col) {

  if (row == 9) return 1; // Found solution
  
  if (col == 9) return solveSudoku(board, row+1, 0);

  if (board[row][col] != 0) {
    return solveSudoku(board, row, col+1); 
  }

  int solutions = 0;
  for (int num = 1; num<=9; num++) {
    if (isAllowed(board, row, col, num)) {
      placeNumber(board, row, col, num);
      solutions += solveSudoku(board, row, col + 1);
      clearNumber(board, row, col); 
    }
  }
  return solutions;
}

Python example for Magic Squares:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def solveMagicSquare(square, i, j):
  
  if i == N: 
    return 1
  
  if j == N:
    return solveMagicSquare(square, i+1, 0)  
  
  solutions = 0
  for k in range(1, N+1):
    if isAllowed(square, i, j, k):
      placeNumber(square, i, j, k)
      solutions += solveMagicSquare(square, i, j+1)
      removeNumber(square, i, j)
      
  return solutions

Dynamic programming stores intermediate results in a table, avoiding recalculation. Improves performance of backtracking exponentially for many problems.