I'm wondering if there's a way to check if every square of a board can be visited such that every time you move to a new square, it can't be in the same row, column, or diagonal as the previous square. If it can, how could I find a sequence of squares that works? I've ascertained that it can't be done if $\text{rows} + \text{columns} \leq 6$. It kind of reminds me of the n queens problem, but I'm not sure how to proceed.
Asked
Active
Viewed 63 times
-1
-
Uh... It seems like you are doing Google Code Jam, which is currently running.... – athin Apr 13 '19 at 03:20
-
This post has been locked, as it is taken from an ongoing contest. For more information see our policy on Questions from Ongoing Contests. It will be eligible to be unlocked when the contest ends, 4/28/19. – Rubio Apr 13 '19 at 03:46
-
(And now unlocked.) – Rubio May 10 '19 at 05:27
1 Answers
1
If I am understanding your question correctly, a Knight's Tour would satisfy your restrictions. Each knight move ends up on a different row and column from the starting point, and is not on a diagonal from it. This is more restrictive than necessary for your purposes, but at least sets a base case that you know is possible.
From the Wikipedia page for Knight's Tour:
Schwenk proved that for any $m \times n$ board with $m \le n$, a closed knight's tour is always possible unless one or more of these three conditions are met:
- $m$ and $n$ are both odd
- $m = 1, 2,$ or $4$
- $m = 3$ and $n = 1, 2, 3, 5$ or $6$
Cull et al. and Conrad et al. proved that on any rectangular board whose smaller dimension is at least 5, there is a (possibly open) knight's tour.
So those would give some minimal constraints for which a Knight's Tour is provably possible.
