"Programmable" Robot Maze: Possible Paths?

  • Thread starter mishima
  • Start date
  • #1
532
31

Main Question or Discussion Point

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.

quoridorBoard.jpg


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
 

Answers and Replies

  • #2
34,038
9,879
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).
 
  • #3
532
31
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.
 
  • #4
34,038
9,879
"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.
 
  • #5
532
31
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?
 
  • #6
34,038
9,879
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).
 

Related Threads for: "Programmable" Robot Maze: Possible Paths?

  • Last Post
Replies
3
Views
3K
Replies
1
Views
3K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
15
Views
4K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
3
Views
1K
Replies
1
Views
1K
Top