1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

"Programmable" Robot Maze: Possible Paths?

  1. Jan 18, 2015 #1
    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
     
  2. jcsd
  3. Jan 18, 2015 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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).
     
  4. Jan 18, 2015 #3
    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.
     
  5. Jan 18, 2015 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    "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.
     
  6. Jan 18, 2015 #5
    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?
     
  7. Jan 19, 2015 #6

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: "Programmable" Robot Maze: Possible Paths?
  1. All possible paths (Replies: 3)

  2. Is This possible? (Replies: 21)

  3. Robot ! (Replies: 3)

  4. Is this possible! (Replies: 4)

Loading...