Knights

knightsThere’s an old puzzle involving four chess knights, two black and two white, in the corners of a 3×3 board. Making only knight moves, you’re supposed to swap the positions of the black and white pieces. The key to solving it is to think in terms of the topology of how the squares are connected by knight moves instead of the geometry of the board. To a knight, the center square is unreachable, and the other eight are each connected to exactly two others, forming a single loop. Swapping the knights is as simple as having them chase each other around that loop halfway.

Knights is essentially a generalization of that puzzle. In each level, you have a board with some red and blue knights on it, and have to move them to target squares of the same color. Some squares will be blocked off. After a certain point, it introduces yellow knights, which don’t have targets and only exist to clog things up and get in the way of the other knights. And that’s it for rules. It’s presented in a clean, elegant graphical style that’s immediately comprehensible, requiring not a word of tutorial explanation. While the puzzles are more complex than the Four Knights puzzle, I don’t think it’s a ruleset with a great deal of room for variability. But that’s okay, because the game is also pretty short.

It definitely trains your brain up, though. After working through the bulk of the levels, I was seeing knight-move connections far more easily than when I started, even perceiving the relevant topology directly. There are a couple of levels that try to confuse you with yellow knights in places that are completely disconnected from anything that the red and blue knights can reach, but by the time I reached these levels, the ruse seemed laughably obvious in a way that it probably wouldn’t have when I started.

The day after finishing the game, I experienced some pretty strong Tetris effect, tracing knight-move patterns with my eyes on the seats around a table and suchlike. Mostly I traced the eight-pointed star that’s the basis of the original Four Knights puzzle. This is a pattern I kept returning to again and again over the course of the game, a sure-fire if tedious method for shifting a knight around short distances without disturbing things elsewhere on the board. Even if seven of the eight spaces in such a ring are occupied, it’s possible to shuffle them slowly around.

The later levels tend to interfere with such rings by blocking off squares. This can create dead ends in the connectivity graph, trapping pieces behind a bottleneck until you can consolidate enough empty space to let them free. This, in turn, forces the player to think hierarchically: “I’ve got to get that piece out of the way, but I can’t do that until I can move this piece”, etc. Completing the last level gives you access to the daily puzzles, which, if I understand correctly, are generated procedurally. I’ve only tried these a little, but it seems to me that, lacking a human designer’s sense of symmetry and beauty, the daily puzzles are even more prone to multiple-tiered blockage of this sort. This makes the puzzles take longer to complete, but it doesn’t necessarily make them more difficult to figure out.

I suppose there’s a balance to be struck. If things are too loose, if there’s too much empty space and the player has too many options, the puzzle becomes easy, because it’s easy to get things where you want them. If things are too tight, and the player has too few options, the puzzle becomes easy because there’s so little opportunity to go wrong. But then, this only applies once you’ve played enough puzzles to look at things the right way. The original Four Knights problem fits into the too-few-options category, but only if you can see it as a loop.

2 Comments so far

  1. matt w on June 29th, 2016

    I often find myself tracing patterns like that even though I’ve never spent any appreciable time playing this game. It’s something that I was particularly prone to do with the buttons on the clickers they would give me to vote in faculty senate meetings (4 x 3 grid).

  2. Vincent V on July 1st, 2016

    Your last paragraph touches on some interesting computer science topics. It’s been studied that the problems that are difficult to solve for computers (NP-complete) are only hard in specific cases, but for random parameters they often are not.

    In fact, it has been shown that every NP-complete problem has a parameter that governs this behaviour, and result in either an overconstrained problem (it’s easy to prove there is no solution), underconstrained problem (it’s easy to find one out o many solutions) or a remarkable phase transition between those two, where the really hard to solve problems are.

    You can pretty easily find academic references on this by searching for ‘phase transition NP-complete’ or something similar.

    I suspect this is happening in these puzzles. This academic result seems like an interesting thing to know about if you want to randomly generate interesting puzzles!

Leave a reply