How would I go about making the following program? I need help making a plan for the logic, as I can program it. I just don't know how to find solutions that can also go back on previously visited spaces, as most algorithms don't allow that.
I have tried implementing A* algorithm and Dijkstra's algorithm, however like I said, I'm not sure how to modify these to allow it to go back on previously visited spaces.
Write a program that navigates a 4 by 4 maze by hopping from one spot to another.
- Can not land on spaces that are "|", "—", "I", "=", or ".".
- Can jump over "|" and "—".
- Can not jump over "I" or "=".
- Can not jump diagonally.
- Can go back on spaces that have already been landed on.
- Can only jump over one space at a time.
- Must start on space "S".
- Must end on space "E".
- Must land on all spaces that are "X" before landing on space "E".
- Ends when space "E" is landed on.
- Must return the shortest possible path.
Output the coordinates of each space that the program lands on in the order that they are landed on.
maze = [ ["O","|","E","I","X","I","O"], ["—",".","=",".","—",".","—"], ["O","|","O","|","O","|","O"], ["=",".","—",".","=",".","—"], ["X","|","O","I","O","|","X"], ["—",".","=",".","—",".","="], ["O","|","S","|","O","|","O"], ]
Here's what the 2D array above looks like:
