< 3 hours and 4 seconds

So I’ve been absent a while. My course started about 6 weeks ago, and I’ve been busy working away at the assignments. Acing them, mostly due to my previous experience, and partly due to my copious free time. In spite of the introductory nature of the subject, I have been learning.
Learning mostly about how various techniques, methods and algorithms are so well documented out in the internet, if one just takes a little time to search. It’s perfect for my own abilities to be able to say, “I need to know how to do this” and just go find out how.
Now, the latest assignment had, as part of its requirements, the goal of writing a solver for sudoku puzzles. And that taught me all about the notion of an exact cover and how it’s useful for solving sudoku puzzles. Since I suspect none of my readers knows what an exact cover is (I didn’t at first either), I’ll briefly give an example.
Suppose you’re organizing a bake sale, and you have 10 potential contributors, each of which will want to bring her/his two or three best baked goods. You want every imaginable kind available, but no repeats – that is, every possible baked good shows up once and no baked good shows up twice. How do you choose who to ask to bring baked goods? Your answer, if there is one, is what is called in mathematics an exact cover.
Now I suppose that you, my dear reader, are curious about where I’m going with all this. Well, two Christmases ago, I received a puzzle as a gift. Ok, make that a fiendishly hard puzzle as a gift. I worked on it, off and on, for a while, before setting it aside. It involved attempting to construct a 5x5x5 cube, perfectly filled, using 25 identically shaped pentominoes (think dominoes, but with 5 cubes instead of 2).
Well last night, during a common bout of insomnia, it occurred to me that that puzzle is perfect for solving using the techniques I learned for the sudoku assignment. In other words, I had a programming project ahead of me, and one that I was quite happily itching to do.
Less than three hours later, my program was done. No, I didn’t construct the whole thing from scratch in that time, I used parts of code from the sudoku assignment that I’d already put together for that purpose. Still, with under three hours of effort devoted solely to solving this puzzle, I had a working program.
I ran the program.
Less than 4 seconds later, I had an answer.

About twio

In accepting Doubt, I find Certainty
This entry was posted in Computers, Mathematics, Personal, Programming and tagged , , . Bookmark the permalink.

One Response to < 3 hours and 4 seconds

  1. Matthew says:

    Of course, what really sucks about computer science is that all these well documented algorithms are patented – and the papers describing them don’t have to say this. Of course if you struggle with it for weeks and then come up with the same solution the last guy did you still violate the patent…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s