# Backtracking

###### tags: `Backtracking`

>Prerequisite: None

## Content
[ToC]

## Generate All Subset

### Problem Statement
Given an array A[], generate all possible subsets of A.

Example:
    Input: A[] = {1,2,3};
    Output: {},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}

### Algorithm

Note that we will need to print out the current subset we generate; then we can decide if the next element we choose is available or not. Use a bitmap[] to record the previous choice.

When we decide to change the current bitmap[i] to become one, we can proceed to generate the subset with A[i+1]. After generating the subset with element A[i], we have to change bitmap[i] into zero. Therefore, we can get another subset without A[i].

### C++ Code

#include <iostream>
using namespace std;

void allSubset(int A[], int bitmap[], int n, int size){
    for(int i = 0; i < size; i++){
        if(bitmap[i] == 1){
            cout << A[i] << " ";
        }
    }
    cout << endl;
    for(int i = n; i < size; i++){
        bitmap[i] = 1;
        allSubset(A, bitmap, i+1, size);
        bitmap[i] = 0;
    }
}
int main(){
    int A[] = {1,2,3,4,5};
    int bitmap[] = {0,0,0,0,0};
    allSubset(A, bitmap, 0, 5);
    return 0;
}

## N Queens

### Problem statement

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other. Two queens attack each other when two queens are in the same row; in the same column; in the same diagonal line.

Given an integer n, return the number of 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.

### Algorithm
When we are putting one queen on the chessboard, we will need to check if the position is valid or not. We will see all the positions on row i. We will only put a queen in one row. Therefore, once we find a valid position, we can next move to i+1 row to find another valid position.

The method to check the validity will be that we can go through the whole chessboard and see whether any queen attacks the current queen.

With the method of backtracking, we will put the queen in the current valid position and go through the next rows. Once we finish going through the following rows, we will remove the current queen and see whether there is another valid position for the queen.

### C++ Code

#include <iostream>
#include <vector>
using namespace std;

void display(int rows, vector< vector<int> > Q){
    for(int i = 0; i < rows; i++){
        for(int j = 0; j < rows; j++){
            cout << Q[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

bool valid(int i, int j, int rows, vector< vector<int> > Q){
    for(int row = 0; row < rows; row++){
        for(int col = 0; col < rows; col++){
            if(i >= rows || j >= rows) return 0;
            else if((col == j && Q[row][col] == 1)) return 0;
            else if(((row-col) == (i-j)) && (Q[row][col] == 1)) return 0;
            else if(((row+col) == (i+j)) && (Q[row][col] == 1)) return 0;
        }
    }
    return 1;
}

int c = 0;
void dfs(int i, int rows, vector< vector<int> > Q){
    if(i == rows){
        display(rows, Q);
        c++;
    }
    else{
        for(int col = 0; col < rows; col++){
            if(valid(i, col, rows, Q)){
                Q[i][col] = 1;
                dfs(i+1, rows, Q);
                Q[i][col] = 0;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    int rows;
    cin >> rows;
    vector< vector<int> > Q(rows, vector<int>(rows, 0));
    dfs(0, rows, Q);
    cout << c << endl;
    return 0;
}

### N queens M rocks

The n-queens puzzle is the problem of placing n queens and m rocks on an (n+m) x (n+m) chessboard such that no queens or rocks attack each other. The valid position for queens is mentioned as follows. After putting a rock on the chessboard, we cannot put another queen or rock on the same row and same column of the current rock. As the code below:

#include <iostream>
#include <stdio.h>
using namespace std;
char board[15][15];

void display(int rows){
    for(int i = 0; i < rows; i++){
        for(int j = 0; j < rows; j++){
            cout << board[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

int valid_q(int row, int col, int size){
    for(int i = 1; i <= row; i++){
        if(col-i >= 0 && (board[row-i][col-i] == 'Q' || board[row-i][col-i] == 'R')) return 0;
        if(col+i < size && (board[row-i][col+i] == 'R' || board[row-i][col+i] == 'Q')) return 0;
        if(board[row-i][col] == 'R' || board[row-i][col] == 'Q') return 0;
    }
    return 1;
}

int valid_r(int row, int col, int size){
    for(int i = 1; i <= row; i++){
        if(col-i >= 0 && board[row-i][col-i] == 'Q') return 0;
        if(col+i < size &&  board[row-i][col+i] == 'Q') return 0;
        if(board[row-i][col] == 'Q' || board[row-i][col] == 'R') return 0;
    }
    return 1;
}

//n queens
//m rocks
int c = 0;
void dfs(int row, int queen, int rock, int size){
    if(row == size){
        c++;
        //display(size);
        return;
    }
    else{
        for(int j = 0; j < size; j++){
            if(queen > 0 && valid_q(row, j, size)){
                board[row][j] = 'Q';
                dfs(row+1, queen-1, rock, size);
                board[row][j] = '0';
            }
            if(rock > 0 && valid_r(row, j, size)){
                board[row][j] = 'R';
                dfs(row+1, queen, rock-1, size);
                board[row][j] = '0';
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n+m; i++){
        for(int j = 0; j < n+m; j++){
            board[i][j] = '0';
        }
    }
    dfs(0, n, m, n+m);
    cout << c << endl;
    return 0;
}