0

I have a $N\times N$ chessboard, and I need to compute all the paths from a corner to the opposite, walking once on each tile, and only walking from a tile to one of the nearest tiles (i.e., no jumps, no diagonal moving).

I was thinking to solve it by recursion, like on a $1\times i$ chessboard I have one path for any $i$, and for a $2\times i$ I have the same number of paths than for a $2\times i-2$, and so on. But adding more rows is making it difficult, and I am getting swamped in too specific cases.

Is there a general problem behind this that I am not aware of? I cannot understand if it is a problem of combinatorics or of graph theor. I am ignorant in both of them ..

It is maybe related to domino covering problems, with the constraint that the tiling should form a path, maybe?

marco
  • 365
  • 1
  • 6
  • If you restrict the movement to two directions, say up and right so you start at the bottom left and arrive at the top right it is just Pascal's triangle. If you allow all four directions it is much more complicated. – Ross Millikan Oct 16 '20 at 15:50
  • yes exactly, that killed me, I can think if only two movements are allowed, but not if the four of them are .. – marco Oct 16 '20 at 15:51
  • There are none for even $N$ as you start and end on the same color square so must miss at least one square of the other color. I think I would write a backtracking program to solve the $3 \times 3$ case and maybe $5 \times 5$, then look it up in http://oeis.org/ – Ross Millikan Oct 16 '20 at 16:01
  • wait, consider a $N\times M$ chessboard, you say if I jump on every tile I should touch $N\times M$ tiles, and if the two extreme corners have both the same color, means that I touched an odd number of tiles, and this can happen only if both $M$ and $N$ are odd, right? So this is generalisable to if both $N$ or $M$ is even. In that case the two opposite tiles have always the same color but the total number of tiles is even .. – marco Oct 16 '20 at 16:13
  • Yes, that is correct. – Ross Millikan Oct 16 '20 at 19:22

0 Answers0