Geek alert. Flying back from the states, I came across a contest called "Crossing Capitals" in the back of Games Magazine. The object is to take the 50 US state capitals, plus all of the Canadian capitals, and fit as many as possible into a 19 by 19 grid, crossword puzzle style. This is a regular sort of contest they do, called a "stuffer" contest.

This sounded like a fun thing to write a program to solve, so I set to the task, and was soon generating some pretty good results. I started running it overnight at home, and pretty much constantly at work -- I'd estimate a good eight weeks of total computing time. I'm not sure how many million combinations were tried, but it was a lot. I also did a lot of fine tuning of the algorithm.

The deadline is now passed -- here are the results of the effort:

M

O

N

T

P

E

L

I

E

R

C

O

N

C

O

R

D

C

A

E

O

L

Y

M

P

I

A

H

A

L

I

F

A

X

S

L

T

E

B

M

U

T

R

E

N

T

O

N

I

T

O

R

O

N

T

O

M

P

G

I

I

B

P

I

E

R

R

E

C

H

A

R

L

E

S

T

O

N

I

Q

K

H

T

A

E

E

A

L

B

A

N

Y

A

A

L

N

S

L

A

R

A

U

S

T

I

N

C

O

L

U

M

B

U

S

L

N

I

B

H

I

G

B

O

S

T

O

N

I

E

S

T

P

A

U

L

T

A

G

S

S

Y

A

S

T

R

T

M

E

N

S

T

D

E

N

V

E

R

J

A

N

T

A

A

T

G

D

O

V

E

R

N

A

L

P

H

O

E

N

I

X

H

C

E

F

E

W

N

N

K

E

D

M

O

N

T

O

N

M

A

D

I

S

O

N

That's thirty-four capitals. The tie breaker is the total count of letters used; my total is 243.

Unfortunately, I found a forum for people who do this sort of thing all the time, and it looks like at least three people managed to fit in 35 capitals. At least one did it by hand, too, without computer help! I would have thought that everyone in contention to win would have done it by program -- interesting that brains and computers are so evenly matched.