I love puzzle games. I especially like to write programs to solve puzzles. I have recently been obsessed with "pentominoes", and it's not the first time. I was introduced to the puzzle in high school and wrote a program to find solutions. It was slow, but I found some ways to optimise it. By the end, it was taking less than an hour to solve puzzles.
Years later I read a paper by Donald Knuth called "Dancing Links" that used pentominoes as an example and expanded my interest accordingly. Now I've rewritten my program in the old style but slightly improved, as well as implemented Knuth's method, which finds all solutions rather than just one. It counts up over 500 solutions in under 3 seconds. Knuth's method is also applicable to variations on the theme, including cubes, triangles and sticks.
And what is the point of all this? Don't know, really. It just seems like fun to me.
Mokalus of Borg
PS - That probably makes me weird.
PPS - I'm okay with that.
No comments:
Post a Comment