填字遊戲發電機（瑞典填字遊戲） - Java

我正在嘗試創建一個簡單的Java生成器填字遊戲（瑞典填字遊戲） - 只是爲了好玩。我從網上下載了詞彙單詞（約300,000字）。這些詞我保存在一個HashMap（按字長排序）。發生器的輸入是X和Y的大小以及拼圖。拼圖我隨機插入矩陣填字遊戲發電機（瑞典填字遊戲） - Java

但我不能找出一個工作算法來填補矩陣的其餘部分。

例如：

X X X X 
X D O G 
X X X X

沒有任何人有什麼建議嗎？或者在互聯網上的一些有用的文章？謝謝。

你有什麼，只要填充算法？任何嘗試？ – wumpz

我沒有發明任何東西，我只能將單詞添加到拼圖（在我們的例子DOG），而且不知道 – user3392947

可能重複[算法生成一個縱橫]（http://stackoverflow.com/questions/943113/算法生成一個填字遊戲） –

更新編譯填字遊戲（如瑞典，斯堪的納維亞，等。）這裏的算法描述（除其他外，當然:)）

：發佈算法的主要步驟描述在給定的SO鏈路（每註釋）

該算法的第一步是在隨機選擇一個空wordslot（柵格字）並從其相關聯的單詞表與候選字填充（RA （1）或O（N））
對於每個仍然爲空的單詞槽（與已經填充的單詞槽有交點），計算一個約束率（這可能會有所不同，簡單地說就是該步驟中可用解決方案的數量），並按照該比率（複雜度O（NlogN）或O（N））排序空單詞空間。循環遍歷在先前計算的空單詞步驟，併爲每一個嘗試一些cancdidate解決方案（確保「弧一致性是保留」，即網格有一個解決方案後，這一步，如果這個單詞被使用）和排序他們根據最大可用性下一步（即下一步一步有最大可能的溶膠如果utions這個詞在那個地方使用在那個時候，等..）（複雜度爲O（N * MaxCandidatesUsed））
填補字（標記爲填補，轉到步驟2）
如果沒有發現滿足步驟.3的標準的詞，嘗試回溯到某個先前步驟的另一個候選解決方案（標準可以在此變化）（複雜度O（N））
如果找到了回溯，重置可能需要重置的任何已填充的單詞（將它們標記爲未填充）（複雜度O（N））
如果發現沒有回溯，無溶液可以發現（至少與該結構中，初始種子等）
否則當所有wordlots填充有的話溶液

該算法對問題的解決方案樹執行隨機一致的步驟。如果在某一時刻有死衚衕，它會回溯到前一個節點並沿着另一條路線前進。直到找到的解決方案或用於各個節點的候選人數量都用盡。

一致性部分可確保找到一個解決辦法確實是一個解決方案，並隨機部分能夠產生不同的執行，也的平均不同的解決方案有更好的表現。

PS試圖避免複製粘貼不同的，所以答案之間回的往復，但確定可能是一些總結可能是有用的

2014-05-02 20:25:14

雖然這個鏈接可能回答這個問題，但最好在這裏包含答案的重要部分，並提供供參考的鏈接。如果鏈接頁面更改，則僅鏈接答案可能會失效。 –

@AndrewMedico好的，發佈編輯後，你現在可以刪除否定的投票嗎？如果不是，那麼也許你應該添加你的評論，並等待看看我是否修復這個帖子，如果沒有，然後投票，只要你喜歡，夠公平嗎？ –

我沒有投票。 –

回答