In this tutorial, you will learn about Backtracking and its approach to solve constraint satisfaction problems such as crosswords and puzzles

### What is Backtracking?

Backtracking is a method for solving a constraint satisfaction problem by incrementally building candidates to the solution and abandoning a candidate as soon as it can not satisfy the constraint

Let's see a specific example

### The N-Queen puzzle

Write an algorithm to place N chess queens on an NxN chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column or diagonal

### Backtracking approach

```
```

`int[][] board = new int[8][8]`

all cells default value are 0

`isValid(board, row, col)`

ensures no two queens share the same row, column or diagonal

`enumerate(board, col)`

tries all possible candidates starting from column 0 to 7, backtracks to remove the queen from the board as soon as can not build the solution

`col == board.length`

means all queen are placed on the board

`board[i][col] = 1`

places a queen on the board at rows `i`

and column `col`

`board[i][col] = 0`

removes the queen at rows `i`

and column `col`

from the board