算法：解決字謎給出的單詞

我看着類似的問題前面的問題的列表，但我有與此相關的算法一個具體的問題。問題陳述（https://www.hackerrank.com/challenges/crossword-puzzle/problem）如下：算法：解決字謎給出的單詞

提供了一個10x10 Crossword網格，以及需要填充到網格中的一組單詞（或地名）。網格中的單元格最初是+符號或 - 符號。標有+的單元必須保持原樣。標有「 - 」的單元格需要填入適當的字符。

樣品輸入：

+-++++++++ 
+-++++++++ 
+-++++++++ 
+-----++++ 
+-+++-++++ 
+-+++-++++ 
+++++-++++ 
++------++ 
+++++-++++ 
+++++-++++ 
LONDON;DELHI;ICELAND;ANKARA

通訊輸出：

+L++++++++ 
+O++++++++ 
+N++++++++ 
+DELHI++++ 
+O+++C++++ 
+N+++E++++ 
+++++L++++ 
++ANKARA++ 
+++++N++++ 
+++++D++++

我做寫出的算法沒有完全理解這個問題，在這裏我只是把下一個字符一個空的錯誤現場解決迷宮的方式（這裏是我的代碼）：

def populate_grid(maze, locations) 
    maze.each_index do |row| 
     maze[row].each_index do |col| 
      if maze[row][col] == "-" 
       maze[row][col] = locations.first[0] 
       if locations.first.length == 1 
        locations.shift # remove this location altogether 
       else 
        locations[0] = locations[0][1...locations.first.length] 
       end 
       populate_grid(maze, locations) 
      end 
     end 
    end 
end

Un幸運的是，這個問題沒有提供解決方案，我想知道如何爲每個單詞建立一致的方向性（例如只沿水平/垂直方向）。我想過使用一個3參數作爲布爾值來判斷這個單詞是上升還是下降，但這對我來說似乎不可行。

任何人有怎樣保存方向性的想法？

來源

2017-07-13 Sunny

您可以使用遞歸來解決問題。在每個可行位置放置第一個單詞。對於每一個，將第二個單詞放在每個可行的位置。對於第一個和第二個的每個配對，將第三個單詞放在每個可行位置。遞歸方法可能寫成'recurse（partially_filled_crossword，remaining_words）'，這兩個參數都是數組，返回一個表示完成字符串的數組（array）;如果沒有有效的完整字符串存在，那麼搜索樹的該部分就不存在。 –

一般情況下，你需要用的詞彙來當作字單位，並辦理網（這是cruciverbalist的任期爲您maze）與程序插入整個單詞爲單位。

你需要「分析」電網識別所有可用的位置。寫一個函數到match一個單詞到一個可用的位置，反之亦然。一個位置由起始方塊（行，列），方向（布爾）和字母圖案（空白，除了交叉字已填入的位置）組成。 match將考慮字長任何方格已經填寫。

現在，你可以遍歷將依次對每個字，或填充每個網格位置。致電match，直到找到填寫單詞的地方。如果您找不到，當前的網格填充不會導致解決方案;回溯一個詞，然後再試一次。當你找到一個點時，填寫單詞（另一個函數），用現在填充的字母更新任何交叉點位置，然後轉到迭代中的下一個單詞或位置。

如果成功到達終點，你有一個完整的拼圖。

這讓你感動嗎？

來源

2017-07-13 21:33:37 Prune

代碼會使這個更有用的答案。 –

@CarySwoveland：我覺得設計數據結構和提供工作代碼將遠遠超出SO的通用目的。我同意OP所發佈的代碼是無效的攻擊;一個適當的改變是一個大的改寫。 – Prune

我不是在批評你的回答，只是指出代碼對OP和其他讀者更有幫助。人們經常看到的答案可能會被視爲「遠遠超出SO的一般目的」，但仍然值得讚賞。 –

算法：解決字謎給出的單詞

回答

相關問題