« back             Browsing Levels: #443 "Knights and Rotations"
prev: #442 "Knight's Tour" next: #444 "Combination Lock"

"Knights and Rotations" by Brian Potetz

added 20 Mar 2005 16:16
Shortest Solution
NameSpeed Record
Length321 moves
On14 Apr 2005 23:30

Comments (turn spoilers off)
3412 Knights and Rotations noname (559) Sat 09 Jul 2005 12:35 SPOILER
  I solved it by noticing the following:

Claim: If the board can be divided into two halves such that:

(i) One of the halves, when rotated 90 degrees, becomes the other half;

(ii) There is a reentrant knight's tour in one of the halves;

then there is a solution to this puzzle.

Proof: Just identify the two halves. In more detail, just follow the knight's tour in one of the halves: move normally when moving from red to black; and when following the KT from black to red, one just rotate to the other half, make an appropriate knight move, then rotate back to the first half.

So it remains to find a way to split the board into two halves satisfying (i) and (ii). It turns out that when I solved KT, I used eight circuits which has rotational symmetry among them, and I just need to join four of them to yield a solution.
1935 Knights and Rotations bpotetz (144) Thu 14 Apr 2005 23:37 SPOILER
  Congratulations, mjn. Good job. I also solved it using some symmetric circuits.
1934 Knights and Rotations mjn (118) Thu 14 Apr 2005 23:32 SPOILER
  Hey, this wasn't so bad, actually--I found that the rotation squares made it easy to splice circuits together.

Still took a good half hour to work it out on paper, though! Nice level...
1933 Knights and Rotations mjn (118) Thu 14 Apr 2005 23:30 SPOILER
  Added speedrun: 321 moves (old: 999999).
621 Knights and Rotations bpotetz (144) Sun 20 Mar 2005 16:21  
  Here's a variation on the Knight's Tour that I made up. If you're on a red square, you move like a knight. But if you're on a black square, you move by picking up your piece, rotating the board some multiple of 90degrees, and then dropping your guy back down. This variation seems more difficult to me than the original, maybe because the travelling salesman graph is now directed. Let me know if you came up with some elegant way to solve it.