魔方吧·中文魔方俱乐部

标题: 点灯游戏的解法讨论 [打印本页]
作者: noski    时间: 2009-7-3 15:00:06     标题: 点灯游戏的解法讨论

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

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

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

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


http://files2.17173.com/flash/4062.swf

说说我的两个想法：
当从上而下点灯时，最后一行灯的状态只与第一行灯的状态和点击有关；
随机亮灯时，先从下至上全部灭掉，再从上至下全部打开。
作者: superacid    时间: 2009-7-3 15:19:13

可以编程搜索，就1024种情况嘛
作者: migl    时间: 2009-7-3 16:05:45

（题外话）
找个显示步数（ 点的次数 ）的吧。还能顺便玩玩。
作者: lulijie    时间: 2009-7-4 11:21:13

我就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    时间: 2009-7-4 12:20:13

小时候在游戏机上玩过5x5的，当时是琢磨出了一个解决方法的（虽然不知道道理是什么），现在反倒不记得了……
作者: sokoban    时间: 2009-7-4 12:26:49

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

http://mathworld.wolfram.com/LightsOutPuzzle.html
作者: lulijie    时间: 2009-7-4 15:07:25

便于记忆的一般解法：
    从最下面开始逐层往上将每行的灯全部打开，最后只剩下第一行的灯有灭的，将第一行灯的状态用二进制数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    时间: 2009-7-4 15:10:52

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    时间: 2009-7-4 15:14:29

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

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

附件: a.jpg (2009-7-4 15:14:29, 20.37 KB) / 下载次数 122
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTc5MzF8YjQwYThkMDJ8MTc0MDU4MjExMnwwfDA%3D

附件: b.jpg (2009-7-4 15:14:29, 22.04 KB) / 下载次数 103
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTc5MzJ8NDFkYzE2OTd8MTc0MDU4MjExMnwwfDA%3D

附件: b1.jpg (2009-7-4 15:14:29, 22.11 KB) / 下载次数 111
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTc5MzN8NDkzODcxZjJ8MTc0MDU4MjExMnwwfDA%3D

附件: b2.jpg (2009-7-4 15:14:29, 22.94 KB) / 下载次数 99
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTc5MzR8ZTQ5MGJhMjR8MTc0MDU4MjExMnwwfDA%3D

附件: b3.jpg (2009-7-4 15:14:29, 22.61 KB) / 下载次数 103
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTc5MzV8NmYwYWU5Y2J8MTc0MDU4MjExMnwwfDA%3D

附件: b4.jpg (2009-7-4 15:14:29, 22.5 KB) / 下载次数 108
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTc5MzZ8Njc5MDRjNDR8MTc0MDU4MjExMnwwfDA%3D

附件: b5.jpg (2009-7-4 15:14:29, 21.97 KB) / 下载次数 110
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTc5Mzd8ZWE0MjRiZjl8MTc0MDU4MjExMnwwfDA%3D

附件: b6.jpg (2009-7-4 15:14:29, 22.35 KB) / 下载次数 110
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTc5Mzh8M2RiNmQyYmJ8MTc0MDU4MjExMnwwfDA%3D

附件: b7.jpg (2009-7-4 15:14:29, 22.95 KB) / 下载次数 108
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTc5Mzl8NzM3NzM2ZTF8MTc0MDU4MjExMnwwfDA%3D

附件: b8.jpg (2009-7-4 15:14:29, 22.58 KB) / 下载次数 99
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTc5NDB8NjRmZjEwNmN8MTc0MDU4MjExMnwwfDA%3D

附件: b9.jpg (2009-7-4 15:14:29, 22.85 KB) / 下载次数 128
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTc5NDF8OGIzYTMzNWV8MTc0MDU4MjExMnwwfDA%3D

附件: b10.jpg (2009-7-4 15:14:29, 22.48 KB) / 下载次数 112
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTc5NDJ8MThmZDJiNTd8MTc0MDU4MjExMnwwfDA%3D
作者: lulijie    时间: 2009-7-4 15:24:56

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

楼主所谓的最乱状态，无非指最少步数最大的状态。
最少步数最大的就是每个格子都点击一次。
应该是将全亮的状态每个格子都点击一次形成的状态，如下：
         c.jpg

附件: c.jpg (2009-7-4 15:35:51, 19.78 KB) / 下载次数 20
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTc5NDN8MTBmZmY2MjB8MTc0MDU4MjExMnwwfDA%3D
作者: noski    时间: 2009-7-4 16:26:48

顶，分析得漂亮！
我发现一个有意思的地方：
你11楼这个图，是从灯全亮状态下每个格点击一下，一共点击了100下得到的。
我按照你前面的解法来解这个图，先从下至上把灯全部点亮，除了最顶行，这用了42步；
查得状态633：204，然后从上至下把灯全部点亮，用了58步，加起来恰好是100步！

还有，lulijie贴出的1024表格挺有用的，但是玩起游戏来还要查表，就不那么容易了，谁也记不住啊，呵呵！

另外1楼游戏的小BUG：在一个格子里狂点三四下，这几格的灯就全亮或全灭了-_-
作者: superacid    时间: 2009-7-4 20:02:28

谢谢sokoban，看来这样的问题就是要解一个矩阵方程，长见识了。
作者: superacid    时间: 2009-7-4 21:33:30

不过好像如果阶数再大一点，电脑会算爆掉的
作者: noski    时间: 2009-7-5 00:39:45

回复sokoban：
回复superacid：
sokoban发的链接中的方法直接可以解出最终结果，对于10*10的游戏，要解一个100维的非齐次线性方程组。
这样看来，“最少步数”“最乱状态”什么的就都可以靠穷举搜索出来。

看看能不能找到一个可玩性好点的策略，让这个游戏除了查表、解方程组之外，不只是碰运气-___-，这样没事还可以玩一玩。。
就像平时玩魔方，我们不是对于每个乱的魔方，都去全空间搜索它的最短路径来还原它，而是有一系列的方法，比如层先、CFOP等。。
作者: 今夜微凉    时间: 2009-7-5 09:16:45

点灯可以用~~层先法~~~呵呵~~所以只需要最后一层的公式即可~~情况也不多~~
作者: lulijie    时间: 2009-7-5 09:28:46

先将一般状态转化为基本状态S，解决方法为P：
那么S和P的关系可以：
1.   查表法。
2.   可以用表达式法。
    S=A1A2A3A4A5A6A7A8A9A10   （十位二进制）
    设 P=B1B2B3B4B5B6B7B8B9B10  ，那么
    B1=A1+A3+A5+A7+A8+1                            这里的加法是模2加法（也就是总和除以2，取它的余数。)
    B2=A7+A8+A9+1
    B3=A1+A3+A5+A6+A8+A9+A10+1
    B4=A5+A6+A7+A9+A10+1
    B5=A1+A3+A4+A6+A7+A8

    B6=A3+A4+A5+A7+A8+A10
    B7=A1+A2+A4+A5+A6+1
    B8=A1+A2+A3+A5+A6+A8+A10+1
    B9=A2+A3+A4+1
    B10=A3+A4+A6+A8+A10+1
  十条公式，其实只要记忆前面5条就可，（1-5 与10-6 公式是对称的。）
---------------------------------------------
用这些式子的好处是不用进行进制的换算。
直接根据第一行灯的亮灭情况写出 A1A2A3A4A5A6A7A8A9A10 ，
然后运用公式得到B1B2B3B4B5B6B7B8B9B10。
根据B1B2B3B4B5B6B7B8B9B10，就可以直接进行第一行灯的点击操作，非常方便。
作者: 今夜微凉    时间: 2009-7-5 09:37:39

原帖由 lulijie 于 2009-7-5 09:28 发表
先将一般状态转化为基本状态S，解决方法为P：
那么S和P的关系可以：
1.   查表法。
2.   可以用表达式法。
    S=A1A2A3A4A5A6A7A8A9A10   （十位二进制）
    设 P=B1B2B3B4B5B6B7B8B9B10  ，那么
    B1=A1+ ...

楼上的十分详细啊~~看来已经完全解决点灯问题了~~呵呵
作者: lulijie    时间: 2009-7-5 09:50:57

公式法，跟楼主所推崇的魔方解法很类似。
第一步：层先法  ，最后只剩最上面一层。
第二步：运用公式，只要记忆5个（或10个）公式，比魔方的公式少多了，而且公式很简单。
第三步：返层。完成。
作者: lulijie    时间: 2009-7-5 13:32:08

前面所说的公式法，在第二步，运行公式的时候，由于点击的格子会影响灯的亮灭状态，所以不能边点击边计算公式，必须10个公式一次性计算完毕，才能开始点击，影响了速度。
    我现在把解决方案P的点击不放在第一行，而是放在最下一行，这样可以边点击边运用公式计算结果，速度加快。
这样重新计算，得到计算公式如下，非常简洁：
    S=A1A2A3A4A5A6A7A8A9A10   （十位二进制）
       设 P=B1B2B3B4B5B6B7B8B9B10  ，那么
              B1 =A3+1                       B10 =A8+1
              B2 =A2+A4                     B9 =A9+A7
              B3 =A1+A3+A5+1           B8 =A10+A8+A6+1
              B4 =A2+A4+A6+1           B7 =A9+A7+A5+1
              B5 =A3+A5+A7+1           B6 =A8+A6+A4+1
-------------------------------------------------
这样，解法步骤如下：
第一步：从下往上逐渐点亮每行的所有灯，只剩第一行，
             转化为基本状态  S=A1A2A3A4A5A6A7A8A9A10     
           （Ai表示第一行第i列的灯的状态，值为1表示该灯亮，0表示灭。）
第二步：运用公式计算P的值：    P=B1B2B3B4B5B6B7B8B9B10
              B1 =A3+1                       B10 =A8+1
              B2 =A2+A4                     B9 =A9+A7
              B3 =A1+A3+A5+1           B8 =A10+A8+A6+1
              B4 =A2+A4+A6+1           B7 =A9+A7+A5+1
              B5 =A3+A5+A7+1           B6 =A8+A6+A4+1
         Bi=1表示点击最下面一行的第i个格子的灯，Bi=0表示该格子不点击。
第三步： 从下往上依次点亮每行格子的灯。
-------------------------------------------------------------------------------------
我觉得非常完美了，公式非常好记，楼主应该够满意了吧。
作者: lulijie    时间: 2009-7-5 14:06:25

B1 =A3+1                       B10 =A8+1
              B2 =A2+A4                     B9 =A9+A7
              B3 =A1+A3+A5+1           B8 =A10+A8+A6+1
              B4 =A2+A4+A6+1           B7 =A9+A7+A5+1
              B5 =A3+A5+A7+1           B6 =A8+A6+A4+1
上述公式的记忆方法可以这样：
  1.   距边1个格子的地方，只有1个加数，
        距边2个格子的地方，只有2个加数，
        距边3个以上格子的地方，有3个加数。
2.     第一个加数是 该格子往中间方向行2个格子的值。若还有第二、第三个加数，那么每个加数都是往边上行2个格子。
      若加数的个数是奇数，则需加上1。
---------------------------------------------
比如B8，8往中间方向行2个格子，就是A6，因为总共3个加数，依次加上A8，A10（往边方向行每次行2格），奇数个加数再加1。
    所以B8=A6+A8+A10+1
作者: 金眼睛    时间: 2009-7-5 15:32:05

呵呵，其实没有那么麻烦，无论是n*n的方阵，还是m*n的方阵，都可以采用倒推的方法解决。

开始的时候设定灯都是亮的，对最下面一行的灯采用各种点击方式（如本例共有1024种点击方式），然后倒推到前两行，记录下第一行将第二行的灯都打亮的操作以及最后第一行灯的状态即可。

这里最后一行的状态及操作，还有第一行的状态及操作是一一对应的。
例如：最后一行状态（固定为：1111111111），最后一行操作（取1024中的一种，例如：000000001）

          倒推到第一行：
          第一行状态（对应为：1010111010—698），第一行操作（对应为：1101010101—853）

可以看到这与lulijie提供的表中的数据是一致的，其实它们都来源于倒推的第一步操作000000001。

当所有操作的结果都获得了以后，就可以按图索骥了。

最后鉴于noski提供的Flash中存在小bug，而且没有全开全关也不便研究，我重新编了一下。

时间仓促，如果有什么错误或者好的建议就留言吧，我好进行更正，o(∩_∩)o...

[ 本帖最后由 金眼睛 于 2009-7-5 15:35 编辑 ]

附件: [Light程序界面] LightsOutPuzzle.JPG (2009-7-5 15:32:05, 39.64 KB) / 下载次数 34
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTgwNjd8NzQyNzQyMTh8MTc0MDU4MjExMnwwfDA%3D

附件: [Light程序] LightsOutPuzzle.rar (2009-7-5 15:32:05, 205.79 KB) / 下载次数 49
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTgwNjh8NTY4MjMzY2Z8MTc0MDU4MjExMnwwfDA%3D
作者: Cielo    时间: 2009-7-5 16:10:52

楼上两位真厉害，我来学习一下！
作者: lulijie    时间: 2009-7-5 17:30:54

公式法：采用我的20楼的方法。对于n*m方阵，结果如下
------------------------------------------------
4*4、5*5、9*9、11*11、3*2、5*2、7*2、9*2、5*3、8*3、9*4、7*5、8*5、9*5、8*6、8*7、9*8
    无公式解，即某些状态无解。
------------------------------------------------
2*2、4*2、6*2、8*2、10*2
    B1 =A1+1
    B2 =A2+1
------------------------------------------------
3*3
    B1 =A2+A1
    B2 =A3+A2+A1+1
    B3 =A3+A2
---------------------------
4*3、6*3
    B1 =A3+1
    B2 =A2+1
    B3 =A1+1
------------------------
7*3、9*3
    B1 =A2+A1
    B2 =A3+A2+A1+1
    B3 =A3+A2
-----------------
10*3
    B1 =A1+1
    B2 =A2+1
    B3 =A3+1
--------------------------------------------------
4*5、10*5
B5 =A1+1
B4 =A2+1
B3 =A3+1
B2 =A4+1
B1 =A5+1
-------------------
6*4
B1 =A3+1
B2 =A4+A2
B3 =A3+A1
B4 =A2+1
-------------------
7*4
B1 =A4+A3+A1+1
B2 =A4+A3
B3 =A2+A1
B4 =A4+A2+A1+1
------------------
8*4、10*4
B1 =A1+1
B2 =A2+1
B3 =A3+1
B4 =A4+1
----------------------------------
6*5
B1 =A1+1
B2 =A2+1
B3 =A3+1
B4 =A4+1
B5 =A5+1
-----------------------
6*6、10*6
    B1 =A3+A1
    B2 =A4+1
    B3 =A5+A1
    B4 =A6+A2
    B5 =A3+1
    B6 =A6+A4
----------------------------
7*6、9*6
B1 =A4+A3+A1+1
B2 =A5+A4+A3+1
B3 =A6+A5+A4+A2+A1+1
B4 =A6+A5+A3+A2+A1+1
B5 =A4+A3+A2+1
B6 =A6+A4+A3+1
------------------------------------------
7*7
    B1 =A2+A1
    B2 =A3+A2+A1+1
    B3 =A4+A3+A2+1
    B4 =A5+A4+A3+1
    B5 =A6+A5+A4+1
    B6 =A7+A6+A5+1
    B7 =A7+A6
---------------------------------------------
9*7
B1 =A4+A3+A2+1
B2 =A5+A4+A2+A1
B3 =A6+A5+A3+A1
B4 =A7+A6+A4+A2+A1+1
B5 =A7+A5+A3+A2
B6 =A7+A6+A4+A3
B7 =A6+A5+A4+1
----------------------------------------
10*7
B1 =A5+A3+A1+1
B2 =A6+1
B3 =A7+A3+A1+1
B4 =A4+1
B5 =A7+A5+A1+1
B6 =A2+1
B7 =A7+A5+A3+1
-----------------------------------------------
8*8
    B1 =A5+A3
    B2 =A6+A2
    B3 =A7+A1
    B4 =A8+1
    B5 =A1+1
    B6 =A8+A2
    B7 =A7+A3
    B8 =A6+A4
----------------------------
10*8
B1 =A7+A3
B2 =A8+A6+A4+A2
B3 =A7+A3+A1+1
B4 =A2+1
B5 =A7+1
B6 =A8+A6+A2+1
B7 =A7+A5+A3+A1
B8 =A6+A2
--------------------------
10*9
B1 =A7+A3+A1+1
B2 =A8+A6+A4+1
B3 =A9+A7+A1+1
B4 =A8+A4+A2+1
B5 =A5+1
B6 =A8+A6+A2+1
B7 =A9+A3+A1+1
B8 =A6+A4+A2+1
B9 =A9+A7+A3+1
--------------------------------
10*10
    B1 =A3+1
    B2 =A4+A2
    B3 =A5+A3+A1+1
    B4 =A6+A4+A2+1
    B5 =A7+A5+A3+1
    B6 =A8+A6+A4+1
    B7 =A9+A7+A5+1
    B8 =A10+A8+A6+1
    B9 =A9+A7
    B10 =A8+1
-------------------------------------
12*12
    B1 =A9+A7+A5+1
    B2 =A10+A4
    B3 =A11+A7+A3+1
    B4 =A12+A8+A6+A2
    B5 =A9+A7+A5+A1
    B6 =A12+A10+A8+A6+A4+1
    B7 =A9+A7+A5+A3+A1+1
    B8 =A12+A8+A6+A4
    B9 =A11+A7+A5+A1
    B10 =A10+A6+A2+1
    B11=A9+A3
    B12 =A8+A6+A4+1
-----------------------------------
13*13
    B1 =A12+A11+A10+A6+A5+A3+A2+1
B2 =A13+A12+A10+A9+A7+A6+A5+A3+A2+A1
B3 =A13+A11+A9+A7+A6+A2+A1+1
B4 =A13+A12+A10+A9
B5 =A12+A11+A10+A8+A7+A6+A2+A1
B6 =A9+A8+A6+A5+A3+A2+A1+1
B7 =A12+A11+A9+A7+A5+A3+A2+1
B8 =A13+A12+A11+A9+A8+A6+A5+1
B9 =A13+A12+A8+A7+A6+A4+A3+A2
B10 =A5+A4+A2+A1
B11 =A13+A12+A8+A7+A5+A3+A1+1
B12 =A13+A12+A11+A9+A8+A7+A5+A4+A2+A1
B13 =A12+A11+A9+A8+A4+A3+A2+1
作者: lulijie    时间: 2009-7-5 17:56:02

金眼睛兄的点灯程序还可以优化：
1.状态栏不用手动输入（可以把它从窗口中删除），直接根据左边格子上的灯的状态，给出解法。
2.左边的灯也不要求2-9行灯全亮，任意一般状态，直接给出最少步数解，最少步数解只要给出第一行的解就行。解法的框足够显示，不用扩大。
3.最好设计一个选择项，可以选择n*m方框。
作者: 金眼睛    时间: 2009-7-5 20:04:42     标题: 回复 25# 的帖子

呵呵，你的提议很好啊，多谢多谢！

明天上班，没时间弄了，先弄了一版没提示的，本着娱乐精神，加入了一些好玩的功能，哈哈！

附件: [点灯游戏] LightsOutPuzzle.rar (2009-7-5 20:04:42, 209.01 KB) / 下载次数 54
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTgwODR8NWZjYjJlN2R8MTc0MDU4MjExMnwwfDA%3D
作者: sokoban    时间: 2009-7-5 20:27:01

金眼睛兄的新版本很好用，我十分喜欢。
作者: superacid    时间: 2009-7-5 20:43:20

新版本某些功能蛮有趣的。
作者: noski    时间: 2009-7-7 01:30:18

lulijie在20楼的解法很不错，用此法可一举解决点灯问题，在步数和时间上有个平衡，可玩性好。。
在理解了这个解法之后就可以更直观一些，不用记任何公式。比如对于距边3个格子以上的地方（N，1），只要看（N-2，10）、（N，10）、（N+2，10）这三个位置亮灯的个数，如果亮的灯是偶数，就需要点击一下。

金眼睛的小程序也很赞，还有击缶功能
作者: ggglgq    时间: 2009-7-7 09:27:23

　　
　　
  
    这是一个典型的“交换群”，因此它可以用“线性方程组”来解决。
  
    看到 sokoban 的发言，使我想起 “三陪集 正六面体四轴二阶魔方”(Skewb) 。
  
相关讨论请大家参考：
  
    Skewb 中的一些理论问题  http://bbs.mf8-china.com/viewthread.php?tid=18112
  
那么什么样的魔方是“三陪集魔方”、“ N 陪集魔方”呢？请大家参考：
  
  奇偶差异性魔方的拓展推广  http://bbs.mf8-china.com/viewthread.php?tid=7532&page=1#pid109484
  
   
　　
　　
　　
作者: ggglgq    时间: 2009-7-7 09:29:30

　　
　　
  
    为什么要提及“ N 陪集魔方”呢？ 因我们可以利用类似本主题的“交换群”
  
很容易地构造“N 陪集魔方”，比如 灯 的色彩可自定义为
  
    灭、亮、色2、 ...  、色N-1  （ 0 、 1 、 2 、  ...  、 N-1 ） 循环
  
对于极个别的“灯 交换群”可构造出“N 陪集魔方”！
  
     当然，灯的形状也可自定义！ 大家可以试试！
  
   
     对比 “三陪集 正六面体四轴二阶魔方” ( Skewb ) ，需要注意的是：
  
     “正六面体四轴二阶魔方” ( Skewb ) 对于“四轴心”旋转构成“三陪集”
  
魔方，但如果按 八角方向旋转，那就谈不上“三陪集魔方”了！ 大家可以试试！
  
     对比 “ N 陪集魔方”，也要注意类似问题。
  
　　
　　
　　
作者: lulijie    时间: 2009-7-7 11:50:05

对于以下公式，有下面助记歌：
              B1 =A3+1                       B10 =A8+1
              B2 =A2+A4                     B9 =A9+A7
              B3 =A1+A3+A5+1           B8 =A10+A8+A6+1
              B4 =A2+A4+A6+1           B7 =A9+A7+A5+1
              B5 =A3+A5+A7+1           B6 =A8+A6+A4+1
                              10*10点灯歌
               1看3，      10看8，               没有灯亮点；         
               2看2、4， 9看9、7，          一盏灯亮点；
               余下就看三盏灯(n,n-2,n+2)，零盏、两盏灯亮点。
作者: lulijie    时间: 2009-7-26 14:54:46

10*10点灯的方法也可以如下：将原来第一步的点亮所有灯，变为熄灭所有灯。
这样，解法步骤如下：
第一步：从下往上逐渐熄灭每行的所有灯，只剩第一行，
            第一行灯的状态  S=A1A2A3A4A5A6A7A8A9A10     
           （Ai表示第一行第i列的灯的状态，值为1表示该灯亮，0表示灭。）
第二步：运用公式计算P的值：    P=B1B2B3B4B5B6B7B8B9B10
              B1 =A3+1                       B10 =A8+1
              B2 =A2+A4                     B9 =A9+A7
              B3 =A1+A3+A5+1           B8 =A10+A8+A6+1
              B4 =A2+A4+A6               B7 =A9+A7+A5
              B5 =A3+A5+A7               B6 =A8+A6+A4
         Bi为奇数表示点击最下面一行的第i个格子的灯，Bi为偶数表示该格子不点击。
第三步： 从下往上依次点亮每行格子的灯。
-----------------------------------------------------------------
这样若原来所有的灯都是熄灭的，那么所有的Ai值都等于0。代入上述公式得B1=B3=B8=B10=1，其他都等于0。
所以点击方法P就是1010000101。
将最下行的第1、3、8、10个格子各点击一下，然后从第九行往上，依次点亮所有下一行的灯即可。
作者: lulijie    时间: 2009-7-26 16:06:21

记得魔方转法中有换角、换边等公式，所谓的换角、换边公式，就是保持不参加交换的块不变的一系列手法公式。
       我突然觉得10*10点灯游戏中应该也有类似的公式。
       先把灯的一般状态转变成基本状态，使得除了第一行以外，其他各行的灯都是全亮的。
       那么第一行的第一列的灯若是灭的，那么应该存在一种点灯方法，该方法仅使得第一行第一列的灯的状态发生改变，而不影响其他所有的灯的状态。
10*10点灯的单格转换公式
      我们用g(m)表示仅使得第1行第m列的灯的状态发生改变，而其他所有灯状态都不改变的点灯方法。（可以用最后一行格子的点击组合来代替所有格子的点击方案）。
那么g(1)=3           g(10)=8
       g(2)=2,4        g(9)=7,9  
       g(3)=1,3,5   
       g(4)=2,4,6   
       g(5)=3,5,7  
       g(6)=4,6,8
       g(7)=5,7,9  
       g(8)=6,8,10
---------------------------------------------
这样经过第一步将一般状态转化成基本状态后，
若第一行只剩第3列的格子是灭的，因为g(3)=1,3,5
        那么只需要点击一下最后一行的第1、3、5格子，然后从第九行开始依次点亮下面一行所有的灯即可。
若第一行只剩第3、5列的格子是灭的，因为g(3)=1,3,5  ， g(5)=3,5,7
       那么先点击一下最后一行的第1、3、5格子，接着点击一下第3，5，7格子，然后从第九行开始依次点亮下面一行所有的灯即可。或者  g(3) + g(5)=1,3,5   +   3,5,7  =1,7        (点击两次等于不点击)
对于第一行其他的灯的状态，只要看那些灯是灭的，依次运行g(m)方法即可。
--------------------------------------------------------------------------------
这种方法的好处不用进行加法计算，转化为基本状态后，根据第一行那些灯灭着，对每盏熄灭的灯在第十行的格子各运行一次g(m)方法即可。g公式非常简单，点击过程几乎不假思索就可进行。
作者: lulijie    时间: 2009-7-26 18:35:57

如果我们用g(n,m)表示仅使得第n行第m列的灯的状态发生改变，而其他所有灯状态都不改变的点灯方法(点灯方法用最后一行需点击的格子的组合来表示)。
那么一共有100个值，运用这100个值，就可以推导出所有状态的最少步数解法。
--------------------------------------------------------------------
g(1,1)=3             ‘表示成10位2进制数就是  0010000000
g(1,2)=2,4           ‘表示成10位2进制数就是  0101000000
g(1,3)=1,3,5        ‘表示成10位2进制数就是  1010100000
g(1,4)=2,4,6        ‘表示成10位2进制数就是  0101010000
g(1,5)=3,5,7       ‘表示成10位2进制数就是   0010101000
g(1,6)=4,6,8       ‘表示成10位2进制数就是  0001010100
g(1,7)=5,7,9      ‘表示成10位2进制数就是    0000101010
g(1,8)=6,8,10      ‘表示成10位2进制数就是  0000010101
g(1,9)=7,9          ‘表示成10位2进制数就是  0000001010
g(1,10)=8           ‘表示成10位2进制数就是  0000000100

g(2,1)=2,3,4
g(2,2)=1,2,4,5
g(2,3)=1,3,5,6
g(2,4)=1,2,4,6,7
g(2,5)=2,3,5,7,8
g(2,6)=3,4,6,8,9
g(2,7)=4,5,7,9,10
g(2,8)=5,6,8,10
g(2,9)=6,7,9,10
g(2,10)=7,8,9

g(3,1)=1,5
g(3,2)=2,4,6
g(3,3)=5,7
g(3,4)=2,6,8
g(3,5)=1,3,7,9
g(3,6)=2,4,8,10
g(3,7)=3,5,9
g(3,8)=4,6
g(3,9)=5,7,9
g(3,10)=6,10


g(4,1)=1,3,5,6
g(4,2)=5,6,7
g(4,3)=1,3,4,6,7,8
g(4,4)=3,4,5,7,8,9
g(4,5)=1,2,4,5,6,8,9,10
g(4,6)=1,2,3,5,6,7,9,10
g(4,7)=2,3,4,6,7,8
g(4,8)=3,4,5,7,8,10
g(4,9)=4,5,6
g(4,10)=5,6,8,10

g(5,1)=3,5,7
g(5,2)=2,8
g(5,3)=1,5,9
g(5,4)=4,6,10
g(5,5)=1,3,5,7
g(5,6)=4,6,8,10
g(5,7)=1,5,7
g(5,8)=2,6,10
g(5,9)=3,9
g(5,10)=4,6,8

g(6,1)=1,2,6,7,8
g(6,2)=1,2,3,5,6,8,9
g(6,3)=2,3,5,7,9,10
g(6,4)=5,6,8,10
g(6,5)=2,3,4,6,7,9,10
g(6,6)=1,2,4,5,7,8,9
g(6,7)=1,3,5,6
g(6,8)=1,2,4,6,8,9
g(6,9)=2,3,5,6,8,9,10
g(6,10)=3,4,5,9,10

g(7,1)=9
g(7,2)=8,10
g(7,3)=7,9
g(7,4)=6,8
g(7,5)=5,7
g(7,6)=4,6
g(7,7)=3,5
g(7,8)=2,4
g(7,9)=1,3
g(7,10)=2

g(8,1)=1,2,6,7,9,10
g(8,2)=1,2,3,5,6,7,9,10
g(8,3)=2,3,5,6
g(8,4)=9,10
g(8,5)=2,3,5,6,8,9,10
g(8,6)=1,2,3,5,6,8,9
g(8,7)=1,2
g(8,8)=5,6,8,9
g(8,9)=1,2,4,5,6,8,9,10
g(8,10)=1,2,4,5,9,10

g(9,1)=3,5,9
g(9,2)=2,6,8,10
g(9,3)=1,9
g(9,4)=6
g(9,5)=1,5,7,9
g(9,6)=2,4,6,10
g(9,7)=5
g(9,8)=2,10
g(9,9)=1,3,5,9
g(9,10)=2,6,8

g(10,1)=1,3,5,7,8
g(10,2)=7,8,9
g(10,3)=1,3,5,6,8,9,10
g(10,4)=5,6,7,9,10
g(10,5)=1,3,4,6,7,8
g(10,6)=3,4,5,7,8,10
g(10,7)=1,2,4,5,6
g(10,8)=1,2,3,5,6,8,10
g(10,9)=2,3,4
g(10,10)=3,4,6,8,10
------------------------------------------------------
将所有灯不亮的格子的n,m值代入g(n,m)中，将它们全部相加，若某个数字出现偶数次，将它全部消除；若出现奇数次，保留一个。这样得到的结果就是最少步数解法。它比前面的解法少了第一步，可以直接得到结果。
这种方法适用于电脑解答，金眼睛可以将它整合进他的点灯程序中。
         (可以用10位2进制数表示g(n,m)，用异或运算表示不同的g(n,m)相加，计算结果非常快）
作者: yang_bigarm    时间: 2009-8-19 21:49:27

原帖由 superacid 于 2009-7-3 15:19 发表
可以编程搜索，就1024种情况嘛


您在开玩笑吗？怎么是1024种情况呢？应该是2^1024种情况吧。

原帖由 sokoban 于 2009-7-4 12:26 发表
就是解一个线性方程组，可以参考这个：

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


我原来就思考过这个问题，后来在mathWorld上看到了答案，确实不能盲目搜索啊，要
靠解一个0-1矩阵的方程，我是用mathematica解的，自己编比较麻烦。但是mathWorld
上面只是给了方程，然后就是让你求逆举证，可是如果你直接调用mathematica求逆矩阵
可能求不出来，但是如果回到求逆矩阵本源的方法——高斯消元法，就可以得到正解。

注意这个0-1矩阵的方程可能无解，按照线性代数书上的判别准则，初始条件构成的0-1矩阵
和原来的0-1矩阵构成的叫增广矩阵，增广矩阵的秩大于方程矩阵的秩，那就无解了。

关于点灯游戏，我知道的大概也就这么多了，如果对于更大规模的问题，比如20x20方格的
点灯游戏，直接求解方程也是很慢的，但是高斯消元法有并行的算法，即在多个CPU上运行
的算法，用这个方法可以求解规模稍微大一些的问题。这个问题的算法复杂度是O(n^4)  
（求矩阵的逆是 n^2， 矩阵的规模又是 n^2）。



欢迎光临 魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/) Powered by Discuz! X2