Limited-Information Maze-Solving Bot
(Still in draft/beta format. Feedback welcome.)
Based on a challenge idea I posted in chat and the ensuing conversation. Thanks to NathanMerrill and zgarb for assistance in fleshing this out.
The challenge
There exists a 50x50 maze. For clarity here, it is composed of # walls and corridors, but you can use any two distinct, consistent ASCII characters of your choice. E.g., use ! for walls and x for corridors, use 1 for walls and 0 for corridors, etc. This maze is the input to your helper program/function.
The start is always guaranteed to be somewhere on the left-most column, and the exit is always guaranteed to be somewhere on the right-most column. The maze is guaranteed to have at least one path from the start to the exit. As a result of this construction, the very top row and very bottom row are all #.
The maze-solving bot (as a program or function) that you're creating needs to find a solution to the maze (not necessarily the shortest), but is limited in that it can only "see" a 5x5 section of the maze at a time. The bot is scored by how many times it needs to request a new 5x5 section from the helper program/function.
The upper bound is obviously to simply request every possible 5x5 section, for a score of 100. The lower bound is where someone with perfect knowledge of the maze can request only those 5x5 sections containing the exact route of the shortest solution, possibly as low as 10. Your bot will be run through (1000?) different mazes, and the bot with the lowest total requests will be the winner.
The bot is placed on the left-hand side where the start is, and the first 5x5 section is provided for free. However, the bot doesn't know where, vertically, it is on the left-hand side of the maze. It could be in the top corner (as in the example), in the bottom corner, or somewhere in between.
Input/Output
The code you're writing be required to take the maze as an input (STDIN, a file to read, etc.) and call a subroutine of some sort for the solution bot. Input: 50x50 maze, output: how many requests your bot took. Rinse/repeat 1000 times.
Yes, this is a non-observable requirement to be on the honor system and ensure the two "halves" of your program (i.e., the I/O half and the solving half) talk to each other correctly and accurately. I trust the community enough to believe that this is OK.
Further rules
Your solving bot should be deterministic. That is, when presented with the same maze two or more times, it should request the same number of 5x5 sections.
Example Maze
(generated from http://www.delorie.com/game-room/mazes/genmaze.cgi )
###################################################
# # # # # # # # # #
# ######### ##### # # # # # # # # # ####### ### # #
# # # # # # # # # # # # # #
### # ####### # # ### # ### # # ############# # # #
# # # # # # # # # # # # # # # #
# ####### # ### ### ####### # ### # # # # # # ### #
# # # # # # # # # # # # # # #
##### # ################# # # # ### ### # # # # ###
# # # # # # # # # # #
### ####### ##### # ######### ##### ##### # ##### #
# # # # # # # # # # #
# ##### ### ### # ### ########### # # # # # # ### #
# # # # # # # # # # # # # # #
######### # ### # # ### # ######### # ##### # # ###
# # # # # # # # # # # # # # #
# ##### # ### ##### # ##### ##### # # # ##### # # #
# # # # # # # # # # # # # #
### # ####### # ### # # # ##### # ### # ####### # #
# # # # # # # # # # # # #
# ####### # ##### # ####### # ### # ### # ### # ###
# # # # # # # # # # # # # #
# # ### # ##### # # ####### # # ##### ####### ### #
# # # # # # # # # # # # # #
##### ########### ##### # ########### # # # # # # #
# # # # # # # # # # # # # # #
# # ### # ##### ### # # ### ### # # # ### # ##### #
# # # # # # # # # # # # # # #
##### # # ##### # ##### # # # ##### ### # ### # ###
# # # # # # # # # # # # # #
# # # # ##### # ### # ### ##### ### ##### # # ### #
# # # # # # # # # # # # #
# ####### ########### # ############### ##### # ###
# # # # # # # # # # #
##### # ### # # ####### ######### # # ### # ### # #
# # # # # # # # # # # # # #
# ##### # ### # # ######### ### ##### # ### # ### #
# # # # # # # # # # # # #
# # ####### ######### # # # ##### ### # # ##### ###
# # # # # # # # # # # # # # #
# # # # ######### # ##### ##### # # ##### ### # # #
# # # # # # # # # # # # # # #
### ##### # ### # # # ### # # ####### ### ### # # #
# # # # # # # # # # # # # # #
# ##### # # # ### # # ##### ####### ####### ##### #
# # # # # # # # # # # # #
### ######### # # # ######### # # # # ####### # # #
# # # # # # # # # # # # #
# ### # # # # # ##### # ####### ########### ##### #
# # # # # # #
###################################################
Example starting block:
#####
# ###
# #
### #
