Enumerating the Kight’s Tour

So, I got a little sidetracked tonight by a brief mention of the Knight’s Tour problem.  I wasn’t interested in solving the problem — I was just curious how many possible 64-move tours could be made.  Following is a reference image and the Mathematica code:

(*
Let fn[x] be the number of possible move sequences of length
(x-1), starting from square n.

Also, let An be the set of immediate possible "next move"
squares, starting from square n.

Then fn[0] is the number of squares in An, and fn[x] for x>0
is the sum of fi[x-1], for each square i in An.
*)

f0[x_] := Piecewise[{{2, x == 0},
                     {2*f5[x - 1], x > 0}}];

f1[x_] := Piecewise[{{3, x == 0},
                     {f2[x - 1] + f7[x - 1] + f6[x - 1],
                    x > 0}}];

f2[x_] := Piecewise[{{4, x == 0},
                     {f8[x - 1] + f5[x - 1] + f1[x - 1] +
                      f6[x - 1], x > 0}}];

f3[x_] := Piecewise[{{4, x == 0},
                     {f4[x - 1] + f7[x - 1] + f5[x - 1] +
                      f8[x - 1], x > 0}}];

f4[x_] := Piecewise[{{4, x == 0},
                     {2*f3[x - 1] + 2*f8[x - 1], x > 0}}];

f5[x_] := Piecewise[{{6, x == 0},
                     {f3[x - 1] + f8[x - 1] + f9[x - 1] +
                      f6[x - 1] + f2[x - 1] + f0[x - 1],
                    x > 0}}];

f6[x_] := Piecewise[{{6, x == 0},
                     {f2[x - 1] + f7[x - 1] + f8[x - 1] +
                      f5[x - 1] + f1[x - 1] + f9[x - 1],
                    x > 0}}];

f7[x_] := Piecewise[{{8, x == 0},
                     {2*f9[x - 1] + 2*f3[x - 1] +
                      2*f6[x - 1] + 2*f1[x - 1], x > 0}}];

f8[x_] := Piecewise[{{8, x == 0},
                     {f3[x - 1] + f5[x - 1] + 2*f8[x - 1] +
                      f9[x - 1] + f6[x - 1] + f4[x - 1] +
                      f2[x - 1], x > 0}}];

f9[x_] := Piecewise[{{8, x == 0},
                     {2*f5[x - 1] + 2*f6[x - 1] +
                      2*f7[x - 1] + 2*f8[x - 1], x > 0}}];

fall[x_] := 4*(f0[x] + f4[x] + f7[x] + f9[x] + 2*(f1[x] +
               f2[x] + f3[x] + f5[x] + f6[x] + f8[x];

(* This will run for a LONG time! *)
fall[63]

Update: I woke up this morning and realized that Mathematica was re-computing all the function values multiple times, so the above code will run (virtually) forever. I didn’t know how to make it “save” each computed value for later, so I just did it manually. Here is the updated mathematica file. Anyway, it turns out that there are on the order of 4*10^51 possible moves (3926356053343005839641342729308535057127083875101072, to be exact) that can be made.

To give you an idea of how many moves that is, let’s imagine that the smallest microchip in the world (1.6875*10^-13 m^3) can simulate a move every 12 attoseconds (the shortest time interval ever measured). Now, imagine that you have enough of these microchips running in parallel to build a super computer the size of a minivan (180 in x 72 in x 60 in). Even with these impossibly fortuitous conditions, every star in the universe would be expected to die out (roughly 2*10^13 years) before the simulation was finished.

Update: Adjusted size of imaginary supercomputer. Sorry about that.

Building The josIpod (part III)

The grand finale, peoples!  Enjoy:

THE IPHONE/IPOD TOUCH APPS THAT I CANNOT LIVE WITHOUT

Dropbox is the ultimate flashdrive-in-the-sky system — WITH A MOBILE APP!!!  If you’re like me, you have about 30 different computers that you use — depending on your mood, location, and which computers your classmates and family members are busy using.  If you’re like me, you also are pretty darn afraid of using thumb drives because of their slow speed, risk of data corruption (I’ve actually had a mis-configured windows XP box “eat” my homework before), and “misplaceability.”  Dropbox creates a folder on your local hard drive that gets automatically sync’ed with all of your other computers.  The iPhone app can’t edit the files, of course, but it can download documents for offline viewing — perfect for reading papers or homework assignments on the bus, for instance.  My only complaint is that unlike AirSharing, the DropBox app does not allow users to open web archives.  But, it’s intuitive and flexible interface with the computer  makes it a definite must-have.

I really do wonder how I survived before the Pandora Radio application hit the app store.  High-quality streaming radio that plays only the music that you like — for free!  I really don’t need to say anything more.  I know you’re all pretty annoyed at the audio/video advertisements on the website, but there seem to be significantly fewer such ads on the app.  You can even get around the 40 hour/month listening limit if you alternate between a couple of different accounts!  Or, for a change, you can listen to the slightly less reliable (in my opinion) last.fm application.

I’ve used a variety of Bible applications in the past, but in my opinion, Pocket Bible by Laridian Electronic Publishing is by far the most intuitive, full-featured, and functional app out there.  If you’re looking for something snappier and easier to use than Mantis Bible Study, but something with a bit more substance than YouVersion Holy Bible, then Pocket Bible is the perfect Bible Study tool for you.  It’s got notes, highlighting, search tools, free commentaries, and all kinds of other goodies.  The super-slick reading interface makes it easy to quickly flip through a chapter or to switch between several open books.  I’m still trying to carry God’s Word in my heart, but I for one am glad that it’s now available in my pocket as well. ;-)

Anyone with access to a XENAPP server such as the University of Iowa’s virtualdesktop system (which allows users access to expensive licensed software such as Dreamweaver, Mathematica, and Adobe Photoshop), will know how excited I was to find the Citrix Receiver application in the app store.  After some reading on the Citrix website and a conversation with the University ITS staff, I was able to connect from my iPod touch.  I contacted the ITS department with a suggestion that they add a help page similar to this to their site so that everyone else at the University could take advantage of this awesome service.  C’mon fellow students… this means MATHEMATICA ON THE IPHONE!

Last time I checked (which was admittedly a long time ago), Dictionary.com was the ONLY free dictionary/thesaurus application which does not require an internet connection.  Plus, it doesn’t even have all the annoying advertisements that you will find on the official website!  And yes, reading the dictionary IS my idea of a good time.

MochaSoft RDP lite is a full-featured Windows Remote Desktop client.  I’m not sure why, but RDP feels significantly more responsive than the VNC lite client by the same company.  Using this in conjunction with a free Dynamic DNS service makes truly mobile computing a breeze.

I’m too cheap to buy a Kindle, and I’m still protesting the silly name and enormous size of the iPad.  But, I don’t need them! — because I’ve got Stanza.  The app is so full of features, and the interface is so clean that I really feel no need to try anything else.  Just to give you an idea of how fun Stanza is, I was able to read Middlemarch, by George Eliot ALL THE WAY THROUGH (for those of you who know me, finishing anything — much less a book — is a big deal for me).

When Happy Maau Studios released their MathRef Free, my engineering study was instantly made a WHOLE lot happier.  No longer was I stuck with memorizing (and forgetting) the same trigonometric identities, calculus tricks, and math definitions over and over again.  No longer did I have to walk around with (and lose) stacks of ill-organized notes.  If I can just manage not to lose my trusty iPod for another year, I think I’ll be set!

This concludes MY list of the most essential apps ever.  If anyone has any suggestions/additions I’d be happy to hear about them!

Building the josIpod (Part II)

These are SUPER FUN apps, but will waste all of your time if you let them.  In other words, the following have great entertainment value, but they probably won’t help you accomplish anything more than that. ;-)  Oh, and one more thing.  I HATE applications that have a crappy lite version.  So, if there’s a lite app in this list, it’s TOTALLY fun even without purchasing the “full” version.  So, without any further ado, here are, as promised:

Apps That Aren’t Useful But Get Used a Lot Anyway

P.S. They’re in no particular order.  Not even a normally distributed randomized ordering!

Anyone remember the good old days of Microsoft Entertainment Pack?  In my opinion, computer games were OODLES better when they were designed by graphically-limited, puzzle-loving computer nerds instead of by creepy psychologists who want to keep you playing whether a game is fun or not.  All that to say that Boxed In has a whole lot of levels, and kinda reminds me of Chip’s Challenge — which, in my opinion is enough to make it one of the best games ever.

And, speaking of classic game analogies, Catcha Mouse is basically a combination of the good old BSD Robots with Rodent’s Revenge. Only, instead of turning evil bots into deadly junk heaps or trying to turn a cat into cheese, you try to keep the mouse from escaping down several holes.  Pretty nifty.  You should try it out, folks!

Optime Checkers is most assuredly the best iPhone checkers game I have played — and believe you me, I have played just over TWO versions.  It’s got a great, clean interface and even an easy one-player mode for people who have friends who annoyingly ALWAYS beat them at checkers.  Anyone else have that problem?

Another uber-fun board-game port from Optime is Crack the Code.  I can’t tell you how many hours I’ve spent with my sister(s!) playing Mastermind.  All you strategy snobs out there, I KNOW it’s kind of pointless to play once you have the algorithm down, but it makes me feel so darn smart to be called a “Mastermind” that I can’t help playing it again and again.

Cube Runner is unique in that it is the ONLY 3D game on this list (aside from those other two 3D apps in this list).  You’re a little arrow flying around in a world of cubes.  The strategy is to not run into any of the cubes.  Believe it or not, you’ll find that it is anything but simple to survive this “simplistic” world.

After soundly beating me at the time-honored pen-and paper game, one of my friends from school kindly suggested that I download Doodle Dots to hone my then-nonexistent dot-boxing skills.  I haven’t gotten much better, but when I do, there’s gonna be a re-match!

Google Earth is really only on here because I still can’t get over how amazing it is to be able to stream 3D graphics over the internet TO A MOBILE DEVICE.  I don’t really use the app that much.  The technology’s just too cool to get ignored.

Now, here’s an app that some of you will be offended by.  At the very least, you’ll think that I’m morbid.  But, to me, iDie is actually one of the most useful apps on this list.  It reminds me that, considering average life expectancies, I’ve lived over a fourth of my life already — and only have got around 41 million MINUTES left to live.  So, I had better make each one count.

iDoodle2 lite is a full-featured drawing app that’s got transparency, multiple pencil sizes, and a playback feature.  A must-have for all you artists out there.

When I first saw Trace in the app store, I thought it was another of those annoying stick-figure games where the designer didn’t have the time, energy or talent to create attractive art work.  But, then I downloaded the game and started playing.  The concept is amazingly simple and yet it takes a surprising amount of strategy to finish the game’s fun & challenging levels:  You get to draw the path on which your character walks.  But, watch out!  There are baddies that will get you if you aren’t careful.

Logitech Touch Mouse is definitely a useful application — if you don’t already have an awesome bamboo digital writing tablet.  Aside from the obvious use of easy screen navigation and drawing, this app is great for annoying other users of your computer.  Just install, walk up behind them, and start moving their files to the trash or “editing” the e-mail they are working on.

As one of the top free apps for a while now, Tap Defense probably needs no introduction.  Battling demons with arrows, bombs, and bolts of lightning.  What’s not to love?

Sol Free Solitaire was the very first game I downloaded to my iPod.  Contrary to popular belief, solitaire is fun for people other than bosses and managers.  It also sports variants similar to FreeCell, and Spider solitaire.

Sheep Launcher FREEEE! is a game where you tap the sheep to make it go higher and higher.  It’s harder and more enjoyable than it sounds.  SO, instead of wasting your nights COUNTING sheep, you can now spend your evenings sending sheep into far reaches OUTER SPACE.

When Gandreas software came out with their amazing port of THE ORIGINAL dungeon-crawler Rogue, I immediately rushed to their website to see if they had a port of NetHack in the works.  They did, and I checked the app store almost daily until it was released.  For those of you who don’t know, I used to spend weeks at a time playing NetHack on our ancient Linux computer.  Now, I don’t HAVE weeks at a time to spend doing anything — but, it’s nice to know that if I ever did, I’ve got NetHack waiting for me on my iPod.

This is my last classic, folks.  I promise.  Light Bike FREE is a clone of the amazing Tron LightCycles arcade game — only in 3D (actually, the game is most similar to ArmageTron — only without the obstacles)!  The physics are completely unrealistic (you can make abrupt 90 degree turns while going light speed), but that’s part of what makes these kind of games fun.  Hey, if I wanted hyper-real graphics and true-to-life physics, I could get that OUTSIDE of a video game!

Labyrinth was the second game that I downloaded onto my iPod.  I can’t tell you how amazed I was when I could control the little silver ball by TILTING MY DEVICE.  As much fun as this game is, I’d have to say that I like the feel of the physical version better.  Too bad they don’t make iPhones with knobs on the side. ;-)

Knots is twister for the iPhone.  However, please make sure your screen is free from mud, pizza, ghostbuster slime, or any other unpleasantries before you ask someone else to play with you.  I can’t wait for the iPad version of this to come out — which will probably allow users to use their hands and feet instead of just their fingers!

Instead of linking to the app store page for Jungle Crash, I’m linking to a list of all the iPhone games from Donut Games.  They’re all so creative, challenging, and instantly playable that it’s hard to pick out just one.  Check ‘em out, peoples.

Last and certainly not least is Jelly Car.  I guess the only way to describe this game is that you drive a car made out of jelly — in a world made out of jelly.  It’s really a fascinating idea — since players have to come up with strategies they have never used in other games.  For instance, you can squeeze your car through a small space to make it slurp out at a faster speed than it was going before.  I wish I had thought of it.

Alrighty!  I hope you’ve all enjoyed this little list.  If not, maybe you can come again soon and have a look at the upcoming part III (Apps That I Cannot Live Without).

Building the josIpod (Part I)

Hey folks, I’m taking a short break from my studies.  With the advent of the bigger and… mostly just bigger iPod for giants, I thought it would be a good idea to do a little series on some of the normal-sized applications that have made Josiah’s well-used first-generation iPod touch (aka The josIpod) the awesomely fun and still-totally-useful device that it is.  So, without any further ado, here is Part 1, alternately titled

Apps That I’d Really Like To Use If They Actually Worked


Instapaper is a pretty useful little tool — if the only information you need to download for offline viewing is contained in a simple HTML webpage.  The interface is a little clunky (you have to navigate to the page you want to download in Safari, then click a bookmark that executes some Javascript, then navigate to the application, and click the download button), but it’s usable.  The main reason I don’t use this application all the time is that it does not allow you to download PDF files, raw images, pages with frames, or anything else that is not contained in a simple HTML page.  I’m not sure why they didn’t just write a simple in-application browser with a “save this page” button…

Quicken is the site that I use to keep track of all my financial transactions.  Despite it’s several bugs, the site is able to automatically connect with my bank, and provides a quick and secure way to keep up an electronic “checkbook.”  The app claims to be an optimized interface to the site, but it has far too few features to be really usable.  For instance, it cannot edit previous entries.

Remember the Milk was one of my absolute favorite “To-Do” list services on the whole Internet.  You can categorize items, set up reminders, and it will save all your previous entries.  It WAS among my favorites, that is, until the company came out with one of the most infuriating applications in the app store.  It’s a close call, but I think it’s almost a match for Stephen Wolfram’s outrageous $50.00 interface to a website which can be accessed for free via Safari.  Why, instead of simply putting a price-tag on their application, RTM allows users to download the app from iTunes for no charge — and THEN requires them to pay a $25.00 fee to enable this very UN-free application.  Even that wouldn’t be so bad if users weren’t made to pay that fee again and again and again EVERY SINGLE YEAR.

For those of you who are wondering why there are only three applications on this list instead of bazillions, just be grateful that I don’t have time to list ALL of the underachieving applications I have downloaded and then immediately deleted.

For those of you who are looking for something a bit more positive, tune in next time for Part 2 (Apps That Aren’t Useful But Get Used a Lot Anyway)!

Get a FREE Twist Tie Animal!

So, here’s the beef, folks.  Check out the following actual traffic data for this blog:

chart

dogPretty pathetic, huh?  We here at Josiahland.com sure think so.  And, so we’ve decided that it’s time for something new and exciting with the site.  But, what that something is, we want YOU to decide. For each qualifying submission, we’re GIVING AWAY one of our awesome custom Twist Tie Animals (See example to the right).  Let me tell you folks, these things will TOTALLY make your life WAY BETTER IN EVERY WAY.

To qualify, a comment must be posted on this post before next Sunday (August 23rd).  If you’d like a specific animal, please include that information.

IMPORTANT:

If you would like to receive the actual twist-tie animal via mail (as opposed to a link to a digital photo), please provide me with the following information:

  1. Your mailing address.
  2. A comment suggesting something new and exciting to add to or change about Josiahland.com.  This must be something that is actually possible for a time-pressed college student like myself to implement.