Backtracking Leetcode Summary, Part 1

1. N-Queens
2. Permutation

N-Queens:

Problem Description: The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.
Thought Process in Short: Backtracking with DFS. We know each row has one queen, so we move from top line to the bottom line line by line, checking each column, and two diagonals.
Few Key Points:

• For all “hill” diagonals row + column = const, and for all “dale” diagonals row - column = const.
• There could be the only one queen in a row and the only one queen in a column.

Algorithms:

1. Start from the first row = 0.
2. Iterate over the columns and try to put a queen in each column.
   1. If square (row, column) is not under attack
      1. Place the queen in (row, column) square.
      2. Exclude one row, one column and two diagonals from further consideration.
      3. If all rows are filled up row == N
         • That means that we find out one more solution.
           Else
         • Proceed to place further queens backtrack(row + 1).
      4. Now backtrack : remove the queen from (row, column) square.

Codes:
Initialize log variables:

int rows[];
int hills[];
int dales[];
int n;
List<List<String>> output = new ArrayList();
int queens[];

Checking if a cell is under attack:

public boolean isNotUnderAttack(int row, int col) {
    int res = rows[col] + hills[row - col + 2 * n] + dales[row + col];
    if (res == 0) {
        return true;
    } else {
        return false;
    }
}

Method placing and removing queens:

public void placeQueen(int row, int col) {
    queens[row] = col;
    rows[col] = 1;
    hills[row - col + 2 * n] = 1;
    dales[row + col] = 1;
}

public void removeQueen(int row, int col) {
    queens[row] = 0;
    rows[col] = 0;
    hills[row - col + 2 * n] = 0;
    dales[row + col] = 0;
}

Adding a solution to existing solutions:

public void addSolution() {
    List<String> solution = new ArrayList<String>();
    for (int i = 0; i < n; ++i) {
        int col = queens[i];
        StringBuilder sb = new StringBuilder();
        for (int j = 0; j < col; ++j) {
            sb.append(".");
        }
        sb.append("Q");
        for (int j = 0; j < n - col - 1; ++j) {
            sb.append(".");
        }
        solution.add(sb.toString());
    }
    output.add(solution);
}

The actual backtracking process:

public void backtrack (int row) {
    for (int col = 0; col < n; col++) {
        if (isNotUnderAttack(row, col)) {
            placeQueen(row, col);
            if (row + 1 == n) {
                addSolution();
            } else {
                backtrack(row + 1);
            }
            removeQueen(row, col);
        }
    }
}

Main function of solution:

public List<List<String>> solveNQueens(int n) {
    this.n = n;
    rows = new int[n];
    hills = new int[4 * n - 1];
    dales = new int[2 * n - 1];
    queens = new int[n];
    
    backtrack(0);
    return output;
}

Permutation:

One of the more basic backtracking problem.
Algorithms:

1. If the first integer to consider has index n that means that the current permutation is done.
2. Iterate over the integers from index first to index n - 1.
   1. Place i-th integer first in the permutation, i.e. swap(nums[first], nums[i]).
   2. Proceed to create all permutations which starts from i-th integer : backtrack(first + 1).
   3. Now backtrack, i.e. swap(nums[first], nums[i]) back.

Code：
BFS to find solutions, then backtracking to reverse to previous states. The following is the backtracking part.

public void backtrack(int n, 
                      ArrayList<Integer> nums, 
                      List<List<Integer>> res, 
                      int first_idx) {
    if (first_idx == n) {
        res.add(new ArrayList<Integer>(nums));
    }
    for (int i = first_idx; i < n; i++) {
        # swap first and ith
        Collections.swap(nums, first_idx, i);
        backtrack(n, nums, res, first_idx+1);
        # swap back to original
        Collections.swap(nums, first_idx, i);
    }
}

Main function of solution:

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new LinkedList();
    ArrayList<Integer> nums_list = new ArrayList<Integer>();
    for (int num : nums) {
        nums_list.add(num);
    }
    int n = nums.length;
    backtrack(n, nums_list, res, 0);
    return res;
}