Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Introduction To Backtracking Programming

What is Back­track­ing Programming??

Recur­sion is the key in back­track­ing pro­gram­ming. As the name sug­gests we back­track to find the solu­tion. We start with one pos­si­ble move out of many avail­able moves and try to solve the prob­lem if we are able to solve the prob­lem with the selected move then we will print the solu­tion else we will back­track and select some other move and try to solve it. If none if the moves work out we will claim that there is no solu­tion for the problem.

Gen­er­al­ized Algorithm:

Pick a starting point.
while(Problem is not solved)
	For each path from the starting point.
		check if selected path is safe, if yes select it
                and make recursive call to rest of the problem
		If recursive calls returns true, then return true.
		else undo the current move and return false.
	End For
	If none of the move works out, return false, NO SOLUTON.

Prob­lems on Backtracking

 

 

You may also like...