幫助填字遊戲算法

Question

這樣的問題在我的大學給了我，也許有人會有一個有趣的算法如何解決這個問題。在stackoverflow上有幾種解決方案，但沒有一個是可以的（因爲他們正在循環所有可能性）。

問題：查找所有可能的組合給給定的表格，網格（矩形，見下面的輸入）給定的單詞。應該沒有空閒單元，單詞可以從左到右或從上到下。單詞不能位於連續（列）字中。

輸入：矩形區域，例如：

+-----+ 
| * | 
|  | 
+-----+ 

或

+-----+ 
| * | 
|  | 
| *| 
| * | 
+-----+ 

不同字被輸入隨後後（下一個輸入數據）來填充該網格如：

cdi 
zobxzst 
tdxic 
r 
sc 
zro 
and etc ... 

數字最初是未知的，但輸入直到標準輸入 - 活動EOF結束。

輸出：如果存在一個解決方案，則在填充的網格內輸出該可能的解決方案。 如果沒有解決方案或解決方案的數量，則輸出0或確切的數字。

實施例：

（表輸入）

+-----+ 
| * | 
|  | 
| *| 
| * | 
| * *| 
| * | 
|  | 
+-----+ 

然後詞語cdi zobxzst tdxic r sc zro rgfvacd oikf df x c r xvf ogish za sh fc hh h bfkh

（每個作爲輸入，但在這裏，由空格分開的）（僅1種溶液）

輸出：

+-----+ 
|zro*h| 
|ogish| 
|bfkh*| 
|xvf*r| 
|za*c*| 
|sc*df| 
|tdxic| 
+-----+ 

重要提示：輸入的網格僅受16（！）個單元限制，單詞數量少於60個。我編寫了一個算法，搜索所有可能的組合，但由於執行時間有限，到10秒我猜），這個問題不能用粗略的算法解決（例如， 15格15格，約60！可能或更多可能的排列，可以處理大約1天？在普通的2GHz PC上）。

也許還有另一種獨特的解決方案。也許這個問題在編程時更具數學意義，也許可以使用一些左上角的組合，而不是上下？或者也許加權單元格？

P.S.我有3周的時間來解決這個問題，如果沒有，我可以在3周後發佈解決方案（好消息）;）

Answer 1

在stackoverflow上有幾種解決方案，但沒有一個是好的他們正在循環所有可能性）。

我的想法可能是錯誤的，那麼：但這裏有一個想法，我的頭頂。

我寫了通過所有可能的組合

如果有太多的搜索算法，那麼問題可能是，你也搜索/通過是不可能的組合以及可能的組合循環。

例如，當您在左上角放置一個詞像「的ZrO」，還有可以放置在垂直的話它下面很少有「可能」的組合：

1. 第一垂直字必須以「Z」開始
2. 第二垂直字必須帶「R」
3. 第三垂直字開頭必須以「O」
4. 的第二行字母（從放置垂直得到的組合開始字）本身必須是一個有效的字
5. 等

因此：

1. 挑選任何單詞，並將其放置在左上角
2. 找到滿足上述
3. 約束現有詞如果你發現一個或多個這樣的話，然後繼續這樣看看你是否能解決整件事情;或者，如果你失敗了，然後再次嘗試使用不同的初始字

摘要：

• 不生成每一個完整的網格，然後進行測試，看看它是否滿足所有約束
• 相反使用限制爲您打造的電網，以減少你測試

---

我建議個的可能性的數量在你解決網格問題時，從最初的單詞開始。

而是在左上角測試每個字，一個更好的（例如，因爲它教育部很快消除了不可能的事）的方式產生的起始位置[s]是：

• 查找最長的單詞（如rgfvacd）
• 查找其交叉/加入吧
• 嘗試把每個那些有效組合對電網

Answer 2

我sugges詞所有可能的組合牛逼，你首先應該看你有沒有填寫的話是什麼長度，在你的榜樣：

+-----+ 
| * | 
|  | 
| *| 
| * | 
| * *| 
| * | 
|  | 
+-----+ 

你有兩個7字母的單詞，三個1個字母的單詞，等等。

您應該根據計數對這個列表進行排序，並且首先嚐試用最低計數的長度，在下一次迭代中，您應該列出您需要查找的單詞列表 - 三個4個字母的單詞開始用'a' - 你應該計算你在單詞列表中留下了多少這些單詞，然後選擇一個單詞中包含最少單詞的單詞 - 如果它是0，則返回。

希望它是有道理的。