在Prolog中解決七巧板拼圖的好方法是什麼？

我不確定這個最好的屬於這裏還是數學，但我想我可以在這裏得到一些關於代碼的指針。對於一個作業，我需要使用Prolog解決凸Tangram puzzles。在Prolog中解決七巧板拼圖的好方法是什麼？

所有的謎題和可用的片段被定義爲頂點列表。例如： puzzle(1,[(0,0),(4,0),(4,4),(0,4)])代表一個方形拼圖，而piece(1,[(0,0),(4,0),(2,2)])可能是一個大三角形。

我已經定義了所有7個元素和一個點列表，我想我應該能夠編寫正確的代碼來遍歷這些元素並對它們執行一些操作。然而，當我談到幾何時，我並不那麼富有洞察力，所以我不知道如何才能確定哪個部分適合於基於其頂點的拼圖。

本課程中的大部分任務均基於經典的組合問題，如旅行推銷員。是否有任何涉及凸形（或任何形狀）的問題可能激發我想出一個解決方案？我很難找到以這種方式處理形狀的在線聲明性代碼示例。如果我知道要尋找什麼，這將非常有幫助。

我想我可以驗證解決方案是否正確，方法是檢查拼圖的外部邊界是否覆蓋一次，內部（由放置棋子產生的）覆蓋兩次。我可以將這個事實作爲我的解決方案的一部分的基本案例。除此之外，我現在能想到的最好的辦法就是蠻橫逼迫每一塊物品進入難題邊界之間的一個空閒空間，直到它們合適爲止。

來源

2011-11-08 Lawyerson

實現蠻力解決方案，然後重構使用CLP（FD）謂詞通常是解決這類問題的好方法。 –

設計問題是爲了減少對離散（有限）搜索空間的可能位置。某些部分比其他部分具有更多對稱性，這可能有助於減小搜索空間的大小，但頂點位置和方向始終受限於一組連續的值。我喜歡沿着邊界放置人物的想法，這會導致小面積區域的一系列邊界。我曾想過其他形狀的「解剖」問題，其中一種離散化放置可能性的方式更爲明顯。 – hardmath

我認爲解決這個問題的關鍵應該是檢測件的重疊。根據定義，如果沒有重疊發生，每個可接受的放置將是一個解決方案。然後，迭代一塊'放置，我們應該檢測是否有重疊發生。

每個形狀都可以表示爲單位網格細分產生的最小三角形的聯合。我們共有100（4 * 5 * 5）個小三角形。

因此，當我們將一系列的座標轉換爲小三角形列表時，可以很容易地通過交集來檢測重疊。

例如，按照遞增的座標和順時針編號，piece(1, [(0,0), (1,1), (2,0)])變爲[2, 3, 4, 7]。

如果我們注意到每次旋轉X'= Y和Y'= - X，則圍繞原點順時針旋轉90°的形狀很容易。上面的片段順時針旋轉90°：片段（1，[（0,0），（1，-1），（0，-2）]）。當在Y：piece（1，[（0,2），（1,1），（0,0）]）上歸一化時。

確定哪些小三角形覆蓋形狀可以天真地重複每個小三角形的'point in polygon'測試。

來源

2011-11-11 15:41:00 CapelliC

謝謝你的回答。你對旋轉形狀的解釋和在多邊形測試中提出的要點幫助我想出了一個解決方案。 – Lawyerson

您是否必須用純Prolog解決問題，還是可以使用約束編程？

如果你可以使用CP，那麼看看這篇文章：Perspectives on Logic-based Approaches for Reasoning About Actions and Change。第6節描述了作者如何用CLP（FD）解決七巧板問題。

也許論文給你一個想法，即使你必須使用純Prolog，如何解決它，因爲約束可以被被動測試所取代。然而，搜索將花費更長的時間，因爲搜索樹不會被約束脩剪。

我還記得很久以前，我在一個CLP課程中學過一個人，他使用Gröbner基地來推理幾何（「如何在緊密的角落移動鋼琴？」），儘管我不確定這是否適用爲了解決七巧板。

對不起，如果這一切都有點理論和先進。

來源

2011-11-09 07:32:25 twinterer

在Prolog中解決七巧板拼圖的好方法是什麼？

回答

相關問題