stacks if applied to the maze problemthe brute-force method would require we start at the beginning and follow path until we either find the exit or encounter blocked passage if we hit wall instead of the exitwe would start over from the beginning and try different path but this would be time consuming since we would likely follow part of the same path from the beginning to some point before we encountered the blocked passage instead of going all the way back to the beginningwe could back up along the path we originally took until we find passage going in different direction we could then follow the new passage in hopes of finding the exit if we again encounter blocked passage before the exitwe can back up one or more steps and try different passage this process of eliminating possible contenders from the solution and partially backing up to try others is known as backtracking and is refinement of the basic brute-force method there is broad class of algorithms that employ this technique and are known as backtracking algorithms all of these algorithms attempt to find solution to problem by extending partial solution one step at time if "dead endis encountered during this processthe algorithm backtracks one or more steps in an attempt to try other possibilities without having to start over from the beginning designing solution the solution to the maze problem is classic example of backtracking in this sectionwe explore the technique and design solution to the maze problem problem details given maze with indicated starting and exit positionsthe objectives are ( determine if there is path from the starting position to the exitand ( specify the path with no circles or loopbacks in designing an algorithm to solve mazeit will be easier if we think of the maze as collection of equal-sized cells laid out in rows and columnsas illustrated in figure the cells will either be filled representing walls of the maze or empty to represent open spaces in additionone cell will be indicated as the starting position and another as the exit figure sample maze from figure divided into equal-sized cells