0
$\begingroup$

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:

enter image description here

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:

enter image description here

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.

$\endgroup$
3
  • 3
    $\begingroup$ Could you make the images larger? I have to squint to see the dots. $\endgroup$
    – bobble
    Dec 5 '20 at 19:38
  • 1
    $\begingroup$ I count only 14 roads on a 3x3 grid. $\endgroup$ Dec 5 '20 at 20:20
  • 1
    $\begingroup$ There is an entry in OEIS related to Tak: A309514 $\endgroup$ Dec 5 '20 at 22:01
1
$\begingroup$

The possibilities, divided in path-forms/symmetry groups:

enter image description here

edit: I just realized I did not answer the actual question; adding all together for each cell gives:

enter image description here

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.