The board game Tak is played on a chess-like board of variable size (most commonly, 5x5 and 6x6). Players place and move pieces on the board with the goal of creating a "road", which is a string of pieces that connects two opposite ends of the board. The pieces connect to each other vertically or horizontally, but NOT diagonally.
For example, in this image, the board to the left features two valid roads, while the board to the right features no valid roads:
My question is, how many roads can each square be a part of?
Keep in mind, for the purposes of this calculation, a road is not simply a line that wins you the game, but also one that isn't a variant of another road. In other words, roads which can have pieces removed from them and remain roads don't count.
For example, in the following image, the two roads are essentially the same, you can't build the first one without building the second one, so they count as one road:
Calculating this is easy for small boards - a 2x2 board has only four possible roads, and each square has two possible roads. A 3x3 board has a total of 20 roads (edit: this is wrong), 4 roads per corner, 6 roads per edge, and 10 roads at the centre.
Beyond that, things start getting a bit trickier, but one thing to keep in mind is that, because the board is symmetrical, you don't need to calculate both horizontal and vertical roads: you can only calculate one type, and then double the number.
To be honest, I don't know how difficult or easy this problem is, but someone suggested I try my luck here, so I'm doing just that. Any help is greatly appreciated.
