題:
解決“熄燈”難題的策略
Denilson Sá Maia
2010-11-18 05:44:24 UTC
view on stackexchange narkive permalink

熄燈是一個基於網格的難題,其中每個單元格都有兩種狀態:開/關。您可以交換任何單元的狀態,但是當您這樣做時,相鄰的單元(水平或垂直)也將被交換。給定初始具有隨機狀態的網格,目標是將所有單元格設置為關閉狀態。

但是,我從來沒有能夠制定出如何(手動)解決此類難題的策略。通常我最終會隨機切換單元格。 有哪些策略可以解決該遊戲?

此難題有很多變體,但我只對經典難題感興趣。

此拼圖可用於多種網格尺寸。理想但並非必需的是,建議的策略適用於所有網格尺寸。

我通常的(也是有缺陷的)策略試圖從上到下逐行清除。不幸的是,我最終無法清除最後一行,然後我才開始隨機交換單元格,或者只是完全 ragequit


有一個開源程序和稱為 flip 的多平台實現,是 Simon Tatham的Portable Puzzle Collection的一部分。

老實說,這聽起來似乎比我們更適合Math站點。
Gah,我將向您指出Lights Out的實現以獲取更多信息。它可以為您提供任何可以構築的有效配置的解決方案。
@StrixVaria-我也這麼想。我認為這是博弈論。
關於將其移至數學...相信某些問題在多個Stack_something網站中有效。例如,這在數學和遊戲中都有意義。 — @badp:如果您可以從源代碼中提取某種策略,請隨時用簡單的英語進行描述! (是的,我可以查看源代碼,但現在不會查看它)
@Raven:嗯,這當然與數學(算法)有關,但與[博弈論](http://en.wikipedia.org/wiki/Game_theory)無關。它可能最適合[stackoverflow](http://www.stackoverflow.com)(甚至是新的[理論CS站點](http://cstheory.stackexchange.com/)),但絕對不能在此使用。
@BlueRaja-DannyPflughoeft(我什至如何在帖子中給您加上標籤?Oo)誠然,我對遊戲理論的了解很少,但給我的印像是“這是一個獲勝的位置,這將使您更接近獲勝的最終遊戲“是*博弈論。
@BlueRaja:我不想實現一種算法,我只想採用某種策略來手動解決它。因此,它不是用於StackOverflow,當然也不是用於理論CS。
@Raven:您只需要前四個字母即可標記某人。博弈論試圖使用數學對各種情況下的人/動物相互作用進行建模。實際上的例子是[囚徒困境](http://en.wikipedia.org/wiki/Prisoner%27s_dilemma)。 @Denilson:“一種手動解決問題的策略”,您所要求的被稱為算法,或者,如果您僅想了解一般技巧,則可以使用啟發式算法。無論哪種方式,都會在理論CS站點找到研究此類問題以謀生的人。
-1
這適用於該網站嗎? :http://gaming.stackexchange.com/questions/10204/what-are-some-advantages-of-different-usages-of-jokers
八 答案:
Chad Birch
2010-11-18 06:42:38 UTC
view on stackexchange narkive permalink

我將要解釋的方法在技術上適用於任何大小的網格,但是它需要一些我不知道如何從頭確定的知識。如果要在線進行相關搜索,通常將該方法稱為“追光燈”或“追光燈”。頂行上的單元格,然後第三行上的按鈕與第二行中點亮的單元格相對應,依此類推。這正是您已經在做的工作,將燈光追逐到底行,這就是名稱的來源。

現在,您知道,當您有一個除底行以外的空白網格時,棘手的部分就會出現。在這一點上,完成它的方法是在第一行中按下與底部行中點亮的單元格相對應的特定按鈕,然後再次從頂部向下追逐燈光。如果您按了正確的第一排按鈕,那麼當您完成第二次追趕時,難題便會解決。

據我所知,您必須只知道哪些按鈕按下頂行以對應於初始追逐後留在底行上的特定圖案。如果您可以找到確定合適的方法以推到頂部,則可以使用非常相似的方法將其推廣到任何尺寸的網格。但是我不知道這種方法,所以,我將其留給讀者練習。

對於經典的5x5版本的拼圖,事實證明只有最初追踪後,最下面一行中有7種可能的模式,因此我將列出7種可能的模式以及相應的第一行按鈕以按每個模式。按鈕從左到右編號。

  | -------------------- + ---------- ------- ||左下排|頂行|| -------------------- + ----------------- || 1,2,3 | 2 || 1,2,4,5 | 3 || 1、3、4 | 5 |
| 1、5 | 1、2 || 2,3,5 | 1 || 2,4 | 1、4 || 3,4,5 | 4 || -------------------- + ----------------- |  

可以在網上找到其他尺寸的相似查找表。

既然是這種解決方案,我就有一種確定此表的方法:1.分別嘗試嘗試最上面一行中的每個位置,並查看其傳播到的位置。 2.由於這些解決方案堆疊在一起,因此您可以將它們組合起來(例如,可以將它們用作高斯消元中的行)來求解與求解所需集合相對應的線性代數方程。作為一個示例(儘管不是有用的示例;您的表已經具有最小的解決方案),[1,5]由(1,2)解決,[2,4]由(1,4)解決(來自表)。因此,[1,2,4,5]由(2,4)求解。
badp
2010-11-18 06:11:49 UTC
view on stackexchange narkive permalink

我沒有策略,但是以下是有關5×5面板的一些事實:

  • 訂單不計算在內。 A,然後單擊圖塊B與單擊圖塊B,然後單擊圖塊A完全相同,或者先單擊圖塊A,然後單擊圖塊B,再單擊圖塊A,再單擊圖塊A,然後再翻轉圖塊A瓷磚,然後是瓷磚B。
    簡而言之,瓷磚是解決方案的一部分,還是不是解決方案的一部分(必須切換的無序瓷磚集)。一圈又一圈地嘗試相同的動作並不會帶您到任何地方。

    1 unlit cell, 11 moves away.
    如此接近,但到目前為止……

  • 少不了。嘗試最小化點亮/熄滅的細胞數量可能適得其反(請參見上圖)。相反,您應該嘗試將游戲設置為可以通過內存識別和解決的配置。
  • 對稱遊戲具有對稱解決方案。請記住:反映您的動作和遊戲複雜性將大大降低。
  • 解決方案不是唯一的,並且永遠不需要中間的方塊。儘管它可能更容易解決難題,但它出現所有可解決的遊戲都可以在沒有中間位置的情況下解決。
“對稱遊戲具有對稱解決方案”-讓我想起:一位數學教授走進他的教室,發現一個空桶,桌子著火。他仔細估計了情況,按了一下手指,然後抓住水桶。老師把水裝滿,然後把桌子伸了出來。第二天,同一位數學老師再次走進去,發現他的書桌著火了,除了這次,桶裡已經有水了。他思考了一會兒,然後踢開水桶,清空裡面的東西,從而將問題減少到他已經解決的問題上。教授。用桶裝滿水,並保存他的桌子。
@Raven-[工程師/物理學家/數學家]有趣的變化(http://www.farmdale.com/emp-jokes.shtml)笑話
-1
-1
@John也就是說,我很困惑。給定這些空解決方案,您如何解決這個遊戲:[0,0,0,0,0],[0,0,1,0,0],[0,1,1,1,0],[0 ,0,1,0,0],[0,0,0,0,0],您顯然可以通過單擊中心磁貼來解決,這些解決方案無法通過合併這些空解決方案來解決。 (我並不是說您不能。只是想知道其他解決方案是什麼。)
@badp從點亮到熄滅的解決方案是非常不對稱的。也許我還缺少對稱性的其他定義。我的觀點是,對稱遊戲沒有**必須具有對稱解決方案。如您的示例所示,它們可能永遠無法通過考慮對稱解決方案來找到。因此,您需要查看可能的非對稱解決方案。 (我的fermat問題是,即使問題很簡單,解決方案也很糟糕,每個人都在尋找一個不錯的優雅解決方案)
-1
但是,請看與問題和答案相比,解決方案的對稱性要少得多。
我認為5x5熄滅的原因之所以令人著迷,是因為人們尋找對稱的解決方案而失敗。其他尺寸具有更大的對稱性。
Martin Thoma
2011-06-09 22:36:04 UTC
view on stackexchange narkive permalink

以下解決方案適用於每個m×n網格:

將給定網格視為m×n維向量空間中的向量。每個值要么是1(如果燈亮著),要么是0(如果燈滅著)。現在,您可以將每個單元格推入該向量空間中作為一個向量。由於可以推入m x n個不同的像元,因此您有m x n個不同的向量。如果它們更改了單元格中的某些內容,則值為1,否則為0。

如前所述,只有在您必須按下一個按鈕時才有趣。無需查看順序,無需多次按下按鈕。因此,您的網格有一個方程

vector = a_1 x cellvector1 + a_2 x cellvector_2 + ... a_mn x cellvector_mna_1, a_2,...,a_mn為0或1。

由於您擁有mxn變量(a_1 ... a_mn)和mxn方程(向量的行),因此可以使用求解高斯消除法

如果您是德國人,則可能需要閱讀“ Aufgabe 2,30。Bundeswettberwerb Informatik

John Herro
2018-10-05 06:16:37 UTC
view on stackexchange narkive permalink

6x6熄滅的解決方案: b>
6x6拼圖的底行可以包含任何可能的燈光組合。因此,一張桌子,類似於上面為5x5拼圖提供的一個乍得樺木,將包含63行。但是,您可以使用此小桌子解決任何6x6熄燈難題:

  | -------------------- + ----------------- |
|左下排|頂行
| -------------------- + ----------------- |
| 1 | 1、3 |
| 2 | 4 |
| 3 | 1、5 |
| 4 | 2,6 |
| 5 | 3 |
| 6 | 4、6 |
| -------------------- + ----------------- |
 

對於底行上剩餘的任何燈光組合,只需組合上表中的行,請記住兩次按下按鈕與完全不按下按鈕相同。例如,如果底行包含
4、5、6
你會推
2,6,3,4,6
或簡單地
2,3,4,
因為兩個6s取消了。

為什麼這樣做有效?
之所以有效,是因為頂行上的每個按鈕都在底行上切換了一組按鈕(1切換1和5; 2切換2、4和6; 3切換5; 4切換2; 5切換1、3和5和6切換2和6)。可以從中輕鬆得出上表(例如,按1切換1和5,按3切換5,因此按1和3的淨效果僅切換1)。該表起作用是因為每個按鈕的效果相加,並且取消了相同位置的兩個切換。
PaddingtonBear
2014-03-25 16:38:30 UTC
view on stackexchange narkive permalink

在玩不同大小的遊戲時,我發現了一些引起我好奇心的東西。

首先,4 x 4的情況微不足道-追逐亮點,並在第一遍解決。 2 x 2和3 x 3的情況比較瑣碎,但並不十分困難。

第二,9 x 9的情況幾乎是瑣碎的。如果我們將第1列到第9列編號(在我的腦中從左到右,但當然可以),那麼在第一次追逐之後只有兩個結果-要么在第一次通過時就解決了(例如4 x 4情況),要么否則,底行上的正方形是1、3、5、7、9,如果現在單擊頂行中的正方形並將其向下追逐,則可以解決。

7 x 7的情況似乎給出一個非常簡單的策略,使我發現了大約十二個遊戲。第一次追逐最終在底線出現了各種不同的配置-太多了,無法合理分類。但是,在第一次追逐之後,我可以可靠地選擇頂行,如下所示:對於點亮的底行中的每個正方形i,您需要單擊頂行的正方形i-1,i和i + 1。您可以根據該規則單擊它們,也可以將其寫成整行,然後單擊出現奇數次的框-同一件事,但在紙上。之後,追逐方塊並完成工作。顯然,如果正方形1或正方形7點亮,則結果為1,2或6,7,因為沒有0或8。它仍然有效。

在這一點上,我在其他維度嘗試了此策略,6、8、11、12、16-並不能對它們起作用,因此它是7 x 7情況或7 x 7策略所特有的,是更通用方法的特例。

MASMC
2015-05-17 01:49:28 UTC
view on stackexchange narkive permalink

現在,我們只需要帶包裝的4x4解決方案。例如:{0000} {0000} {0000} {0000}按下左上角,您將得到:{1101} {1000} {0000} {1000}是的,我知道我關閉了所有燈,但是一個例子。但是,為了遵循準則,我在這裡使用其他給定的方法檢查了一些7x7解決方案,其中一些是無法解決的。我目前正在為4x4矩陣創建表格,因為我已經找到了一些必須“追光燈”兩次或更多次的地方。

 下面是矩陣形式的示例.0000000000000000頂部左側1101100000001000  

看看我的意思是包裝嗎?隨便問一下,我就會回答包裝新聞的問題。

這可能為時已晚,但是您介意展示一個帶有包裝的解決方案(對於5x5效果會更好!)
Baud2death
2015-07-23 23:53:54 UTC
view on stackexchange narkive permalink

這個難題顯示在DDO任務的裹屍布中,非常容易解決3x3-4x4和5x5

4x4很簡單,因為只需1次即可解決3x3和5x5需要第二次通過指示

第一次通過,只需單擊頂部行上任何亮點下方的切換按鈕即可重複此操作,直到到達底部

對於4x4,您的問題已解決

對於3x3,這將使您在底行中保持亮起狀態,無論是3x3還是5x5,您都只關注左側的底部光點(忽略5x5右側的2個光點)

現在有趣的部分

您將返回到與底部3的亮點所在列相同的頂部行

對於第1列中的亮點,請按切換1和2

對於第3列中的一個,是2和3

對於第2列中的一個,是1,2 & 3

重複即使對每個亮點也是如此,即使這意味著重複切換相同的

所以XX 0將為1、2、1、2、3X 0 X將為1、2、2、3

E tc

然後完成,解決最終的通行證並完成工作

一種完全手動的方法來解決3x3 4x4和5x5難題

Fuk Hu
2014-07-25 06:17:33 UTC
view on stackexchange narkive permalink

我很滿意地證明此處給出的解決方案均無效。實際上,有5x5的情況完全無法解決。這是您自己證明的方法:拿一包紙牌,用紅牌表示燈亮,黑牌表示燈滅,發出矩陣。處理您喜歡的任何大小矩陣,然後嘗試此處提供的技術。我嘗試使用5x5矩陣,但底行與此處發布的不匹配。這意味著使用“跟隨燈光”算法無法解析5x5矩陣。另一個站點聲稱6x6矩陣始終是可解的。同樣,使用上述方法-處理卡片以創建矩陣,並使用“跟隨燈光”算法,我發現使用此技術無法解決的幾種6x6矩陣。您可以找到所有想要的數學,但實際上,此處提供的解決方案不適用於所有矩陣。

這是因為所有遊戲中只有25%可以解決。那些可解決的方法將可以使用該方法解決。

您是說一種策略無效,因為它不能讓您解決難題。最好弄清楚某些熄燈配置是無法解決的,因此它們不是有效的熄燈難題。但是,大概提出的解決熄滅難題的技術旨在用於有效的(即可解決的)難題。


該問答將自動從英語翻譯而來。原始內容可在stackexchange上找到,我們感謝它分發的cc by-sa 2.0許可。
Loading...