Problem where a rat starts from source and has to reach the destination (https://www.geeksforgeeks.org/backttracking-set-2-rat-in-a-maze/)

Backtracking : Rat in a Maze.py

#!/usr/bin/env python3


def is_safe(x, y, n, maze):
	if 0 <= x <= n-1 and 0 <= y <= n - 1 and maze[y][x] == 1:
		return True
	else:
		return False


def solve(x, y, n, maze, sol):
	if x == n-1 and y == n-1:
		sol[y][x] = 1
		return True

	if is_safe(x, y, n, maze):
		sol[y][x] = 1

		if solve(x + 1, y, n, maze, sol):
			return True

		if solve(x, y + 1, n, maze, sol):
			return True

	if 0 <= x <= n-1 and 0 <= y <= n-1:
		sol[y][x] = 0

	return False


def main():
	n = 5
	maze = [[1, 1, 1, 1, 0], [0, 1, 1, 1, 0], [0, 1, 1, 1, 0], [0, 0, 0, 1, 1]]
	sol = [[0 for x in range(n)] for y in range(n)]

	solve(0, 0, n, maze, sol)

	for row in sol:
		print(*row)


if __name__ == '__main__':
	main()