返回题库

骑士动作 5

Knight Moves 5

专题
Discrete Math / 离散数学
难度
L7

题目详情

An 8-by-8 “lattice” is represented above. A knight arrives at a1 at time T=0, and wishes to travel to the upper-right corner (h8). This lattice respresents a 3-dimensional landscape; the numbers at each “point” represent their altitudes.

But there’s a big problem here, which is that this grid was built on a swamp, and the lattice points are prone to sinking. Whenever the knight arrives on a lattice point of altitude A, that point and all others with the same altitude start sinking at the rate of 1 unit per n minutes, where n is the number of lattice points of altitude A. Furthermore, the lattice point diametrically opposite the one the knight is on rises at the rate of 1 unit per n minutes. This sinking (and rising) continues only while the knight remains stationary, which may be for as much or as little time as the knight chooses. No other points move or begin to move during this time. (Altitudes can become negative. In the event that the “opposite” point is at the same initial altitude, it neither rises nor sinks, and is ignored for the purpose of calculating n.)

The knight is only allowed to make 3-dimensional jumps that are permutations of (0,±1,±2) – that is, jumps that move exactly 0 units in one dimension, exactly 1 unit in another, and exactly 2 units in the third. Jumps take 0 time to complete. In the spirit of a knight’s “tour”, your goal is to find the path to the upper-right corner that takes as much time as possible. Tours of 180 minutes or longer are eligible for the leaderboard.

Updated 11/6: Due to some shortsightedness on our part we forgot to include the following extra rule. All “sinks” in a tour must be necessary sinks. That is, if a jump (t, P) has t > 0, it must be the case that there exists a value t’ such that replacing (t, P) with (t’, P) would result in an illegal move or would cause a move later in the tour to be illegal. (Our tour operator regrets the oversight.)

To enter, send in a comma-separated list of moves. Please use the notation (t , P) to describe a move, where t is the number of minutes you wait at your current lattice point before jumping to lattice point P. (The 19-move sequence in the example above would begin “(1, b3), (0, a3), (0, a2),…”.) Your tour ends as soon as you first reach h8; all other lattice points may be visited at most 3 times. (Your starting state at a1 counts towards this limit.)

Updated 11/21: We’ve really enjoyed the variety of tours we’ve received thus far! The regional tourism board has designated certain tours for being particularly special, using the following citations:

LT: very Long tours (in total Time spent)
LJ: very Long tours (in total number of Jumps)
SJ: very Short tours (in total number of Jumps)
E: visits Every point at least once
U: does not visit any point more than once (i.e. Unique points)
H: finishes at a High-altitude h8
L: finishes at a Low-altitude h8
S: contains at least once very large Sink

解析

Original Explanation

This month’s puzzle was an open-ended challenge: to find a knight’s tour from a1 to h8 on a constantly shifting 3-dimensional board.

In the end we received a wide variety of tours. We’ll mention a few of the most interesting ones below. (Their “finishing states” are all shown above.)

The longest1 valid tour came from Brandon Cage, which takes 1547 minutes.

The second-longest2, at 1482 minutes, came from Calvin Pozderac. This tour also set the records for “lowest finishing altitude” (-32) and “longest individual sink” (364 minutes).

The most efficient tour3 came from Sondre Rogde, who managed to get from a1 to h8 in just 33 jumps.

The first tour4 (out of just two) we received that managed to visit every point at least once came from Anton 3 Terekhov.

Those were some of our favorites, but congrats to everyone who managed to find a valid tour!

Some open problems we were pondering:

  • What’s the longest valid tour? (Can 2000 minutes be achieved?)
  • What’s the highest possible finishing altitude? (The highest we saw was 19; could it be as high as 25?)
  • Does there exist a valid tour that does not repeat a single point? (I.e. the unclaimed “U” designation from the tourism board.)
  • Is it possible to finish a tour with every point at the same altitude? If not, what’s the largest group of same-altitude points that can be obtained?
  • Does there exist a valid tour with “max sink” < 10? (The lowest “max sink” we saw across any valid tour was 27.)

If you’re able to solve any of these problems, feel free to let us know! (We might update the leaderboard for especially interesting submissions.)

  1. (0, b1), (0, b3), (0, c3), (0, a3), (0, a4), (0, a5), (0, c4), (0, c6), (0, b6), (0, b7), (0, c7), (3, e8), (0, f8), (0, e6), (0, e5), (0, g5), (7, f5), (0, h5), (6, h6), (0, h7), (0, g7), (3, g6), (4, e6), (0, e7), (0, f7), (9, f5), (0, e5), (0, d5), (0, c5), (0, c4), (0, d4), (0, d2), (0, c2), (0, b2), (0, b3), (16, c3), (0, c2), (0, b2), (16, c2), (12, d2), (7, e4), (0, d4), (0, c4), (0, c5), (0, d5), (0, f4), (0, h5), (0, h6), (0, g8), (0, f8), (0, e8), (0, c7), (0, e7), (0, f7), (0, g7), (0, g6), (8, g7), (4, f7), (12, e7), (2, c8), (20, d6), (0, d8), (5, b7), (28, d6), (58, f6), (10, h7), (39, g5), (47, h7), (49, f6), (0, g4), (0, h2), (0, f3), (0, h2), (0, g4), (0, f6), (0, e8), (54, c7), (0, e6), (0, f4), (0, h5), (57, g3), (0, e2), (0, c1), (126, a2), (0, c3), (0, b1), (62, d2), (0, b3), (122, c1), (0, a2), (0, b4), (120, c6), (0, d4), (0, b5), (118, a7), (0, c6), (0, a5), (116, b7), (0, c5), (0, a6), (114, b4), (0, d5), (0, b6), (56, d7), (0, b8), (110, d7), (0, b6), (0, c8), (108, d6), (0, e4), (0, f2), (0, f1), (0, g1), (0, g3), (0, h3), (0, h4), (0, g4), (0, g5), (0, g6), (0, g8), (0, f8), (19, h8) ↩

  2. (0, b1), (0, c1), (30, a1), (0, b1), (35, c1), (6, c2), (3, a1), (0, c1), (18, d3), (0, d4), (0, c4), (0, a5), (0, a4), (0, a3), (0, c2), (0, d2), (0, d1), (0, e1), (4, f1), (5, h2), (0, h3), (7, g5), (0, f3), (14, f1), (60, h2), (0, h1), (0, g1), (0, e2), (0, d4), (0, c4), (0, a5), (0, a4), (0, a3), (0, c2), (0, d2), (0, d1), (2, e1), (0, f3), (0, g5), (0, e4), (0, c5), (0, c6), (0, d6), (5, d7), (6, e7), (0, c7), (16, c5), (0, c6), (1, d6), (5, f5), (0, f3), (2, h4), (3, h3), (0, g5), (0, g4), (0, f4), (0, h5), (0, h6), (0, h7), (0, f7), (24, d8), (0, d6), (0, d5), (0, f4), (0, h5), (0, h6), (0, h7), (0, g7), (1, g8), (0, f8), (14, e8), (12, f8), (12, h7), (45, f8), (19, g6), (364, f6), (20, f7), (112, f6), (20, f7), (112, f6), (20, g6), (112, f4), (0, h3), (0, h2), (5, f2), (27, e4), (26, g3), (25, h5), (0, g3), (0, e4), (0, c5), (0, d5), (0, e5), (24, d5), (1, b6), (9, b5), (116, b6), (12, b5), (116, a7), (0, b5), (0, b6), (12, b7), (0, d8), (0, c6), (0, e7), (0, g6), (0, h8) ↩

  3. (0, b1), (0, b3), (0, c3), (0, a2), (9, a3), (0, a4), (0, a5), (0, c4), (0, b4), (0, b6), (0, b7), (0, c7), (6, a8), (18, b6), (0, d5), (0, f4), (0, g2), (0, h4), (0, f3), (68, d3), (0, b3), (95, a3), (0, a4), (0, a5), (0, c4), (0, e4), (2, e5), (0, e6), (0, e7), (0, f7), (0, g7), (1, h7), (0, h8) ↩

  4. (0, b1), (0, b3), (8, c3), (0, e3), (0, d3), (0, d4), (0, c4), (0, e4), (0, f2), (0, f3), (0, g5), (0, h5), (6, h3), (0, g5), (0, e5), (0, c5), (0, c6), (0, a6), (0, a4), (3, a2), (0, c3), (0, e3), (0, d3), (0, d4), (0, c4), (0, b4), (40, a4), (0, a2), (0, c2), (0, b2), (0, d2), (0, d4), (0, c4), (0, c6), (0, b6), (0, b8), (0, c8), (0, d8), (0, f7), (0, g7), (0, g5), (0, g6), (10, g7), (2, g8), (0, h6), (0, g6), (6, h4), (10, g4), (0, h4), (32, f5), (54, f3), (7, h4), (0, g2), (0, f4), (70, f2), (4, h1), (0, g1), (0, e2), (0, e1), (42, g1), (0, g3), (0, e4), (0, d6), (0, b7), (0, c7), (0, c5), (1, b5), (0, a7), (0, c8), (0, e7), (0, d5), (120, e5), (0, e6), (0, f6), (0, f5), (0, g3), (0, h1), (0, h2), (0, f1), (0, d1), (0, d3), (0, c1), (0, c3), (0, a3), (0, b5), (0, b4), (0, b3), (0, a5), (0, b3), (0, a1), (0, c2), (0, e1), (0, e2), (0, e4), (2, e6), (0, f8), (0, h7), (0, f8), (0, d7), (0, b6), (0, a8), (0, b6), (0, c8), (0, d6), (0, e8), (0, d6), (0, f7), (0, h8) ↩