Python Performance Tuning

Posted on March 3, 2009 by MXH

Having just built a solver for KenKen puzzles, this is a good opportunity to take a look at performance tuning in Python. Today we’ll look at some basic instrumentation, and begin searching for bottlenecks in the solver.

Continue reading →

Posted in Projects, Python | Comments Off

Solver for KenKen puzzles (Search)

Posted on March 2, 2009 by MXH

Today we complete the first version of our solver for KenKen puzzles. Previously we’ve defined constraint classes, input/output functions, and data structures; all that remains is to write the search and propagation code. Once again, this is all based on Norvig’s Sudoku solver.

Continue reading →

Posted in Projects, Python | Comments Off

Taste

Posted on March 1, 2009 by MXH

Editorial Note: We’ll be continuing with daily posts throughout March. The rules remain the same: Contentful posts guaranteed on Fridays, luck-of-the-draw the other six days of the week. Today, for instance, you get musings on the non-transitivity of taste.

Personal taste is a funny thing. “De gustibus non disputandum est”, as the Latin has it: In matters of taste, debate is pointless. It seems to me that one can’t even apply logic to one’s own tastes, let alone anyone else’s.

Continue reading →

Posted in Jack Handy | Comments Off

Solver for KenKen puzzles (Representation)

Posted on February 27, 2009 by MXH

One of the biggest differences between KenKen puzzles and Sudoku puzzles is that the former are harder to represent compactly. Sudoku puzzles can be represented as a simple string of numbers, but the 2-dimensional cages of KenKen puzzles seem to require a more vebose representation. Fortunately, such a representation needn’t be complicated.

Continue reading →

Posted in Projects, Python | Comments Off

Solver for KenKen puzzles (Constraints)

Posted on February 26, 2009 by MXH

Today I’m going to show the Constraint implementation for a KenKen solver I’m building. This code will cover all the rules of the KenKen game, and will shortly be used in a constraint propogation and search algorithm. It contains several inefficiencies, which will be dealt with later.

Continue reading →

Posted in Projects, Python | Comments Off

Solver for KenKen puzzles (Constraint design)

Posted on February 25, 2009 by MXH

Following up on yesterday’s post, I’d like to get started on the construction of a solver for KenKen puzzles, using the same basic constraint-propogation-and-search approach that Norvig used in his Sudoku solver. I’m going to begin with a discussion of the role of constraints in the KenKen solver.

Continue reading →

Posted in Projects, Python | Comments Off

KenKen vs. Sudoku

Posted on February 24, 2009 by MXH

According to Slate, there’s a push afoot to popularize a Sudoku-like game named KenKen. Since it’s already been demonstrated that Sudoku falls easily to a little programming, I thought it would be interesting to (informally) compare and contrast the two games, with an eye to developing a solver for KenKen.

Continue reading →

Posted in Projects | Comments Off

Details Matter

Posted on February 23, 2009 by MXH

I was looking at Norvig’s Sudoku solver the other day, and suddenly understood a design choice that had previously struck me as bizarre. I think it’s a neat example of how small, seemingly arbitrary things can make your programming either easier or harder, depending on whether or not you get them right.

Continue reading →

Posted in Python | Comments Off

Skiing

Posted on February 22, 2009 by MXH

I am not a good skier. I can look ok on the majority of intermediate slopes, and make my way down diamonds. I’ve never been on a double-diamond in my life. I have a lot to learn. However, I have improved over the years (yes, years: I went a decade between trips to the mountains) and would like to share a few tips that would have made my life easier if I’d known them when I started.

Continue reading →

Posted in Jack Handy | Comments Off

Antisocial Product Idea

Posted on February 21, 2009 by MXH

Why, oh why, doesn’t anyone make Bear Treats? (These don’t count.) The box copy practically writes itself:

  • Three flavors: Salmon, deer, and refrigerator medley
  • Delicious, tasty aroma (travels hundreds of yards)
  • Loved by both cubs and adults
  • Irresistible – Bears can’t eat just one
Posted in Jack Handy | Comments Off