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 :-
Given a maze in the form of a matrix of size n x n with all elements as 0 or 1.
0 denotes safe cell & 1 denotes dangerous cell.
A rat is placed at cell ( 0, 0 ). Print a safe path ( if exists ) which rat can take to reach last cell ( n-1, n-1 ).
Constraint :- Rat can move rightwards ( R ) or downwards ( D ).
Consider a maze of size 4 x 4 as shown below :-
0  0  1  0
1  0  0  0
1  0  1
1  0  0  0
Safe Path ( RDRDDR ) is shown below :-
0  0  1  0
1  0  0  0
1  0  1
1  0  0  0

Solution :-
The solution is a matrix in which 1s are present in the cells which consitute the path that rat may use to reach the last cell. There are two options for the rat to move ( right cell or down cell ).
1 ) Suppose the rat chooses right cell and moves there ( if the cell is safe ). At this point, it checks recursively if a path exist from that cell. If there is a path, then that cell is marked as 1 and again the rat chooses either of the two possible options and repeats the same steps.
2 ) If the path doesn't exist, then rat backtracks to the previous cell ( from where to moved to the right cell ) and chooses the down cell, moves there and again checks recursively for a possible path.
If none of these options can lead to a possible solution, then the solution doesn't exist.
See the implementation below.