# Backtracking

`A backtracking algorithm tries to build a solution to a computational problem incrementally.Whenever the algorithm needs to decide between multiple alternatives to the next component of the solution, it simply tries all possible options recursively.`

Talk is cheap, let’s see the problems.

## N-Queens Problem

The problem is to place n queens on an n × n chessboard, so that no two queens can attack each other. For readers not familiar with the rules of chess, this means that no two queens are in the same row, column, or diagonal

We have unattacked cells where we need queues. and every time we place one queue at , the number of unattacked cells reduced, so continue doing this, as long as following conditions hold:

- The number of unattacked cells is not .
- The number of queens to be placed is not .

So our terminal conditions are that when the unattacked cells comes zero or the queues all placed; and for the queue, if all placed, then it’s over, we found the solution; while the unattacked cells comes zero, means we need to backtrack,i.e. remove the last placed queen from its current cell, and place it at some other cell. We do this recursively.

### The pseudocode from `hackerearth`

```
is_attacked( x, y, board[][], N)
//checking for row and column
if any cell in xth row is 1
return true
if any cell in yth column is 1
return true
//checking for diagonals
if any cell (p, q) having p+q = x+y is 1
return true
if any cell (p, q) having p-q = x-y is 1
return true
return false
N-Queens( board[][], N )
if N is 0 //All queens have been placed
return true
for i = 1 to N {
for j = 1 to N {
if is_attacked(i, j, board, N) is true
skip it and move to next cell
board[i][j] = 1 //Place current queen at cell (i,j)
if N-Queens( board, N-1) is true // Solve subproblem
return true // if solution is found return true
board[i][j] = 0 /* if solution is not found undo whatever changes
were made i.e., remove current queen from (i,j)*/
}
}
return false
```

And the pic is clear:

At the end it reaches the following solution:

Generally, when we dealing with backtracking problem, the key is `Recursion`

and difficulty is to **find the recursive rule and find the terminal conditions**, and one should notice is that we should make a sign to show which cell we have placed `board[i][j] = 1`

when one recurrence starts, we need remember to change this sign to origin cell `board[i][j] = 0`

when the recurrence ends. When writing program, we also need to think about how to compute if the queues are in a safe place. And the follow code is show this magic.

### Code from Introduction to algorithm competition

```
void search(int cur) {
if(cur == n) tot++;
else for(int i = 0; i < n; i++) {
if(!vis[0][i] && !vis[1][cur+i] && !vis[2][cur-i+n]) {
//use a 2d array to judge if safe
C[cur] = i; //if dont need to print, C is useless
vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 1; //add a sign means not safe
search(cur+1);
vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 0; //Keep in mind! change it back
}
}
}
```

## Leetcode Problem

```
Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
```

Example:

```
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.
```

### Thinking

Recursively each item in the 2d board, and call backtracking for each item. In this problem, we use an `index`

to represent the step we are in, so when `index`

equal to the `word.size()`

, we got the solution, and this is our one terminal condition; for each loop we use `(i, j)`

to represent the item we are checking, so when , we should backtracking, and this is our second terminal condition.

### Cpp code

```
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int row = board.size();
int col = board[0].size();
for(int i = 0; i < row; i++)
for(int j = 0; j< col; j++)
if(back(board, word, i, j, 0))
return true;
return false;
}
bool back(vector<vector<char>>& board, string& word, int i, int j, int index) {
if(index == word.size())
return true;
if(i < 0 || j < 0 || i > board.size()-1 || j > board[0].size()-1) // boundary of board
return false;
if(board[i][j] != word[index])
return false;
board[i][j] = '*';
bool furtherSearch = back(board, word, i+1, j, index+1) ||
back(board, word, i-1, j, index+1) ||
back(board, word, i, j-1, index+1) ||
back(board, word, i, j+1, index+1);
board[i][j] = word[index];
return furtherSearch;
}
};
```

## References

Some essay, blog or question referred above.

This work is licensed under a Creative Commons Attribution 4.0 International License.