Write a simple application that demonstrate the search algorithms/strategies. You can use multiple types of search strategies in the application. Choose only 1 of the 2 possible problem options below:

OPTION 1: TRAVEL ROUTE PROBLEM Write an application that allows the user to input the current city and the destination city. The system must output the itenerary or possible sequence of cities in which the user will reach the destination from the current city. The application must cover the Mindanao area with an estimated distance in between cities. The application must be able to out the BEST possible route.

OPTION 2: 8-PUZZLE PROBLEM Given the 8-Puzzle game, write an application that allows user to shuffle the puzzle to set the initial state. The application must be able to output the BEST sequence of steps to solve the puzzle (i.e. the original goal state).