Conversations w/ Al Geist

My e-mail to him:

Date: Fri, 06 Dec 1996 14:15:38 -0400
To: gst@ornl.gov
From: Ken Barr
Subject: Lights Out

Wow! I love your Light's Out Applet! Due to the fact that it knows the minimum number of moves required, I assume that you have created a algorithm to solve the puzzle. Would you please share the source code for this applet, or just explain how you have the computer solve the puzzle? Thanks!

He replies...

Date: Sat, 7 Dec 1996 19:41:43 -0500 (EST)
From: Al Geist
To: kbarr@mit.edu
Subject: Re: Lights Out

>Wow! I love your Light's Out Applet!

Thanks.

>Would you please share the source code for this applet,
>or just explain how you have the computer solve the puzzle?

Well that would take all the fun out of it Ken. But let me give you a sketch of an algorithm that solves the puzzle (but doesn't always find the minimum solution -- a much more complicated algorithm. (-: )

1. Any starting pattern can be reduced (chased) to a pattern of lights only on the bottom row by pressing the button below any "on" light. (Note top row of buttons are never pressed in this step)

2. Of all the possible patterns on the bottom row, only 7 unique ones can be solved. How to find them:
a. press a pattern of buttons on the top row chase it to the bottom.
b. record this relationship in a table.

3. To solve puzzle. Do 1) note bottom pattern
Then match against bottom pattern in your table
and press the corresponding buttons on the top row.
Now chase them down and the poof the bottom row will be cleared.

Aside: you can remove all the duplicate button presses but the solution will still not be minimum for all cases.

enjoy!
Al

A few additional comments...

This is obviously a reply to a letter I had sent him, but I can't find the full text. The quotes give you an idea of what I was up to, though...

Date: Sun, 8 Dec 1996 10:51:52 -0500 (EST)
From: Al Geist
To: kbarr@mit.edu
Subject: Re: Lights Out

>we could use a brute force method to solve the first 50 puzzles for
>which we -know- the minimum # of moves.

You can know the minimum # of moves for "ANY" puzzle by just setting it up on my game and seeing how many moves it says it takes. (We have proven the algorithm we use gives the minimum.)

And if you want to see what the minimum solution is all you have to do is "solve" the pattern (in any number of steps) and press "help" button on the gameboard and the game will play (show you) the minimum step solution.

>Just have the computer toggle lights randomly
>Inefficient, but would it work?

Yes it would work, but maybe not in your lifetime! While working on our proof for the fast minimum algorithm. we brute force solved "ALL" the minimum solutions. We would still be waiting a year later if we had coded the brute force to randomly toggle the lights. We only kept this solution file around for about a week because it was so large. (-: To see how fast our solution algorithm is - realize that it recalculates the minimum solution from scratch each time you change the pattern in setup. And it is written all in Java, which is not particularly swift at calculation.

Here are some interesting facts about the game we found while doing a mathematical study of it.

a. What is the longest minimum solution?
15
b. Is every possible start pattern solveable?
no, only 25% of them can be driven to lightsout
c. Are minimum solutions unique?
no, there can be up to (but not more than) 4 different minimum solutions
d. How many puzzles are solveable?
Well you can figure this out given (b) and the fact that the number of patterns possible can be represented by a 25 bit integer.

So what is the URL of your "LightsOut" page?

enjoy!
Al

And...

Date: Mon, 9 Dec 1996 08:36:24 -0500 (EST)
From: Al Geist
To: kbarr@mit.edu
Subject: Suggestions for your Lightsout page

Hi Ken, I would suggest that you describe the format you want people to send their solutions to you. Otherwise they may pick a different button numbering scheme than you.

This will also be useful when they look at your solutions. And here is my interesting fact of the day about LightsOut.

"The order you press the buttons is unimportant to a solution."

Try it. For example problem 10 will lights out if you press
1 2 4 5 7 8 9

Also, if you want solutions to #22 and #24 I'm will send them to you, but you will have to send me the start pattern of the lights Because I don't own the game, I don't know what #22 and #24 are.

enjoy!
Al