The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. ― Donald E. Knuth

# Algorithms

## Backtracking

Problem :-
Solve the N - Queens problem.
N - Queen is the problem of placing N queens on an N x N chessboard so that no two queens
can attack each other. For e.g, on a 4 x 4 chessboard, one of the possible solution to place 4 queens on the chessboard is shown below :
0  0  1  0
1  0  0  0
0  0  0  1
1  0  0
1s are placed in the cells where queens can be safely placed.

Solution :-
The solution requires that no two queens should share the same row, column or diagonal.
We will start placing queens one by one in different columns starting from the leftmost column and check for clashes with the previously placed queens.
Suppose we are at jth column. This means j - 1 queens are already placed. Now in column j , there are n possible rows in which a queen can be placed.
1 ) We will select one of the rows and check recursively if placing the queen in this row leads to a solution. If a solution exists, then we will proceed to the next column and repeat the same steps.
2 ) If the solution doesn't exist, then we backtrack and select some other row and check if placing the queen in that row leads to a solution. We will keep trying till we find a valid row.
When all the columns are visited and all queens are placed, we have found a solution.
See the implementation below.