点灯游戏的解法讨论

noski

前两天在最少步版，有人问怎么下载点灯游戏，我就贴出了下面这个：
http://files2.17173.com/flash/4062.swf

这是一个10*10的点灯游戏，以前还在小游戏机上玩过5*5的，目的就是把方阵中的“灯”全部点亮。
规则是：点击一个小方格时，这个方格以及上下左右与之相邻的4个方格，灯的亮灭状态发生变化。
希望大家讨论讨论这类游戏的解法的数学规律：

1. 如果初始状态灯是全灭的：
对于n*n的方阵，有什么固定的解法吗？
对于m*n的方阵，它与m*m或n*n方阵有什么关系？

2. 如果初始状态灯是随机点亮的：
怎样才能以不变应万变？点灯的策略有什么变化？
有所谓的“最少步解法”和“最乱状态”吗？



说说我的两个想法：
当从上而下点灯时，最后一行灯的状态只与第一行灯的状态和点击有关；
随机亮灯时，先从下至上全部灭掉，再从上至下全部打开。

superacid

可以编程搜索，就1024种情况嘛

migl

（题外话）
找个显示步数（ 点的次数 ）的吧。还能顺便玩玩。

lulijie

我就10*10方阵，谈谈最少步编程解题思路：
   1. 建立坐标，F(n,m)表示第n行第m列的灯的状态，0表示灭，1表示亮。
   2. 用 S(n,m)表示对 第n行第m列的灯是否进行点灯操作，0表示不操作，1表示操作1次。（最少步数，不可能对同一个灯进行2次以上的操作，因为点2次和不点对整个灯的状态是没有影响）。
  3. 根据所有灯的初始状态，设置F(n,m)的初始值。
  4. 先对第一行 S(1,m)的值进行穷举( 比如采用10位2进制数，从0000000000开始逐渐穷举到1111111111)，计算F(1,m)=  F(1,m)+S(1,m)+S(1,m+1)+S(1,m-1)。这样为了使第一行的F(1,m)都等于1，S(2,m)的值唯一确定，S(2,m)确定后，F(2,m)的值也确定，接着确定S(3,m)......
        最后若F(10,m)都等于1，那么就得到点灯的整个方案：
        S(1,1)    S(1,2)    S(1,3)    S(1,4)    S(1,5)    S(1,6)    S(1,7)     S(1,8)   S(1,9)    S(1,10)  
        S(2,1)    S(2,2)    S(2,3)    S(2,4)    S(2,5)    S(2,6)    S(2,7)    S(2,8)    S(2,9)    S(2,10)  
        S(3,1)    S(3,2)    S(3,3)    S(3,4)    S(3,5)    S(3,6)    S(3,7)    S(3,8)    S(3,9)    S(3,10)  
        S(4,1)    S(4,2)    S(4,3)    S(4,4)    S(4,5)    S(4,6)    S(4,7)    S(4,8)    S(4,9)    S(4,10)  
        S(5,1)    S(5,2)    S(5,3)    S(5,4)    S(5,5)    S(5,6)    S(5,7)    S(5,8)    S(5,9)    S(5,10)  
        S(6,1)    S(6,2)    S(6,3)    S(6,4)    S(6,5)    S(6,6)    S(6,7)    S(6,8)    S(6,9)    S(6,10)  
        S(7,1)    S(7,2)    S(7,3)    S(7,4)    S(7,5)    S(7,6)    S(7,7)    S(7,8)    S(7,9)    S(7,10)  
        S(8,1)    S(8,2)    S(8,3)    S(8,4)    S(8,5)    S(8,6)    S(8,7)    S(8,8)    S(8,9)    S(8,10)  
        S(9,1)    S(9,2)    S(9,3)    S(9,4)    S(9,5)    S(9,6)    S(9,7)    S(9,8)    S(9,9)    S(9,10)  
        S(10,1)  S(10,2)  S(10,3)  S(10,4)  S(10,5)  S(10,6)  S(10,7)  S(10,8)  S(10,9)  S(10,10)

Cielo

小时候在游戏机上玩过5x5的，当时是琢磨出了一个解决方法的（虽然不知道道理是什么），现在反倒不记得了……

sokoban

就是解一个线性方程组，可以参考这个：

http://mathworld.wolfram.com/LightsOutPuzzle.html

lulijie

便于记忆的一般解法：
    从最下面开始逐层往上将每行的灯全部打开，最后只剩下第一行的灯有灭的，将第一行灯的状态用二进制数S表示，0表示灭，1表示亮。
    这样每个数代表一种状态，总共只有1024种状态，S从0-1023（二进制0000000000-1111111111）。
    将点灯解决方案中的第一行点灯情况也用二进制数P来表示（0表示不点击，1表示点击1次），第二行至第十行的点灯方法根本不用记忆。
    先点击第一行，然后从第二行逐行往下进行（根据上面一行的灯的状态进行点灯，使得本行点击后，上行的灯都打开即可）
记住基本的1024种状态S的的电灯方法P，就可解决所有的状态。具体结果如下：
为了减少空间，我把2进制数都表示成10进制数。         冒号前面是状态S，冒号后面是解决方法P
0：975    1：794    2：527    3：730    4：122    5：175    6：442    7：367    8：191    9：106   
10：383    11：426    12：778    13：991    14：714    15：543    16：802    17：1015    18：738    19：567   
20：151   21：66    22：343    23：386    24：82    25：135    26：402    27：327    28：999    29：818   
30：551   31：754    32：275    33：454    34：211    35：6    36：678    37：627    38：870    39：947   
40：611    41：694    42：931    43：886    44：470    45：259    46：22    47：195    48：510    49：299   
50：62    51：235    52：587    53：670    54：907    55：862    56：654    57：603    58：846    59：923  
  60：315    61：494    62：251    63：46    64：1012    65：801    66：564    67：737    68：65    69：148   
70：385    71：340    72：132    73：81    74：324    75：401    76：817    77：996    78：753    79：548  
  80：793    81：972    82：729    83：524    84：172    85：121    86：364    87：441    88：105    89：188
   90：425    91：380    92：988    93：777    94：540    95：713    96：296    97：509    98：232    99：61  
  100：669    101：584    102：861    103：904    104：600    105：653   106：920    107：845    108：493    109：312    110：45    111：248   112：453    113：272    114：5    115：208    116：624    117：677   118：944    119：869    120：693    121：608    122：885    123：928   124：256    125：469    126：192    127：21    128：376    129：429   130：184    131：109    132：717    133：536    134：781    135：984   136：520    137：733    138：968    139：797    140：445    141：360   142：125    143：168    144：405    145：320    146：85    147：128   148：544    149：757    150：992    151：821    152：741    153：560   154：805    155：1008    156：336    157：389    158：144    159：69   160：932    161：881    162：612    163：689    164：17    165：196   166：465    167：260    168：212    169：1    170：276    171：449   172：865    173：948    174：673    175：628    176：841    177：924   178：649    179：604    180：252    181：41    182：316    183：489   184：57    185：236    186：505    187：300    188：908    189：857   190：588    191：665    192：323    193：406    194：131    195：86   196：758    197：547    198：822    199：995    200：563    201：742   202：1011    203：806    204：390    205：339    206：70    207：147   208：430    209：379    210：110    211：187    212：539    213：718   214：987    215：782    216：734    217：523    218：798    219：971   220：363    221：446    222：171    223：126    224：927    225：842   226：607    227：650    228：42    229：255    230：490    231：319   232：239    233：58    234：303    235：506    236：858    237：911   238：666    239：591    240：882    241：935    242：690    243：615   244：199    245：18    246：263    247：466    248：2    249：215   250：450    251：279    252：951    253：866    254：631    255：674   256：961    257：788    258：513    259：724    260：116    261：161   262：436    263：353    264：177    265：100    266：369    267：420   268：772    269：977    270：708    271：529    272：812    273：1017   274：748    275：569    276：153    277：76    278：345    279：396   280：92    281：137    282：412    283：329    284：1001    285：828   286：553    287：764    288：285    289：456    290：221    291：8   292：680    293：637    294：872    295：957    296：621    297：696   298：941    299：888    300：472    301：269    302：24    303：205   304：496    305：293    306：48    307：229    308：581    309：656   310：901    311：848    312：640    313：597    314：832    315：917   316：309    317：480    318：245    319：32    320：1018    321：815   322：570    323：751    324：79    325：154    326：399    327：346   328：138    329：95    330：330    331：415    332：831    333：1002   334：767    335：554    336：791    337：962    338：727    339：514   340：162    341：119    342：354    343：439    344：103    345：178   346：423    347：370    348：978    349：775    350：530    351：711   352：294    353：499    354：230    355：51    356：659    357：582   358：851    359：902    360：598    361：643    362：918    363：835   364：483    365：310    366：35    367：246    368：459    369：286   370：11    371：222    372：638    373：683    374：958    375：875   376：699    377：622    378：891    379：942    380：270    381：475   382：206    383：27    384：374    385：419    386：182    387：99   388：707    389：534    390：771    391：982    392：518    393：723   394：966    395：787    396：435    397：358    398：115    399：166   400：411    401：334    402：91    403：142    404：558    405：763   406：1006    407：827    408：747    409：574    410：811    411：1022   412：350    413：395    414：158    415：75    416：938    417：895   418：618    419：703    420：31    421：202    422：479    423：266   424：218    425：15    426：282    427：463    428：879    429：954   430：687    431：634    432：839    433：914    434：647    435：594   436：242    437：39    438：306    439：487    440：55    441：226   442：503    443：290    444：898    445：855    446：578    447：663   448：333    449：408    450：141    451：88    452：760    453：557   454：824    455：1005    456：573    457：744    458：1021    459：808   460：392    461：349    462：72    463：157    464：416    465：373   466：96    467：181    468：533    469：704    470：981    471：768   472：720    473：517    474：784    475：965    476：357    477：432   478：165    479：112    480：913    481：836    482：593    483：644   484：36    485：241    486：484    487：305    488：225    489：52   490：289    491：500    492：852    493：897    494：660    495：577   496：892    497：937    498：700    499：617    500：201    501：28   502：265    503：476    504：12    505：217    506：460    507：281   508：953    509：876

[ 本帖最后由 lulijie 于 2009-7-4 15:29 编辑 ]

lulijie

510：633    511：684    512：355    513：438   514：163    515：118    516：726    517：515    518：790    519：963   520：531    521：710    522：979    523：774    524：422    525：371   526：102    527：179    528：398    529：347    530：78    531：155   532：571    533：750    534：1019    535：814    536：766    537：555   538：830    539：1003    540：331    541：414    542：139    543：94   544：959    545：874    546：639    547：682    548：10    549：223   550：458    551：287    552：207    553：26    554：271    555：474   556：890    557：943    558：698    559：623    560：850    561：903   562：658    563：583    564：231    565：50    566：295    567：498   568：34    569：247    570：482    571：311    572：919    573：834   574：599    575：642    576：344    577：397    578：152    579：77   580：749    581：568    582：813    583：1016    584：552    585：765   586：1000    587：829    588：413    589：328    590：93    591：136   592：437    593：352    594：117    595：160    596：512    597：725   598：960    599：789    600：709    601：528    602：773    603：976   604：368    605：421    606：176    607：101    608：900    609：849   610：580    611：657    612：49    613：228    614：497    615：292   616：244    617：33    618：308    619：481    620：833    621：916   622：641    623：596    624：873    625：956    626：681    627：636   628：220    629：9    630：284    631：457    632：25    633：204   634：473    635：268    636：940    637：889    638：620    639：697   640：980    641：769    642：532    643：705    644：97    645：180   646：417    647：372    648：164    649：113    650：356    651：433   652：785    653：964    654：721    655：516    656：825    657：1004   658：761    659：556    660：140    661：89    662：332    663：409   664：73    665：156    666：393    667：348    668：1020    669：809   670：572    671：745    672：264    673：477    674：200    675：29   676：701    677：616    678：893    679：936    680：632    681：685   682：952    683：877    684：461    685：280    686：13    687：216   688：485    689：304    690：37    691：240    692：592    693：645   694：912    695：837    696：661    697：576    698：853    699：896   700：288    701：501    702：224    703：53    704：1007    705：826   706：559    707：762    708：90    709：143    710：410    711：335   712：159    713：74    714：351    715：394    716：810    717：1023   718：746    719：575    720：770    721：983    722：706    723：535   724：183    725：98    726：375    727：418    728：114    729：167   730：434    731：359    732：967    733：786    734：519    735：722   736：307    737：486    738：243    739：38    740：646    741：595   742：838    743：915    744：579    745：662    746：899    747：854   748：502    749：291    750：54    751：227    752：478    753：267   754：30    755：203    756：619    757：702    758：939    759：894   760：686    761：635    762：878    763：955    764：283    765：462   766：219    767：14    768：365    769：440    770：173    771：120   772：728    773：525    774：792    775：973    776：541    777：712   778：989    779：776    780：424    781：381    782：104    783：189   784：384    785：341    786：64    787：149    788：565    789：736   790：1013    791：800    792：752    793：549    794：816    795：997   796：325    797：400    798：133    799：80    800：945    801：868   802：625    803：676    804：4    805：209    806：452    807：273   808：193    809：20    810：257    811：468    812：884    813：929   814：692    815：609    816：860    817：905    818：668    819：585   820：233    821：60    822：297    823：508    824：44    825：249   826：492    827：313    828：921    829：844    830：601    831：652   832：342    833：387    834：150    835：67    836：739    837：566   838：803    839：1014    840：550    841：755    842：998    843：819   844：403    845：326    846：83    847：134    848：443    849：366   850：123    851：174    852：526    853：731    854：974    855：795   856：715    857：542    858：779    859：990    860：382    861：427   862：190    863：107    864：906    865：863    866：586    867：671   868：63    869：234    870：511    871：298    872：250    873：47   874：314    875：495    876：847    877：922    878：655    879：602   880：871    881：946    882：679    883：626    884：210    885：7   886：274    887：455    888：23    889：194    890：471    891：258   892：930    893：887    894：610    895：695    896：986    897：783   898：538    899：719    900：111    901：186    902：431    903：378   904：170    905：127    906：362    907：447    908：799    909：970   910：735    911：522    912：823    913：994    914：759    915：546   916：130    917：87    918：322    919：407    920：71    921：146   922：391    923：338    924：1010    925：807    926：562    927：743   928：262    929：467    930：198    931：19    932：691    933：614   934：883    935：934    936：630    937：675    938：950    939：867   940：451    941：278    942：3    943：214    944：491    945：318   946：43    947：254    948：606    949：651    950：926    951：843   952：667    953：590    954：859    955：910    956：302    957：507   958：238    959：59    960：993    961：820    962：545    963：756   964：84    965：129    966：404    967：321    968：145    969：68   970：337    971：388    972：804    973：1009    974：740    975：561   976：780    977：985    978：716    979：537    980：185    981：108   982：377    983：428    984：124    985：169    986：444    987：361   988：969    989：796    990：521    991：732    992：317    993：488   994：253    995：40    996：648    997：605    998：840    999：925   1000：589    1001：664    1002：909    1003：856    1004：504    1005：301   1006：56    1007：237    1008：464    1009：261    1010：16    1011：197   1012：613    1013：688    1014：933    1015：880    1016：672    1017：629   1018：864    1019：949    1020：277    1021：448    1022：213    1023：0   
-------------------------------------------------------------------------------------------------------
应用上表可解决所有的点灯问题：先将状态转换成基本状态S，查上表，获得解决方法P。
将P表示成2进制，然后从第一行开始逐行点灯即可。

lulijie

比如：
              一般状态
转化：
              基本状态
用二进制表示基本状态的灯的情况 得到  0010011001                  0表示灭，1表示亮
    十进制就是153，查表得 P=560，表示成2进制及1000110000。
先点击第一行1000110000（1表示相应的格子点击1次，0表示相应的格子不点击），得以下：
→→         点击第二行使得第一行全亮 →→    点击第三行使得第二行全亮→→          点击第四行使得第三行全亮→→      点击第五行使得第四行全亮→→          点击第六行使得第五行全亮→→      点击第七行使得第六行全亮→→        点击第八行使得第七行全亮→→    点击第九行使得第八行全亮→→        点击第十行使得第九行全亮→→   

[ 本帖最后由 lulijie 于 2009-7-4 15:59 编辑 ]

lulijie

要获得最少步数，先记住将一般状态转化成基本状态的第一行的点击情况P‘，再获得基本状态的解决方案P。
那么最少步数的第一行的点击方法=P’+P。   （ 化为二进制，同位数相加，若等于2就记作0，不进位。）
知道了第一行的点击方法，以下每一行的点击方法就逐行完成。