Algorithm implementation for

Solution through "backtracking"

by Tales Igor Ebert


The problem of "Military - Explore territory"!

Scenario: A military man has the important task of entering a hostile territory, exploring all the possibilities of existing paths and mapping a safe path to a final coordinate. There are obstacles that prevent him from pursuing, he needs to check if paths allow passage. He needs to deactivate the land mines that exist along that path. The main objective of the military is to bring back a map indicating all and the best safe route, marking for the other military the free passage coordinates and the location of each mine found and deactivated.

Backtracking: To solve this problem it is necessary to implement a backtracking and recursive algorithm. The proposal is similar to the implementations of the proposed labyrinth solutions with small adjustments to satisfy the initial proposal.

Rules for implementation:

Results: The recursive backtracking algorithm runs from the position x (1), y (1), all possible paths with the order (north, south, east and west), marking the position as 3 for path used, 7 for Mine and 8 for final position. Every time you find a dead-end path, the recursion will drop to the last valid path.

As a result we have:

Initial map:
1   1   1   1

1   0   0   1

1   9   0   1

1   0   4   1

1   1   1   1

Output: run java Search

Path found!

Screen Shot 2017-06-17 at 12.33.39 PM.png

Cost path: 6

Traveled path: 4Km

y(1), x(1), land: free pass, cost: 1

y(2), x(1), land: mine down, cost: 4

y(3), x(1), land: free pass, cost: 1

y(3), x(2), land: end found, cost: 0

---------------------------------------------

Path found!

Screen Shot 2017-06-17 at 12.37.41 PM.png

Cost path: 6

Traveled path: 4Km

y(1), x(1), land: free pass, cost: 1

y(2), x(1), land: mine down, cost: 4

y(2), x(2), land: free pass, cost: 1

y(3), x(2), land: end found, cost: 0

---------------------------------------------

Path found!

Screen Shot 2017-06-17 at 12.38.10 PM.png

Cost path: 3

Traveled path: 4Km

y(1), x(1), land: free pass, cost: 1

y(1), x(2), land: free pass, cost: 1

y(2), x(2), land: free pass, cost: 1

y(3), x(2), land: end found, cost: 0

---------------------------------------------

Path found!

Screen Shot 2017-06-17 at 12.38.49 PM.png

Cost path: 8

Traveled path: 6Km

y(1), x(1), land: free pass, cost: 1

y(1), x(2), land: free pass, cost: 1

y(2), x(2), land: free pass, cost: 1

y(2), x(1), land: mine down, cost: 4

y(3), x(1), land: free pass, cost: 1

y(3), x(2), land: end found, cost: 0

---------------------------------------------

We found 4 path(s)! Debug enabled!

1   1   1   1

1   3   3   1

1   9   3   1

1   0   8   1

1   1   1   1

The best path :) with only: cost 3 and travaled 4Km