Given the 2D grid shown below, where blue tiles can be visited and island tiles cannot.
Given that we do not know the starting position of a player on this grid.
Given that the player can move 1 step in any cardinal direction every turn.
Given that the player cannot visit tiles he has already visited.
Given that we are told every turn in which direction the player has moved.
What would be a computationally efficient algorithm to pinpoint the player's location in the least amount of turns?
One way that comes to mind that would give me good results but would probably be computationally intensive is to try to apply the player's path to every possible starting position. If we can traverse the path without hitting an island or going off the map, then the end tile is a valid possible position for the player. At first we would have a lot of possible positions for the player but eventually, after several turns, we'd end up with only one possible position.
I don't very much like that approach as it seems computationally heavy.
Instead, I've implemented a simple solution using a bounding box. At the beginning of the game, the player could be anywhere. But as soon as he moves, we can narrow the bounding box. For instance, if the player's first move is north, we now know that he can't be in the bottom row of the map. All that is needed is to keep track of the top left and bottom right coordinates of that box and update them every turn according to the enemy's movement until the box is eventually narrowed down to the player position.
I like this solution because it is simple and computationally light. The problem is that it doesn't take into account the islands and the players' previously visited cells. Therefore, only when the bounding box hits the grids' limits can we narrow it down. If the player starts in the middle of the map and tends to stay there, it can take a long time before narrowing down his position.
Is there a way to refine my solution (bounding box) in a way that would at least account for the islands and at best for the player's visited tiles as well? If not, what other algorithm could I use?
