CS 227 Project

I was watching Star Wars Episode IV the other day and came across something interesting. When R2D2 is babbling about he needs to go to his owner Obi-Wan Kenobi, C3P0 says something like, “I don’t know what he’s talking about. Our last owner was Captan Antilles.” That’s right, they used to belong to the infamous Wedge Antilles! Another interesting fact – the actor that played Wedge Antilles, Peter Lawson, is Ewan Macgregor’s uncle. Random facts.

For my CS 227 class, which is basically an algorithms class for Artificial Intelligence, my most recent project was writing a program that, given a blank crossword puzzle, and a dictionary file, fills it in with valid words. It’s a pretty interesting problem, and it was a lot of work. Anyway, although it’s interesting to no one except me, I thought I’d post some samples of what the program came up with.

Pattern 1

		A	A	A
	d	r	i	b
k	i	d	d	e
a	r	e	a
y	e	n

The first few times I ran it, I didn’t use any randomness, so it checked the dictionary in order (by the way, the dictionary I used was the standard UNIX one, on /usr/share/lib/dict/words), so the non random ones have a lot of those early words, like AAA.

		s	p	a
	s	p	i	t
v	e	r	s	e
i	r	i	s
z	a	g

So here’s another solution, this time using randomness. This puzzle made me happy because it has both the words “spit” and “piss.” Liquid coming out of both ends.

Pattern 2

			A	A	A
		o	r	b	i	t
	c	r	e	e	d	a	l
s	u	d	s		a	n	e	w
a	r	e				g	a	r
d	i	r	t		d	e	f	y
	a	l	i	m	o	n	y
		y	e	a	s	t
			d	y	e

What an interesting puzzle! As you can imagine, as they get bigger, it gets a heck of a lot more complicated. Some of these words seem strange, but they’re in the UNIX dictionary. Again, this is non-random, so you see the AAA in the beginning.

			w	e	t
		b	e	f	o	g
	H	a	r	t	m	a	n
s	i	r	e		b	l	o	w
i	n	k				l	i	e
b	e	e	f		r	e	s	t
	s	e	i	z	u	r	e
		p	e	o	n	y
			f	o	e

The random version. Again, so many interesting words!

Pattern 3

w

a

d

i

A

A

A

i

b

i

d

a

l

u

m

a

b

c

m

a

c

e

s

t

e

p

r

e

t

b

l

o

b

p

o

t

a

t

o

o

r

i

e

n

t

i

o

n

n

a

b

N

e

g

r

o

g

e

c

k

o

I

k

e

h

e

n

H

e

l

g

a

b

e

i

g

e

a

b

c

M

a

e

b

i

a

n

c

o

a

d

r

i

f

t

a

b

l

e

c

a

b

i

d

l

e

n

e

a

t

o

n

e

l

e

e

r

e

x

i

t

a

i

l

y

a

w

n

So here is pattern 3, without randomness. Again, you see AAA. The interesting thing, though, is that the first word considered is 1 Across. And it always starts in alphabetical order. This means that there are very few words that 1 Across can be in this puzzle – it had to go all the way to wadi. I found that interesting. Also interesting is when there are capitalized words. You just get interesting words like Ike and Helga.

N

A

S

A

a

r

m

g

a

w

k

A

l

a

n

v

i

i

a

m

e

n

S

a

n

d

a

b

c

r

o

l

e

A

n

d

r

e

i

r

a

n

k

l

e

e

l

l

o

d

e

s

e

p

a

l

d

r

o

n

e

e

a

r

h

i

t

c

r

o

w

d

S

a

m

b

a

h

i

s

D

e

c

s

h

r

i

e

k

e

x

c

u

s

e

l

e

a

n

a

l

b

u

g

l

y

a

i

r

y

t

o

r

s

l

o

e

p

r

e

y

e

t

a

e

y

e

d

This puzzle is just crazy interesting. The most interesting thing is how in the top left and bottom right corners, nearly all the words both up and down are the same. It’s interesting. But at the other corners, you don’t see that. Again, the algorithms picks words somewhat at random, so that you see this is fascinating. This puzzle also includes the words ohm, amen, and Sex. Cool puzzle.

Pattern 4

V

e

d

a

D

e

e

a

b

e

d

e

p

i

c

e

‘

s

c

l

a

y

d

i

s

c

n

e

t

c

a

v

e

a

c

c

e

l

e

r

o

m

e

t

e

r

l

a

b

p

a

l

D

e

n

e

b

d

e

b

a

r

e

‘

e

r

r

a

t

a

e

s

t

o

p

t

o

t

e

m

m

a

d

P

a

m

a

c

c

e

l

e

r

o

m

e

t

e

r

b

l

a

t

b

u

n

t

i

d

e

e

a

s

e

a

b

c

e

d

g

e

d

y

e

r

r

y

e

r

e

e

d

This puzzle is great. The difficulty in the puzzle lies in the fact that there are 4 slots, 2 up and 2 down, that span the entire puzzle. The interesting thing about it is that in this puzzle, all four slots are filled by the same word – accelerometer. That is just so cool. Again, there are the same words on the top left corner and bottom right. Also the top center and left center seem to kind of parallel each other. Fascinating.

m

o

s

t

c

a

b

s

l

a

b

o

‘

e

r

r

u

e

t

o

m

e

s

e

r

a

e

t

a

a

c

m

e

t

r

a

n

s

p

o

s

i

t

i

o

n

s

e

e

t

i

e

e

l

e

c

t

i

s

s

u

e

t

o

r

r

m

a

r

t

a

g

a

i

n

m

a

g

n

a

p

e

e

w

i

n

s

t

a

t

e

s

m

a

n

l

i

k

e

l

o

c

i

t

a

r

i

b

i

d

a

m

m

o

o

u

t

k

i

n

g

b

e

e

n

p

l

y

e

d

g

e

This time I randomized it, so you don’t get four accelerometers. But you do get two transpositions and two statesmanlikes. That fascinates me. That for some reason, it picks words that have some symmetry to them, so they fit together in the puzzle. Another interesting result is that the top right down wordsr are like the bottom left across words! How the heck does that happen? Also, the word pee occurs in this puzzle. It’s great.

So, you just got to see what dominated my life for 2 weeks. I like it.