![[image: xlightoff in action]](shot.png)
This is XLightOff, a little game under X.
Easy to get in hands, not so easy to solve.
It is in the public domain.
I dedicate it to my angel.
Enjoy your life.
(Note: I first played this game under Windows, it was flash stuff or something like that. I saw variations of this game on mobile phones too. If you know who did the first implementation, contact me.)
Note (Mon, 24 Oct 2005): I received an email from Bruce Ediger (bedigerXX@sdf.lonestar.org) (without the XX) this morning, about the origin of the game:
About the origin of "xlightoff"... I first saw this game in the early 90s, a NeXTStep implementation by Edmund Ronald, who was eronaldXX@cnam.cnam.fr (without the XX) at the time. He said something like: -------------- Quinto Quinto is a game. The board is a 5*5 array of buttons, pressing one toggles its' state and that of its 4 neighbors. The aim of the game is to highlight all the buttons. My friend John Horton Conway, who knows some mathematics, took a few hours to solve this back in the early eighties. Other people tend to take slightly longer. The source code is placed in the public domain, however I request that the icon not be used for anything else as it is my own iconic signature. My adress is Edmund Ronald, XX XX email: XX If you like this program, send me a disquette with your favorite game (NeXT, Mac or PC!) Enjoy. Edmund. -------------- I implemented it in Tcl/Tk around 1998: http://www.users.qwest.net/~eballen1/Quinto Looks like Edmund Ronald still puts out versions of it: http://lists.squeakfoundation.org/pipermail/squeak-dev/2002-August/043136.html His version starts with every button one color, and then you try to get them all the other color. I bet you could write him about the origins of the game. -- Bruce Ediger XX eballen1XX@qwest.net (without XX)
Note (Tue, 25 Oct 2005): I contacted Edmund Ronald, here is his reply:
As far as I know I was the first software implementor of this game, but there were hardware versions of it around long ago. I have myself written versions in quite a few computer languages, including Smalltalk and PocketBasic. My friend Conway took an afternoon to analyze it completely, and there have been a few doctoral students who did the same in the time it usually takes to do a thesis. Dr. Edmund Ronald
Once downloaded, simply unzip/untar the archive, go into the created directory, and run "make". It should produce a "xlightoff" file. Then, simply run "./xlightoff" and there you are. It must be played with the mouse. Of course, you must run an X server to get something. It should be easy to use.
Starting with version 1.1, there is a solver included! (In the game, click "solve" to see the shortest solution, click again to clear it.)
A nice game is to create your own solver and send it to me so I can include it in future releases.
Here are the current available solver with their creator, in chronological order of availability (they are present in the tar.gz archive) :
solve_james.c by
James Williams
(received Wed, 26 Dec 2001),
solve_chupcko.c by
Chupcko
(received Mon, 7 Jan 2002),
solve_sed.c by
Sed
(received Tue, 8 Jan 2002),
The default one used by the game is the Chupcko's one, for it's the smallest in file size and the prettiest (In My Humble Opinion).
There are some results we may find about this game.
If a solution exists, there is a minimal solution of less than 25 steps.
Two lemmas have to be noticed.
The first one is that two steps can be done in any order. Imagine no common light, it is then obvious that the order does not matter (all the lights will change their state). Imagine now some light in common, then it will be accessed twice and won't change its state, so once again, ordre does not matter.
The second one is that to play a move twice is the same as play it none. It is very easy to see too.
So the theorem can be proved as follow.
Imagine the minimal solution is longer than 25 steps. Then a move must appear at least twice (there is only 25 lights on the board, so more than 25 steps means to click a light at least twice). If they are not following each other in the solution, you can move one to get close to the other (according to the first lemma used several times) then remove the two moves (according to the second lemma). So you come with a shorter solution, which is impossible because the minimal solution can't be shorted. So the solution is in less than 25 steps.
Some lightings of the board don't have a solution.
Some lights can't have their state changed without affecting at least one other light. I did a little program to test all the possible on/off switching ways (2^25) and it says no for some lights. The only ones that can be changed without affecting the other ones are the one with a 'x' in the following.
o o o o o o x o x o o o x o o o x o x o o o o o o
Unless my program is wrong (I should prove it to be correct), this means a general solution is not possible. The following initial position can't be cleared:
x o o o o o o o o o o o o o o o o o o o o o o o o
If it could, this means we can toggle the 'x' into a 'o', which means change its light's state without changing the one of the other lights, which is impossible. This concludes the proof.
GLighOff with GTK
Paolo Borelli implemented a version from scratch using
the GTK toolkit. Very nice. Give it a try.
LightsOff for Mac OS X
Anthony Loeppert implemented a version from scratch
for Mac OS X. Very nice colors.
Contact: sed@free.fr
Last update: Mon, 14 Apr 2008 12:30:17 +0200
Powered by a human brain, best viewed with your eyes (or your fingers if you are blind).