<?xml version="1.0" encoding="windows-1252"?>
<node id="940808" title="Re^2: Lights out puzzle" created="2011-11-30 05:06:58" updated="2011-11-30 05:06:58">
<type id="11">
note</type>
<author id="832495">
choroba</author>
<data>
<field name="doctext">
Here are some comments on how it works:&lt;br&gt;
The code clears all the lines except for the last one (&lt;c&gt;clean&lt;/c&gt;) the simple way: if there is a light, click underneath. The last line (or, better to say, broken line, i.e. the last line plus the remaining half of the previous one) is then solved half-randomly. At the beginning, I cache how clicking on the top line influences the last line, but only for one click on the line (i.e. I only know what the last line will be after having one light lit). Therefore, I have to click randomly until I get a cached position that I can solve. This works well for size 14, but the time doubles for each +2 in size, so size 20 is already too slow. Caching more positions could be added easily (like clicking two times), but I am not sure how much time it would take to cache all possible combinations on the first line.&lt;br&gt;
Because the order of clicks is not important, I keep a separate map of the board with 0 for the even clicks and 1 for the odd ones. This separate board is the output of the program.</field>
<field name="root_node">
940327</field>
<field name="parent_node">
940423</field>
</data>
</node>
