"Programmable" Robot Maze: Possible Paths?

[mishima]

There is a board game called "Quoridor" (http://en.wikipedia.org/wiki/Quoridor) where you build walls in such a way that your enemy is impeded and you are helped. I would like to build some similar pieces out of wood large enough to allow my students' robots to have a "changeable" maze they could test out pathfinding and such with.

The wall pieces can only touch 2 squares (not 3). For my purposes, there can be any number of walls allowed. (in the game, each player gets 10 walls and can either move or place a wall each turn)

My math question is how many possible paths are there:
a: That lead from one side to the other with the original 81 square board.
b: On an easier to physically construct 3x6 board.
c: How to find max paths for an m x n board

 

[mfb]

Without further limitations, there are always 0 or an infinite number of paths. You can keep moving in circles n times, for every integer n, and then go to the other side (if possible, otherwise there is no path).

 

[mishima]

I understand what you are saying. I suppose I was thinking of the path from the perspective of the environment, instead of the moving object. Let's discard loops that do not add to the progress of the object toward its goal. The robots do tend to loop multiple times in reality, but that isn't important.

 

[mfb]

"A field cannot be used twice"? In general, that will give a complicated problem, and something like backtracking is probably the best way to find all solutions.

 

[mishima]

Are there other constraints possible that might make it a more casual (scratch paper) problem? Or are there computer programs that facilitate the backtracking process?

 

[mfb]

There are computer programs, sure.
To find some number with pen&paper, you could add the requirement that moves are only allowed in specific directions (like "down" and "left"), or find some clever ways to reduce the full problem to smaller sub-problems depending on the wall positions (if there are enough walls).