單詞搜索算法

我試圖想出一個比「蠻力」方法更好的方法，但在某種程度上是一種損失。單詞搜索算法

下面是一個簡單的例子：

鑑於預選擇的字母有限數，和一個艙口（像一個縱橫重疊），我試圖找到詞語的所有組合都可以使用。（字被從字典數據庫中檢索。）

實施例：

鑑於字母：
A，C，R，E，T，U，P，L，M，O
多少組合的話可以適應以下填字遊戲？

_ 
_ _ _ _ 
    _ 
    _ 
    _ _ _

一個例子：

c 
t r e e 
    e 
    e 
    p o t

當然顯着地與每個字母或除字謎艙口搜索時間增加。任何更好的搜索方式的建議？

來源

2011-09-09 kylex

我可以用'sed's | /.* ||'來減少62 000個單詞的字典/var/cache/postgresql/dicts/en_us.dict | egrep「^ [acretuplmo] {3,5} $」|在第一次粗略剪切中，用566個單詞。但我很好奇：你使用4次'e'，但沒有使用'a'。這樣好嗎？ –

是的，單詞是使用提供的任何字母創建的（每個字母可以多次使用） – kylex

查看開放源代碼arccc，填入縱橫填字網格，將它們視爲constraint satisfaction problem。如果你想自己做一個學習練習，閱讀CSP應該是一個很好的起點。

至於限制字母表，最好在源詞典上作爲預處理步驟完成。

來源

2011-09-09 02:57:35

單詞搜索算法

回答

相關問題