Knight's Tour Update (2/3)

Published on Sunday, April 27, 2008 in , , , ,

Click here to go to Grey MattersHopefully you've been practicing the Knight's Tour starting from any square, and learned how to make sure that you leave yourself openings, as we previously discussed.

After learning to do the Knight's Tour starting from any square, many people find that it almost seems too simple. All you really have to remember is the simple alternation of diamond and square systems, and to keep your paths open. Naturally, many move on to the advanced version of the Knight's Tour, where you let someone else choose the starting and ending squares.

It's great when one chosen space is in a diamond system, and the other is in a square system. As long as you choose your path carefully, this isn't much different from the simpler version.

The challenge comes when they're both square or both diamond systems. On this page, I briefly mention to taking care of a few spaces in one pattern (one system in one quadrant). However, I do feel that I need to go into more detail on this point.

For our first example, we'll start with two diamond patterns, with the starting point (S) part of a left-hand diamond system, and the finishing point (F) as part of a right-hand diamond pattern.

Since the systems are two different orientation, you can complete the first one without conflict (as in Start-16 below), then move onto an opposite system (17-32 cover the right hand square below). As the next step in our example, we need to go to the right-hand diamond system, but since the final square is in this system, we need to minimize the steps in it.

Besides minimizing steps, you'll also need to consider your ability to enter and exit that particular quadrant. You want to go into a pattern, but make sure you leave enough squares that will allow you to enter and exit the quadrant. In the current example, I chose to only move into one square in the right-hand diamond system (#33 below) before moving into a left-hand square system (#34-#37 below), as the squares marked A and B in blue allow for easy entry and exit for that quadrant (not forgetting to move into upper rightmost square for completeness).

From here, you would finish the left-hand square system (#38-#49 below). This leaves us the right-hand diamonds, the location of the closing square, as the only remaining system! It's not over yet, though, as we need to proceed through this final system in a manner than allows finishing on the right square.

In the example below, I began the right-hand diamond system in the lower right quadrant (#50-#53), finished the partially filled upper right quadrant (#54-#56), partially completed the upper left quadrant (#57-#59, skipping the finishing square, of course), then completing the lower left quadrant (#60-#63) so that I finished on the chosen final space (F).

As you can see, a large part of the challenge of the advanced Knight's Tour is getting used to properly breaking up the systems. In the previous example, we not only had to break up the upper right quadrant, but later, the upper left quadrant to allow for ending in the chosen square, as well. Looking ahead to check can seem challenging, but since this is mainly done as your working through the final system, there are fewer spaces, and thus fewer paths with which to deal.

When you're dealing with two chosen spaces that are both in the same system and in the same orientation, such as the starting (S) and final (F) squares in left-hand square systems below, you'll need to get the partial pattern out of the way as the first step.

Moving from the starting point to space #2 below is an easy choice, as it gets a space from the Danger Zone out of the way. From there, you could certainly move to the space marked A (in blue), as it would still leave one space in the upper left quadrant's left-hand square pattern (space B in blue) that would allow you to move in from one quadrant, and exit to another. You'll note that I chose to start on a right-hand diamond system instead (#3-#6).

Yes, the first move could be from S directly into a left-hand diamond system, but since moving to space #2 eliminates a space with limited options (a Danger Zone space), it's preferable to get rid of it as soon as possible.

Leaving two spaces (A and B) open, instead of just one (B), will allow for more flexibility later on. Since you won't be coming back to the left-hand square system until the end of the game, allowing for more options later is a good idea.

From here, the moves in the middle of the game are fairly straightforward. The right-hand diamond system is completed (#7-#18), then the right-hand square system (#19-#34), and the left-hand diamond system (#35-#50).

Now that we're back to the final left-hand square system, we have to take that partially completed upper left quadrant into consideration, and work out how to use it to get to the final square (F). In this particular example, I chose to finish off the lower left quadrant (#51-54), then break up the patterns of the remaining 3 quadrants. The bottom right quadrant was first (#55-#57), then along the outside of the upper right quadrant (#58-#60), and the two spaces we left open at the beginning (#61-#62). The remaining space in the upper right quadrant (#63) is then used to get back to the chosen final space (F).

The real challenge in learning the advanced Knight's Tour is getting used various ways of seeing paths and breaking the patterns that were used so rigidly in the simpler version. As an aid to getting used to pattern-breaking, I created a second level of my Knight's Tour game where you have to wind up just one knight's move away from your starting point. This allows you to use the simpler system alternation strategy you learned initially, while still frequently requiring the pattern-breaking needed for the more advanced version.

I hope you've been enjoying this article, and part 1 of the Knight's Tour series, and found it useful. On the original instruction pages here and here, I've added links to these blog posts, so they're immediately available as you need them.

The final third of this series will be dedicated to my newly-improved OS X Dashboard widget for the Knight's Tour. As I mentioned in the first part, you can already download the improved Knight's Tour widget here (or in the Downloads column to the right) and get a sneak peek before my next post.


Knight's Tour Update (1/3)

Published on Thursday, April 24, 2008 in , , , , ,

Click here to go to Grey MattersThe Knight's Tour instructions and game on this site have always been one of Grey Matters' most popular sections. To keep it fresh and helpful, it's time I made some updates.

I'm going to start by assuming you're familiar with the basic patterns, the systems, and the Danger Zone. Once you've learned about the Danger Zone, you might think that getting that out of the way is all you have to worry about.

However, you may sometimes notice that you can't continue on in the same system, as per the instructions. Let's say you've started in a left-handed square system, and made 8 moves in the following order:

From the 8th square, the only way to stay in a left-handed square pattern is to move onto a square you've already visited (#3). The only other possible moves will place you in one of the diamond patterns! How do we prevent this situation?

When you're working through a system, and you're entering a new quadrant, you need to base your decision to go clockwise or counterclockwise on which finishing square will allow you to move to the next quadrant. In the above example, the decision to go clockwise led back to a completed quadrant. If the decision had been made to go counterclockwise (effectively switching the two moves in blue), the knight would easily be able to move to the next quadrant, and continue with the left-handed square pattern.

There is one point in any tour where this situation will always develop. When you enter the last quadrant of your 3rd system (square 45 in the example below), going one direction will allow to proceed to another quadrant and begin a new system, and going the other direction will leave your knight without any possible moves.

In the above example, the knight began in the upper right quadrant, and the left-hand diamond system was completed, followed by the left-hand square system (starting at 17), and then the right-hand diamond system (starting at square 33). As soon as the last quadrant of the third system was entered (square 45), the decision to go clockwise created the problem. If the player here had stopped briefly to consider their options, it wouldn't be difficult to see that going counterclockwise (effective switching the two moves in blue), would allow the knight to begin working on the final system.

In the second of three parts of the Knight's Tour update, I'll discuss the approach to a problem that is faced by those who allow their audience to choose the beginning and ending squares. In the third and final version of the update, I'll introduce my improved version of Petri Kallberg's Knight's Tour Dashboard widget (Mac OS 10.4.3 or later required). If you want to get a sneak peek, you can download my 2.0 version here (Mac OS 10.4.3 or later required), or from the Downloads section in the rightmost column.


Gas Math

Published on Sunday, April 20, 2008 in , , , ,

Click here to go to Grey MattersIf you do math at all at the gas pump, it's probably either related to how many gallons you can get for a given amount of money, or how much money will be required to get a needed amount of gas. If you're willing to do a bit of math and planning before you go get your gas, you can actually work a surprising amount of real savings into the equation, as well.

How do you save on gas? The obvious first answer is to find the cheapest gas you can. My grandfather's method for this was to drive around looking station by station, but that only works well when you're sure you can find gas lower than 35 cents/gallon. Unsurprisingly, the internet is here to help! Sites such as fueleconomy.gov, FuelMeUp, and GasBuddy make short work of finding the lowest gas prices in your area.

Unless you find the cheapest gas in your immediate area, another question begins to raise its head at this point. Sure, if you go a little farther to that station with the cheap gas you can save some money, but if you factor in the gas you'll burn going the extra distance, and the added gas you'll require, are you really saving money? With the current level of gas prices, this isn't a trivial question.

Fortunately, Kimberly Crandell, better known as Science Mom, tackled the question of whether nearby expensive gas or cheaper gas across town was cheaper last July.

As I've explained, there is some math involved, but there are only five different factors involved: The number of gallons needed, the gas mileage of the car, the cost of the closer (more expensive) gas, the cost of the farther (cheaper) gas, and the miles out of the way for the cheaper gas (Google Maps, Yahoo! Maps, or MapQuest will come in handy here). In the article, you learn the formulas to process this, and how to solve for the savings you'll get, as well as the break even points for cost per gallon, total gas gallons, and distance.

Understanding and working through the formulas is one thing, but how about if you would just like to get your answer and go? Once again, the internet is here to help. My favorite tool for this step is Instacalc, which I first mentioned last August.

I've created an instacalc version of Kimberly Crandell's equations where all you have to do is plug in the five factors (remembering that the two prices requested are both price per gallon).

If you prefer, I've also created a metric version of this calculator, for readers in other countries. Whichever version you use, I hope this helps save you some money and that you find it useful!


Perceptions of People Who Do Mental Math

Published on Thursday, April 17, 2008 in , , , , , , , ,

CalculatorLearning how to do math, especially mental math, can be great, but it does come with a price. It frequently changes how perceive you.

You might think that math teachers, who want you to be good at math, would be exempt from this. However, many math teachers know the area of math they're teaching and just a few other areas. To paraphrase Will Rogers, if you get them off the topic in which they were educated, they're not as knowledgeable.

In his book, Secrets of Mental Math, Arthur Benjamin tells about how he discovered how to square two-digit numbers on his own while he was still young. The method itself was previously known, but he had discovered it independently. One day, in an algebra class, his teacher was working through a problem, and finished by writing the answer as 1082. Young Arthur Benjamin then blurted out that the answer was 11,664!

When he explained the method he was using, the teacher said she had never heard of that before, and young Arthur's mind quickly raced with the idea that he'd made a new discovery! He finishes by mentioning that, when he ran across the same method in a Martin Gardner book, it ruined his whole day.

With my interest in mental math and magic, I had a few similar experiences in my high school days. The first time you watch it, don't try to understand what he is explaining. Instead, imagine you're this guy's math teacher, and being boggled by what he's describing. It helped me finally understand what my math teachers must've gone through when dealing with me.

The worst part about the first time I watched this video was realizing that I could follow the techniques (largely because I'd used them myself before), and realizing how I probably sound when describing ideas like this to others.

If you want to understand the shortcuts he describes, go through the video bit-by-bit until you understand. You can find further help with my technique videos (most notably Arthur Benjamin's own Mathemagics). Sites like Curious Math, Mathpath, and BEATCALC can also help.

On a related note, TV's best known math geek, and his friends, are returning from hiatus after the writer's strike. The ad CBS used to announce the return of Numb3rs appeals to me on several levels. First, it demonstrates the perception non-mathematicians often have of people who are good at math. Second, as a Mac user, I couldn't help but appreciate that they're parodying Apple's well-known Mac vs. PC ads to grab your attention.


Timed Quiz Mnemonics

Published on Sunday, April 13, 2008 in , , ,

Click here to go to Grey MattersLately, we've talked quite a bit about how and where to find various timed quizzes. Of course, once you find them and try them out, the next step is getting better at them!

I can't help you out with every quiz, but many of the topics have been around long enough that several well-known mnemonics have been created for them.

Sporcle's recent addition of the Planets quiz is a good example. Fortunately, they've included Pluto in their planet quiz, so my favorite older mnemonic will work. While there are numerous planet mnemonics, I've always favored My Very Easy Method Just Speeds Up Naming Planets. Some people do get confused between Mars and Mercury, however, I've always remembered that Mercury is closer to the sun by thinking of the mercury in a thermometer, and thinking that the mercury on Mercury is much too high.

Moving in on Earth specifically, how about something that seems really tough, like Mogroware's Geological Time Periods quiz? The phrase Camels Often Sit Down Carefully; Perhaps Their Joints Creak? Persistent Early Oiling Might Prevent Permanent Rheumatism can help, as explained here and here. Some people add Pregnant at the beginning to remember Pre-Cambrian, and others replace Rheumatism with Hurting, in order to remember that the recent period is also known as the Holocene period. In the geological time periods quiz, they also include Mississippian and Pennsylvanian periods, but since these are both named after states, they're easily remembered.

Speaking of history, the answers to the Shakespeare's Plays quiz can be learned by reading my posts on mnemonics for the histories, the tragedies, and the comedies. You may also want to read the comments of the comedies post for another excellent Shakespearean mnemonic method!

I was pleased to see a Taxonomic ranks quiz, as this has been a rich area for mnemonics. While you can find plenty of taxonomic mnemonics here and here, the one I've always used is, Do Kids Playing Constantly On Freeways Get Squished? The Do is used to remember domain, while the rest apply to the standard order.

While Kongregate, Mental Floss and Sporcle all feature quizzes on the elements, this is a long list and isn't easy to remember. The few people who can name the majority of the elements have usually put in the time to learn Tom Lehrer's classic elements song:

For quizzes on the western zodiac, like the ones at Mental Floss and Sporcle, there are several approaches here, including a couple of handy poems. If you're trying to remember the animals of the Chinese zodiac, however, there's an ingeniously simple mnemonic you can use.

Because religion is central to so many lives, it's not surprising that there are numerous Bible-themed timed quizzes, nor is it surprising that so many mnemonics have developed to help people remember these lists. The twelve apostles/disciples can be remembered with this poem, as well as these other memory aids. Being short lists, the Seven Deadly Sins and the Plagues of Egypt can be learned quickly (The Exodus Decoded documentary can also help you remember the plagues).

The first 10 rules that God spoke to Moses on the mountain, often mistakenly called the Ten Commandments (The list on Moses' stone tablets, which is specifically referred to in the Bible as the Ten Commandments, is in Exodus 34, and not in Exodus 20), have a reputation for being hard to learn, but the following video is among the quickest ways of learning them:

Probably the toughest of the Biblical memory challenges, aside from remembering any version of the Bible word-for-word, would be naming all the books of the Old (OT) and New Testaments (NT). The earliest ways of remembering these included finger methods, poems (OT only) and songs. As aids like the Major/Peg system developed, these were used to remember all the Bible books. Computers can help greatly, as this Bible book location game shows (turn off the flashing background, the directional arrows, and the section highlighting for a real challenge).

Any of the numerous flashcard programs on the web can be a great help on any of the subjects you wish to learn. If you're looking for established mnemonics (or ideas for new timed quizzes, for that matter), sites such as Memoria Technica and Amanda's Mnemonic Page can also be of great help.


Timed Quiz News

Published on Thursday, April 10, 2008 in , , , , ,

Click here to go to Grey MattersWOW! Timed quizzes have proven to me popular than even I expected!

After my last post, I tried creating three simple quizzes, each with a 2-minute time limit, whose topics are three-letter body parts, Big Mac ingredients, and Disney's Seven Dwarves. After promoting the three-letter body part quiz on StumbleUpon, the interest was amazing! I'm used around 400 visitors per day, so this was definitely a nice surprise:

Almost all of those visits were to the three-letter body part quiz, too! Thank you StumbleUpon and fellow Stumblers. One person, known only as Felix118, even dugg the post!

Word about the How Many Xs Can You Name in Y Minutes? Dashboard widget is also starting to spread. You can download it from not only this site, but from Softpedia (who gave it their 100% clean award), Maccommand, Widgetworld, and numerous other places. You can even download it via Apple's own site. At this writing, it even currently ranks as the 42nd most-downloaded widget of their top 50!

Remember, even if you don't have a Mac, you can still get the latest timed quizzes by adding the How Many Xs Can You Name in Y Minutes? RSS feed to your newsreader.

There are lots of different topics for these quizzes, of course, and my favorites are the more whimsical ones. Topics such as the Lucky Charms marshmallows and collective names for animals are great, but when it comes to the topic of whimsical timed quizzes, I find this one to be highly relevant (If you don't get this reference, click here for a full explanation).

It looks like my time to talk about timed quizzes is running out. Before I leave, I want to thank all of you who have visited and discovered my site once again.


Timed Quizzes Feed

Published on Sunday, April 06, 2008 in , , , , ,

stopwatchMy earlier post on timed quizzes, How Many Xs Can You Name In Y Minutes?, has proven popular. However, as I was adding new links, it struck me that there are better ways to keep it updated.

In addition to the post itself, the list of timed quizzes is now available as an RSS feed! The address for the feed is http://mentalgym.freehostia.com/files/timedquizzes.xml. That address will remain available over in the rightmost column (If you're not reading this on Grey Matters, click here to see the page) under the Site Feeds section, listed as Timed Quizzes Feed. All you have to do is copy this address into your feed reader, and you'll always know where to find your favorite timed quizzes, as well as when new ones become available.

The feed itself describes each timed quiz very simply. The title is the category of the quiz, such as USA capitals, Canadian provinces and territories, or Lucky Charms marshmallows (yes, that quiz actually exists!). The body describes the source (the site hosting the timed quiz), the quiz's time limit, and tags related to the quiz. The tags are very handy. If you decide you want to limit your quizzes to sports, you just search for sports in this feed in your feed reader, and you'll be shown all the sports related quizzes.

Being an RSS feed, though, there are so many other ways to use it above and beyond just using a feed reader. You may be able to read the feed right in your internet browser. For example, Firefox users can install Sage, and Safari users already have built-in RSS support.

Another fun way to use the RSS Feed is as a screensaver. If you run Windows, you can use RSSMore (Vista users might prefer UniveRSS), and Mac users can use the built-in RSS screensaver. This way, you can be updated any time you come back to your computer!

Finally, widgets and gadgets are a very popular way to read RSS these days. I've already prepared two for you. If you use iGoogle, look over in the rightmost column under Google Homepage Gadgets, and you'll find my Timed Quizzes gadget. Just click the link, press the Add It Now button, and you can have up to the 9 most recent quizzes available on your iGoogle homepage.

For users of Mac OS X 10.4.3 and later, I've also created a How Many Xs Can You Name In Y Minutes? Dashboard widget, which keeps a complete list of timed quizzes:

This will remain available in the Downloads section on the right. Just click that link, or the previous link (or even the picture of the widget!), let it download, click "Install", and select "Keep" when it shows in your Dashboard.

It shouldn't be too hard to adapt the feed to other platforms. Users of Vista should have no problem adapting the RSS Feed Sidebar gadget for use with this, nor should users of Konfabulator/Yahoo Widgets. Do you want this RSS feed to post on your blog or other webpage? Go over to Widgetbox and automatically build a Timed Quiz feed widget!

Regardless of how you choose to use the feed, I hope you enjoy these quizzes. If you know of any timed quizzes I'm missing, or have other comments, please contact me by either leaving a message in the comments, or by clicking the Contact Me tab at the top of the page.


Early Days of Computing

Published on Thursday, April 03, 2008 in , , , , ,

Creative Computing MagazineMy previous post, Computing . . . Without Computers!, was certainly a big hit, largely due to Fuzzy Skinner's link on Metafilter (Thank you for that, BTW!).

The response to that last post has encouraged me to do a second post about computing. I first got into computers when I about 9, and my father's work had an early Commodore PET that could be checked out for the weekends. He had no idea the first weekend that he brought it home that it would start a lifelong passion for me.

Back in those days, there were really only 3 ways to get a program into your computer: load it in from tape cassette, load it in from 5-inch or 8-inch floppy disks (which were actually floppy!), or typing it in from a book or magazine. In the late '70s and early '80s, the computing kings of the hill were Creative Computing and COMPUTE! magazines. Those two magazine probably did more to educate the first personal computer generation than any other force.

As you can guess, this meshed well with my early interest in mathematics (my passion for memory work didn't occur until college). When I was learning about programming, it was quite difficult not to learn about mathematical ideas. For example, I remember a teacher describing Sigma notation to me in technical terms, and I wasn't quite getting it. As soon as he explained that it was just the mathematical equivalent of BASIC's FOR/NEXT/STEP command, I got it instantly!

Creative Computing magazine had many great articles, most of which can be found in the above link, or in The Best of Creative Computing, vols. one, two and three. Their other books, BASIC Computer Games, More BASIC Computer Games, and Big Computer Games, focused on computer games that you could type in and play.

Going through those is an excellent way to get a snapshot of computing's early days. Among the interesting things you'll see there are Hexapawn (mentioned in my previous post), Life (Isn't it amazing how often Martin Gardner's name shows up in these articles?), Life for Two, and even Weekday, a computerized version of the Day of the Week For Any Date feat that, thanks to the Internet, has been taken even further.

I could go on and on about the great programs and techniques I've learned from these pages, but one program stands out in my mind above all others. In the December 1983 issue of Creative Computing (one month before the Macintosh was first introduced!), there was an article and program called POLYMAZE! Solver. This was a maze program by Dan Rollins that was really three articles in one. First, it described how to randomly generate a rectangular maze with only one possible solution, regardless of where the entrance and exits were placed. Second, it described how to take that rectangular maze and turn it into a roughly circular maze. Finally, it taught how to program the computer to find the solution to this maze.

Sadly, the illustrations and program listings are not included in the linked article, but it is descriptive enough that you can piece it together if you know enough programming. However, as proof you can find anything on the internet, PC users can download POLYMAZE.ZIP from this archive.

Another interesting game that appeared in these early magazines was the classic Towers of Hanoi. It was not only a challenging puzzle in its own right, but for programmers it could also be an interesting exercise in programming recursive subroutines (routines that can repeatedly refer to themselves). As you can see from the version on this site, the graphics and sound have come a long way, but the same basic ideas are still there.

As I've tried to get across in numerous other posts, understanding the functional principles is one thing, making them appealing to a mass audience is another. Due to many of the earliest programmers having strong mathematical backgrounds, many of the earliest monster-hunting adventures still had a strong mathematical flavor, such as Hurkle and Mugwump, where you did your hunting on a grid. Many of these were little more than a dressed-up version of the classic Guess game. It would take a young programmer by the name of Gregory Yob to start making adventure games more realistic.

Gregory Yob asked himself, "How many stories has anyone ever heard where monsters are hunted on a grid?!? Shouldn't games like this be more realistic?" When he decided to program an adventure game, he decided to make it more realistic in several ways:

* The monster lives in a cave with several rooms in the form of a "squashed dodecahedron", not a grid.
* Other hazards would be introduced: bottomless pits and "superbats" (which pick you up and drop you in a random room).
* If you were ever in the same room as a bottomless pit, you died as a result.
* You killed the monster by shooting crooked arrow into a series of rooms.
* You would be warned if you were one room away from a hazard, but wouldn't be told which room the hazard was in.
* The monster would be lazy, and generally stay in the same place. However, if you shot an arrow or moved into the same room as the monster, he would either move to another room, or stay in the same place. If you and the monster were in the same place after the monster made its choice, it ate you up!

The result was the first hit computer adventure game, Hunt the Wumpus, in 1972. If you would like to try playing it yourself, here's a playable online version. Even though it free to type in and copy, it spread like wildfire, and by a year after its release, you could find people playing it anywhere you found a computer center. The game was so successful it even spawned a sequel, which featured 5 more caves and the even the ability to create your own caves!

It was the Wumpus games more than any other that started the move towards realistic computer games. In 1976, Colossal Cave Adventure, also know simply as Adventure, helped push the genre even further with breakthroughs such as natural language commands, puzzles to solve, and magic spells. It could be said that Adventure is the father of today's adventure games, and Wumpus is the grandfather. You can also play the original version of Colossal Cave Adventure online.

It wasn't long before there were numerous books and articles on programming your own adventure games. Creating Adventure Games On Your Computer and BASIC Computer Adventures were among the most popular early books of this type. I still remember picking up the July 1983 issue of COMPUTE!, and learning about adventure game programming.

Going back through these archives makes me realize that there is at least one concept that is as true for computers as it is for any other area of study: If you want to develop something that is perceived as new and original, start by going through the older works in the field, not the newest.