我正在嘗試開發一個程序來解決C中的魔方問題。我使用了反向追蹤技術。這是一個非常漫長的過程，需要大量的迭代，所以我無法解決它。以編程方式解決魔方問題

請給我關於如何更有效地解決這個問題的建議 - 比如其他技術或採用回溯本身。在谷歌我發現了很多解決這個問題的捷徑，但我不想通過使用快捷方式來解決這個問題。

來源

2011-04-06 Aravindhan

你所說的「快捷方式」意思？ – 2011-04-06 08:47:36

http://www.chessandpoker.com/rubiks-cube-solution.html看到這個鏈接..在這裏他們將在5分鐘內解決這個問題。 – Aravindhan 2011-04-06 08:49:25

您是否介意修改您的問題以包含更清楚地說明您當前方法的代碼？爲了清晰起見，我已經編輯了一些問題。 – 2011-04-06 08:58:00

爲什麼不使用以人爲本的解決方案並對其進行編程。

你需要一些模式匹配，但它不會那麼難。（除了有解決1000x1000x1000的程序）。

的基本思想是在階段的工作：對於每個層要實現一對夫婦的算法，把模型X

第一層
第二層
第三層

到模式X'中。階段中的每一步都應該使立方體接近解決。您可以通過爲每個模式添加一個值來實現這一點（更高的值賦予更多未解決的多維數據集）。您還可以添加一個難度（例如轉數），以便您可以根據每個難度的最佳值增益選擇算法（或以最小轉數達到最佳結果）。

這種方法的好處是，如果你喜歡，你可以添加新的算法，並測試它們的使用頻率。所以你可以測試每種算法的有用性。

如果您確實想要獲得這些geekpoints，請創建一種單獨的語言來描述算法和他們正在解決的模式。

來源

2011-04-06 08:55:25

對於較大的立方體來說，比逐層更好的方法是解決中心然後邊緣問題，最終解決由此產生的3x3x3 – hoang 2012-10-30 15:42:09

這是可以通過DP來解決的嗎？ – pranavk 2012-12-24 08:42:29

@pranavk這取決於[什麼DP意味着]（https://en.wikipedia.org/wiki/DP#Technology）。 – 2014-04-27 01:17:04

我不確定我是否理解你的問題，以及你的意思是什麼。如果您正在使用一些動態編程方法來解決rubik的立方體，那麼您需要確保您正在尋找足夠的步驟才能找到解決方案。我相信，如果您只支持兩種類型的移動（向右旋轉，向上旋轉），則需要在確定每一步之前查看12個步驟（未知），以確保解決方案。

如果您正在做這樣的事情，並且您發現內存空間不足，那麼請記住，您只需要保留要穿過的路徑，以便決定正確的解決方案（而不是整個樹）。

我用這種方法成功地解決了Java中的rubik's cube，所以C應該沒有問題（就內存佔用情況而言）。

來源

2011-04-06 08:56:55 Asaf

有很多算法來解決魔方問題，但是，你可以參考這個最佳的一個 http://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik's_Cube

來源

2011-04-06 09:03:22 nicola

魔方具有在2 訂單狀態空間的大小。一種盲目搜索狀態空間的回溯算法可能需要在找到解決方案之前檢查大部分狀態空間，因此顯然，簡單的回溯算法不能很好地工作。但是，這個問題已經解決了很多次了。見例如http://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf

來源

2011-04-07 04:53:38

如果你不關心此舉涉及的數量，這裏是分裂的狀態空間，使您的bruteforces方法的工作方式。

找到適合假人的Rubix立方體的解決方案

首先暴力破解所有的Rubix方面，但邊角到地方
然後找到舉動，讓不變放入系統方面（例如，（FGF-1.G-1）^3）。兩招實際上就足夠了。爲了找到它們，考慮包含角落和非角落子骰子的置換，然後迭代拐角周長的ppcm以得到並且在角落上不變）
使用你的回溯算法來獲得角落（但它們仍然需要旋轉，對齊顏色）
發現魔術的舉動，使得以立方體在同一網段一起轉動。沒有舉動

來源

2011-04-17 13:54:41 fulmicoton

以編程方式解決魔方問題

回答

找到適合假人的Rubix立方體的解決方案

相關問題