# Backtracking algorithms

On two occasions I have been asked [by members of Parliament]: 'Pray, Mr. Babbage, if you put into the machine wrong figures, will the right answers come out?' I am not able rightly to apprehend the kind of confusion of ideas that could provoke such a question. Charles Babbage

## Rat in a Maze

Language Java | Level Intermediate | Category Algorithms | August 3, 2015 10:03 pm

### Algorithm Problem Description

A Maze is given matrix and Rat start from upper left and should reach to lower right. The Rat starts from source to destination and moves only forward and down direction.

Given a maze, 4 x 4 matrix. A rat has to find a path from source to destination. Rat start from left top corner and go to right bottom destination. There are few cells which are dead end which means rat can­not enter into those cells.

Write a program to rat start from source to destination?

### Output

```

Arrays for Maze1 : [[1, 0, 1, 1, 1], [1, 1, 1, 0, 1], [0, 0, 0, 1, 1], [0, 0, 0, 1, 0], [0, 0, 0, 1, 1]]
1 0 1 1 1
1 1 1 0 1
0 0 0 1 1
0 0 0 1 0
0 0 0 1 1
Arrays for Maze2 : [[1, 0, 1, 1, 1], [1, 1, 1, 0, 1], [0, 0, 0, 1, 1], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0]]
NO PATH FOUND

```