XLightoff - Chupcko's solution

Hello,
 
Sorry for very rich explanation for solve.
This is some precisely explanation, but i dont have time for detail (at
this moment :( )
 
First, let make label of oll light on this way:
 
A B C B A
C D C D C
B B D B B
C D C D C
A B C B A
 
My lite theorem is next:
Let a is count of light of type A
Let b is count of light of type B
Let c is count of light of type C
Let d is count of light of type D (not used, because ...)
Situation is possible to solve if a%2+b%2+c%2 equal 0 or 3.
 
Lite Prof (based on induction):
If some position is possible to solve then a%2+b%2+c%2 is 0 or 3, and if
you click on some light you preserve this equation.
On example if click on some corner (type A) you change a,b,c by 1 (add, or
sub), etc etc....
 
On this way , you can calculate possible or impossible situation of game.
 
Next: strategion of solve all possible situation:
 
For example game board is:
 
00 01 02 03 04
10 11 12 13 14
20 21 22 23 24
30 31 32 33 34
40 41 42 43 44
 
My strategy is simple:
if light 00 is on, then click on 10
if light 01 is on, then click on 11
if light 02 is on, then click on 12
if light 03 is on, then click on 13
if light 04 is on, then click on 14
 
OK, now first row (00,01,02,03,04) is all off
 
Repeat this for row 10,...,14 and 20,...,24 and 30,...,34
At end you can get some of next situations (8 of 32 with
(a%2+b%2+c%2)%3=0)
00000 ~ 000 00 (called 0)
00111 ~ 001 11 (called 1)
01010 ~ 010 10 (called 2)
01101 ~ 011 01 (called 3)
10001 ~ 100 01 (called 4)
10110 ~ 101 10 (called 5)
11011 ~ 110 11 (called 6)
11100 ~ 111 00 (called 7)
 
Next, is at moment black magic:
 
At empty board, i click all combination (00000, ... , 11111) on first row
(10,...,14)
and reduce this situation to one from 40,...,44.
 
This is magic table s in my algorithm.
 
Now algorithm:
 
from some situation I calcuded row 40,...,44
this is r in algorithm.
 
For this situation I use click from table s for this r (some of 4)
and apply procedure for reduction.
 
For all possible situation exist 4 different ? solves.

CHUPCKO

#######################################

  Goran "CHUPCKO" Lazic
  mailto:chupcko@galeb.etf.bg.ac.yu
  mailto:chupcko@turing.mi.sanu.ac.yu
  http://alas.matf.bg.ac.yu/~chupcko/

#######################################

The algorithm to solve XLightOff

1. Let the light go down.
   You do this by clicking under any light which is on. You start with the first line, then you clear the second line, then the third one, then the fourth.
   You will now have lights on only to the last line.
   Due to Chupcko's theorem, we can only have 8 possibilities for this last line for a solvable game.
2. Let the light get back again.
   By clicking some lights in the first line, and then let them down again with the same method as above, you can light everything off.
   This is the magic table :

   0 00 0 00 0 ~ 00000 01110 10101 11011
   1 00 1 11 7 ~ 00010 01100 10111 11001
   2 01 0 10 2 ~ 00111 01001 10010 11100
   3 01 1 01 5 ~ 00101 01011 10000 11110
   4 10 0 01 1 ~ 00011 01101 10110 11000
   5 10 1 10 6 ~ 00001 01111 10100 11010
   6 11 0 11 3 ~ 00100 01010 10001 11111
   7 11 1 00 4 ~ 00110 01000 10011 11101
   

   that you can see in the source file solve_chupcko.c.
   You must read only the 0 and the 1. For example, let's look the fourth line.

   3 01 1 01 5 ~ 00101 01011 10000 11110
   

   We have 01101, which means that after doing step 1 of the algorithm, lights 2, 3 and 5 of the fifth line are on. So now, you have four possible moves, 00101, 01011, 10000 and 11110. Let's take the last one. It means you will click the lights 1, 2, 3 and 4 of the first line, then do the first step again, and magically, all the lights will be off.
   How did Chupcko find those four possible moves ? He says nothing about it, but I think he tried all possible clicks on the first line with an empty board, then applied the step 1 of his algorithm, and watched the lighting of the last line, which makes 2^N cases where I needed a 2^(N*N) test to know something about this game. This is 2^N faster than my method. The question is now :is a there a faster way ?

   Here you are !

   The main problem here was to find this theorem, which makes everything much simpler. How many "real" problems could be easier to solve with such theorems, huh ? What about cryptology, chess playing, and the like ? Maybe some theorems already exist that reduce the complexity of a problem by a 2^N factor, which we don't know the existence. A lot a mathematicians work for a state or another one...

Last edited : Mon Jan 14 21:12:47 CET 2002