Knight’s Tour: Animated GIF

I run hot and cold on Wikipedia, but I stumbled upon this animated GIF of a Knight’s Tour, and thought it was worth sharing. The Knight’s Tour is a mathematical puzzle that requires a knight to visit every square on the board once using his standard move. The GIF is the work of Ilmari Karonen, and uses the following moves:

e8 g7 h5 f6 e4 g3 h1 f2 d1 b2 a4 c3 d5 b6 a8 c7 b5 a7 c8 d6 c4 a3 b1 d2 f1 h2 g4 e3 f5 h6 g8 e7 c6 d8 b7 a5 b3 a1 c2 d4 f3 e1 g2 h4 g6 h8 f7 g5 h7 f8 e6 f4 h3 g1 e2 c1 a2 b4 d3 c5 a6 b8 d7 e5

There’s a beautiful symmetry in the finished solution. If, for some reason, the animation starts in the middle, just let it play out and it should loop around to the beginning.

ToneMatrix: Your Amazing Time-Waster of the Day

The developer describes ToneMatrix as a “simple sinewave synthesizer triggered by an ordinary 16step sequencer. Each triggered step causes a force on the underlaying wave-map, which makes it more cute.” It’s the work of Andre Michelle, and it’s flat-out amazing in its addictive simplicity. If he converts this to a mobile app, he’ll make a pot of money.

I found this one courtesy of my National Catholic Register colleague Simcha Fisher, the irritant who helps little grains of sand become wondrous pearls, whether we want to or not.

Mad Science Fold-ins

This is a draft of a story I’m working on for Games.

There are things artificial intelligence just can’t do, and protein folding is one of them. That’s why Fold.it and other resources are drawing on the puzzle-solving skills of a network of gamers to solve complex problems in protein folding. It’s an approach that is finally yielding its first concrete results.

To understand the nature of this challenge you need to understand a bit of biology. Proteins perform the vital tasks necessary for any living object, be it a human being or a plant. They carry oxygen, transport nutrients, power muscles, and speed up chemical reactions. They do all the work that keep organisms alive and functioning.

Each protein is a chain of linked amino acids. There are twenty different kinds of amino acid, with each defined by its particular combination and arrangement of carbon, hydrogen, sulfur, nitrogen, and oxygen atoms. These atoms come together in an unbranching chain to create a protein. Each main chain functions like a backbone, while each amino acid also has some dangling atoms, which form side chains.

These chains don’t like to just hang about in a single line. They tend to compress into a blob through a process of “folding.” The aminos for each different type of protein fold into the exact same configuration every time. Some amino acids are kept on the inside of the folded protein, while others remain on the outside. Some amino acids need to be near a particular type of amino, while others need to be kept apart. Each protein assumes the most efficient folded shape possible. When proteins fail to form correctly they can’t do their job, resulting in diseases like cancer, Alzheimer’s, and HIV/AIDS.

Proteins can assume incredibly complex structures. A simple one may have a chain of a hundred amino acids, while a complex one may have a thousand. Each amino has to find its place in a correctly-folded chain in order to work. Untangling this knot has proven difficult for computers. Folded proteins are three-dimensional objects, and the number of potential variables is so high that computers are simply inefficient or ineffective.

Humans, however, have an innate, almost mysterious, intuition for pattern recognition and puzzle solving. A computer can only run through every variable, evaluate them all, and try to choose the best one. Puzzle-solving humans don’t do this. We don’t run through every possible version of a puzzle to solve it. We use observation, deduction, intuition, and spatial reasoning skills to evaluate the puzzle, then attempt to find the solution. It’s a vastly more efficient method of problem solving.

The University of Washington’s Center for Game Science decided to tap that power by creating Fold.it, a free game that challenges people to fold protein chains into the most efficient possible shapes. The game begins as a serious of tutorials to introduce the tools and the concepts for protein folding. Each puzzle consists of a 3D representation of a known protein.

The goal is threefold. First, you need pack the protein folds as tightly as possible to eliminate any gaps. Some aminos need to be touching water (hydrophilic) and some need to be protected from water by other aminos (hydrophobic). Thus, the second goal is to place the hydrophilic/hydrophobic aminos in their proper place. Finally, you need to eliminate the “clashes,” which are the places where aminos occupy the same space, or are merely too close together.

The first goal of Fold.it was to see if humans could properly solve protein folding problems. The proof-of-concept trials went well, so Fold.it presented puzzles that were challenging the current automated folding software. People could compete, alone or in teams, for “high scores” by folding proteins in the most efficient manner.

Fold.it had its genesis as an experiment in distributed computing, with people volunteering their computers to aid in the complex calculations needed for protein modeling. The participants would see a screen saver that showed the progress of the automated models, but those watching the screen quickly noticed that the automated modeling was not efficient. That’s when the team created Fold.it to allow people to modify the protein models themselves.

The breakthrough came when the gamers were presented with the Mason-Pfizer monkey virus (M-PMV) retroviral protein, which cause a form of simian AIDS. In an article in the journal Nature Structural & Molecular Biology, the Fold.it team observed that “retroviral proteases (PRs) have critical roles in viral maturation and proliferation and are the focus of intensive antiretroviral drug development work.” Various software models were unable to resolve the structure of the M-PMV retroviral protease. Gamers were provided with a variety of unsatisfactory M-PMV PR models, and then challenged to create a better one. Scientists had been struggling with the structure of this protein for over ten years. When the models were made available on Fold.it, a group of gamers on three continents were able to collaborate and solve the problem in a matter of days.

With the input of human problem-solving, the software modeling suddenly improved. After 600 gamers on 41 teams submitted 1.25 million solutions, the team was able to narrow the field down to 5000 by comparing the models against x-ray data. One team, “The Contendors,” submitted a model that aligned perfectly with this data, and the Fold.it team knew they’d cracked the code.

As the authors write in their Nature article, “The critical role of Foldit players in the solution of the M-PMV PR structure shows the power of online games to channel human intuition and three-dimensional pattern-matching skills to solve challenging scientific problems. Although much attention has recently been given to the potential of crowdsourcing and game playing, this is the first instance that we are aware of in which online gamers solved a longstanding scientific problem. These results indi­cate the potential for integrating video games into the real-world scientific process: the ingenuity of game players is a formidable force that, if properly directed, can be used to solve a wide range of scientific problems.”

And thus the Fold.it experiment continues. You can join the process as http://fold.it.

App O’ The Mornin’: Cut the Rope: Experiments

Grade: A

Price: $1
Cut the Rope is one of the few games to challenge the dominance of Angry Birds in the hearts and devices of app gamers. Cute, clever, and insanely addictive, it combines a wonderful puzzle mechanic with an appealing visual style to make a knock-out game.

Cut the Rope is one of those rare games where the title is also the instruction manual. In a series of single-screen puzzles, hanging objects function like pendulums. You need to cut the ropes at precisely the right time and in exactly the right sequence to get the object where it needs to go.

In this case, the problem is how to get a piece of candy into the mouth of a voracious (yet adorable) little monster named Om Nom. Each puzzle has three stars and a piece of candy.  Cut the rope with a finger swipe, and the candy collects the stars as it drops into Om Nom’s mouth. It’s fairly easy to get the candy into the monster’s mouth, but to get it there while collecting all three stars can be incredibly challenging.

The original game came with 4 sets of 25 puzzles each, and more sets were released with updates and holiday packs. In the first full-blown sequel–Cut the Rope: Experiments–the initial set of puzzles functions as a recap of the entire first game.  All of the many puzzle elements are re-introduced: balloons, whoopee cushions, spiders, rubber bands, ropes, and so on. 
There are only two other puzzle sets: “Shooting the Candy” and “Sticky Steps”–for a total of 75 puzzles. This is fewer than the original, but updates are promised.
The new gameplay elements are certain to appeal to CtR Fans. The targeting button shoots a rope to the candy as it swings. This rope can be of various lengths depending upon how far away the candy is when you fire. If the candy is swinging close to the rope shooter, the rope is short; if it’s further away, the rope is longer. 
The other new element is the suction cup. Tap this cup, and it comes loose from the “wall” of the puzzle and begins to drop. This allows you to reposition ropes, creating far more variables on each screen.
These new features are run through their paces in two sets of twenty-five puzzles each, creating complex variations of the familiar CtR gameplay. Lvels are of consistently high quality. The basic solution usually isn’t all that hard, but earning 1, 2, and 3 stars can be brain-bendingly difficult. There are some I simply couldn’t solve at the 3-star level no matter how many times I tried. That’s a good thing: it means the game is still challenging, which keeps it interesting.
It is a bit disappointing to have only 75 puzzles and 2 new elements, but there’s more than enough here to keep things fun and fresh, and the updates give you something to look forward to. Cut the Rope is one of the best puzzlers in mobile gaming, and Experiments only further cements its reputation.

The New Cut the Rope is Due …

… tonight! It’s called Cut the Rope: Experiments. TechCruch was able to squeeze a few meager facts out of the developers:

What on earth is Om Nom?! That’s what millions of fans of the widely acclaimed game, Cut the Rope, have been asking about the cute little monster who eats candy like its his job! That same question has a mad (but not bad) scientist studying the little creature that mysteriously arrived outside his house.

There’s a teaser trailer up at TechCrunch, but it doesn’t have any in-game footage. I think Cut the Rope’s gameplay kicks Angry Birds in its feathery butt, so you better believe I’ll be checking the app store around midnight. 

Kenken: Sudoku With Math

Kenken is a Sudoku variant invented by Tetsuya Miyamoto as a way to teach math. Frankly, Sudoku bores me senseless, but I found the addition of math makes the puzzles much more interesting.

The game is played on grids ranging from 4×4 to 9×9, and the rules are as follows:

  • Do not repeat a number in any row or column.
  • The numbers in each heavily outlined set of squares, called cages, must combine (in any order) to produce the target number in the top corner of the cage using the mathematical operation indicated.
  • Cages with just one box should be filled in with the target number in the top corner.
  • A number can be repeated within a cage as long as it is not in the same row or column.
Short version: the numbers you place in the bold boxes need to yield the number in the corner by multiplication, division, addition, or subtraction. 
Here’s a video with Will Shortz (former editor of Games Magazine) explaining how to play.You can find playable puzzles at Kenken.com.

PUZZLE: Tabling the Question

I haven’t done a math puzzle in a while, so here’s an old one to strain the average brain. (And by that I mean my brain: in the past, my readers have solved these so fast it’s almost embarrassing.)

Mr. Jenkins comes home to find his son Todd reading a comic book rather that working on his quadratic equations. He sets about berating the boy, when Todd interrupts him with a deal. “If I can pose a problem you can’t solve, you have to finish my homework, and I can to finish my comic.” Mr. Jenkins, considering himself something of a math whiz, takes this bet in a heartbeat.

Todd pushes a large, perfectly round table into a corner, with its edge touching both walls. He places a spot and then turns to his father. “That spot,” says Todd, “is exactly 9 inches from one wall and 8 inches from the other. Without measuring the table, tell me its diameter.”

My Jenkins puzzled and puzzled ’til his puzzler was sore, and then wound up finishing Todd’s homework while the boy returned the adventures of Uncle Scrooge. Would you have done any better?

Review: Stacking (XBLA/PS3)

A game set at the turn of the century dealing with child abduction, labor strife, and poverty, all done in a whimsical silent-movie style and featuring a cast of matryoshka (nesting) dolls with diverse powers? Yeah, Tim Shafer and Double Fine Productions are back.

Stacking is a small, Xbox/PSN Arcade game developed simultaneously with Double Fine’s more high-profile Brutal Legend, and is altogether more entertaining and imaginative than its big-budget cousin.

Stacking concerns the adventures of Charlie Blackmore, the smallest member of a family of nesting dolls. When his siblings are kidnapped and forced into indentured servitude, Charlie is left behind due to his small size. This, however, becomes one of his greatest assets, because Charlie is able to “nest” in any doll that is one size larger than him.

Each kind of doll has a unique power. Some of these are useless, such as playing tag or going to the bathroom. But some are essential for solving puzzles, and therein lay the key to the gameplay. If you need to lure a doorman away from his door, you can use the female doll that screams (he’ll rush to her aid) or the female doll that “seduces” (he’ll fall in love and abandon his post for a few seconds). Many locations include multiple solutions, so you might find yourself clearing a room by (ahem) passing gas into a ventilator, or by infiltrating the room as a mechanic, or by sneaking past the guard.

The variety of dolls and powers along with the detailed environments mean the game is rich in content. You can simply go about collecting new dolls and trying out their powers. You can search out sets of matching dolls in order to learn their stories. Or you can just follow the adventure where it leads by talking to characters and using various doll abilities to solve puzzles.

This is an immensely clever and appealing game. There is a bit of potty humor (belching, flatulence, bathroom visits, etc), but nothing too offensive. The odd and disappointing part is the length. For a game that is jammed with detail and loaded with potential, the adventure itself plays out rather quickly. A sequel—The Lost Hobo King—is already out, but it’s even shorter. I guess there are worse things to say about a game than “I wish it went on longer.”

Eyeball Benders–Vacation Edition ANSWERS

Wow. I knew I made these hard, but I thought some Orlando visitors would have recognized some of them. No luck: no one figured out any of the answers, so here’s each original Eyeball Bender with the larger picture from which it comes.
1. Hogwarts Castle: Wizarding World of Harry Potter (Universal)

2. St. George & the Dragon: Germany Pavilion, Epcot

3. The Lorax: Universal Islands of Adventure

4. Daisey Duck: Disney World

5. Beetle Bailey: Universal Islands of Adventure

6. Butterbeer Cart: Wizarding World of Harry Potter (Universal)

7. Magic Brooms: Disney Hollywood Studios

Over the Top: The World’s Most Complex Rubik’s Cube

I have never solved a Rubik’s Cube, and never really tried. Thus, a Super-Sized Rubik’s Cube, dubbed “Over the Top” by its inventor, holds even less appeal, particularly when it appears to take about a minute to align the parts correctly in order to make each turn.

A normal Rubik’s Cube is 3x3x3. Designer Oskar van Deventer has used new 3D printing techniques and some impressive engineering to design one that is 17x17x17. You can even buy your very own version, for $2006.54, at Shapeways, a 3D printing company. Here’s how it came to be, according the Shapeways

When Oskar heard of the world records being set for twisty puzzles, like the 7x7x7, 9x9x9 and 11x11x11 by Panagiotis Verdes from Greece, he wanted to try his hand at setting a new record himself. With sponsorship from his close friend Claus Wenicker, Oskar set about designing and testing a number of prototypes, and his third attempt was printed successfully with Shapeways. Sorting and dyeing all 1539 pieces took Oskar 10 hours of work, followed by 5 hours of assembling. The result is an oversized (140 millimeter, 5.5 inches) and fully functioning “Over The Top” 17x17x17 puzzle.

3D Printing is fascinating technology that allows anyone to create a viable 3D model, and then have it turned into a real object. Shapeways describes it as “any additive manufacturing process whereby one machine turns a digital file into a finished physical object by building up that object layer by layer. If you were to be more precise the technology would be called rapid manufacturing and 3D printing would just be one of the manufacturing processes used to create objects in this way.”
These videos show Oskar explaining his amazing design. Frankly, the skill and technology that went into creating it is more interesting, to me, than the puzzle itself.

This is Shapeway’s demo showing the entire process from design through completion: