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.

## < 3 hours and 4 seconds

Advertisements

This entry was posted in Computers, Mathematics, Personal, Programming and tagged Computers, math, Personal. Bookmark the permalink.

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…