Ignoring pawns there are 1,375,968,129,062,134,174,771 possible ways to place 0 to 20 walls on the Quoridor board, as answered here.

Ignoring walls there are 81 * 81 = 6410 ways to place the two pawns on the board.

Multiplying these numbers gives us all possible legal and illegal board states. How do I separate out the legal from the illegal board states?

A board state is illegal if either pawn does not have at least one path to its goal.

  • $\begingroup$ My idea for solving this would be to consider each of the 1,375,968,129,062,134,174,771 boards 6410 times. I would follow these steps: Start with one pawn. Look for a legal path to its goal. If no path mark the board as illegal and move to the next pawn position. If a path does exist switch to the other pawn Perform the same check for a possible path to the goal. If the second pawn has at least one path, mark the board as legal. If not, mark it illegal and move to the next pawn position. Move on to the next pawn position. After checking all 6410 positions move onto the next board. $\endgroup$ – lameK Nov 12 '14 at 17:42
  • $\begingroup$ Assuming each check takes 1 ns (a single processor cycle), that will take 27 billion years. $\endgroup$ – Nathan Merrill Nov 12 '14 at 22:28
  • $\begingroup$ Sketch of an approach: augment the previous approach by a set of variables which track whether the cells above and below a row of intersections are reachable from the top row and from the bottom row, and another which tracks totals. This will increase the number of nodes in the graph by a factor of on the order of tens of thousands, but the number of edges won't increase by nearly such a big factor, so it should still be a feasible calculation. $\endgroup$ – Peter Taylor Nov 12 '14 at 23:18
  • $\begingroup$ @MrTi Hi MrTi. Thanks. I tried to figure out whether this problem was too big to calculate. Did you get 27 billion with this calculation? (1,375,968,129,062,134,174,771 * 6410)/ 3.15569e16 =279493730.604 I'm guessing each check would take longer than 1ns, but when it comes to how to check I'm not sure of a good approach. $\endgroup$ – lameK Nov 13 '14 at 0:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.