生成填字遊戲的有效算法（NYtime風格）

Question

我想找到一種有效的方法來生成填字遊戲。我已閱讀here提到的解決方案。這產生了一個簡單的填字遊戲，因爲我正在尋找一種高效和優化的方式來生成填字遊戲，如New York times。即當您旋轉180度魔方時，它看起來相同（黑色方塊保留在相同的位置）。在這裏，我們可以假設網格最初是生成的，並且我們可以使用超過三個字母的單詞。

這樣做的最佳方法是什麼？我們可以使用哪種搜索算法來減少迭代次數並使其耗費更少的時間？

Answer 1

我從另一個角度接近了另一個（未完成）文字遊戲的問題。在我的設計中，如果可以在X軸或Y軸（或兩者）上鏡像，就選擇了電路板。

取一個大小爲N的正方形，我建立了所有可能的網格，使用一個位掩碼，以2^cell count -1作爲最大值。所以對於網格2x2（4個單元格），從0 ... 15開始。

0 - 空格

1 - 在頂黑塊左

2 - 黑色塊在右上方

3 - 頂行

在黑色塊。

。

。

15 - 格全黑塊

的顯然這會產生許多非合適人選。我們可以刪除：

• 模式，其中行不中途點 兩側匹配（等向外）爲Y軸鏡像
• 模式，其中列不匹配任何中途 點的一側（等向外），用於在X軸鏡像
• 網格全黑塊
• 模式其中網格的程度（第一行，最後一行，第一 柱，最後列）沒有白色塊
• P （*）

我想我跑到7x7左右，它在一段合理的時間內完成。我沒有得到的是選擇的話。但是，一旦您搗毀了數字，您可以簡單地存儲每個網格大小的所有候選值，然後每次創建新的填字遊戲。

（*） - 對於我寫的遊戲，這很重要，但我不能100％確定這是填字遊戲的必備條件。在電路板的各個部分有2個或更多個不同的白色方塊圖案（但是這是配置的），我想可能是完全有效的。