如何獲得一個填字遊戲的多個解決方案？

Question

我已經看到了這個論壇和不同的問題。

但我想問一些不同的東西。 我有兩個不同的詞的單詞表和一個由0和1指定的網格。 我將不得不從單詞表1中選擇單詞，對於列選擇單詞2。

主要問題是我必須在給定的時間限制內找到多個解決方案。有人可以建議我一些很好的算法。我沒有得到什麼樣的算法應該採取。

另一件事， 我有兩種語言選項。無論是C++或Java這將是更好的實施。

謝謝

Answer 1

您可以使用一種叫做Dancing Links or DLX算法。這是解決精確覆蓋問題的極其有效的算法。

有幾個程序用來解決數獨謎題。

• http://www.ocf.berkeley.edu/~jchu/publicportal/sudoku/sudoku.paper.html

老實說，我不知道有足夠的瞭解精確覆蓋問題，說這一定會爲您的需要工作，但它是值得考慮看看。

Answer 2

當做一個字謎時，通常會發現自己尋找一定長度的單詞，並在某個特定位置放上某個字母。所以，你可能會想這樣的函數：

List<String> findWord(int ofLength, char withLetter, int atIndex) {/*implementation*/} 

這可能可以使用一組預構建包含HashMap的快速產生一組候選人。 （您可能還希望能夠跟蹤單詞是否已經在填字遊戲中使用了......假設重複項不被允許）

人們做的其他事情是猜測使用提示。我認爲你可能不是在尋找強大的AI，所以這會導致蠻力算法...在這種情況下，試着填寫以最大單詞開頭的填字遊戲，因爲那裏的可能性通常較少。

骨架算法：

private void checkPuzzleOn(Row row, SolutionSet s) { 

    List<Row> crossingRows = row.getCrossingRows(); 

    if(allAlreadyFilled(crossingRows)) { 
     //This part of the crossword works; store info in solution set. 
     return; 
    } 

    crossingRows.sortBiggestToSmallest(); 

    foreach(Row crossing in crossingRows) { 

     int index = row.getIndexOfIntersectionWith(crossing); 
     char c = row.charAt(index); 

     List<String> candidates = findWords(crossing.length, c, index); 
     foreach(String candidate in candidates) { 
      verifyAgainstPresentWords(crossing, candidate); //check that using this word won't collide with others; important because of cycles. 
     } 

     if(candidates.isEmpty()) { 
      //This part of the crossword won't match! store info in solution set. 
      return; 
     } 

     foreach(String candidate in candidates) { 
      crossing.setWord(candidate); 
      checkPuzzleOn(crossing, s); 
     } 
    } 
} 

Answer 3

我found a solution that does what you want。可悲的是我不能讚揚它:)

這是一個例子。你給它一個模式文件，如pattern1：

## ##  
    #  #  
    #  #  
      # 
### ### ## 
#  #  # 
    #  #  
    #  #  
    #  # 
#  #  # 
## ### ### 
    #   
    #  #  
    #  #  
    ## ##  

你可以調用它上面的程序，所以：

./cword pattern1 /etc/dictionaries-common/words 

輸出是

SODS##HOG##AMPS 
APIA#RADON#LAUE 
TESS#ALONE#ERNA 
ENCHANTRESS#GYM 
###ADS###TUTU## 
#PAYDAY#ESPIES# 
REV#SCALD#SCRIP 
ARON#KNOWS#SITE 
MCCOY#KNITS#TET 
#HARASS#NAPPED# 
##TACT###DIE### 
MCI#COORDINATES 
ELOY#AMARU#ROLL 
SINE#TARIM#LIMA 
SOSA##REP##SLOT 

或者運行其他時間：

PAWN##HOT##BEST 
OLEO#SURYA#OMAR 
LOAN#AGAPE#ABLE 
SELFISHNESS#RTE 
###ASH###OKAY## 
#KATMAI#EPILOG# 
INN#SYNOD#MULES 
SETH#SCHWA#MONA 
MEIER#AMIDS#GEM 
#SPLATS#NOWAYS# 
##APSE###RAY### 
WIS#PATRONYMICS 
ALTA#CHOKE#AREA 
SLOP#HEARD#ROBS 
PSST##ERA##ANUS 

當然，具有較大的圖案或小的生詞您的里程可能會有所不同（瘋狂）。我能夠做1000代26.5秒一個Q9550處理器，採用

time for a in $(seq 1 200) 
do 
    for a in 1 2 3 4 5 
    do 
     ./cword pattern1 /etc/dictionaries-common/words | md5sum& 
    done 
    wait 
done | sort | uniq -c | sort -n | tee >(wc -l) 

輸出證實，這些實際上是1000個獨特解決方案。不錯，如果你問我。 （時間包括計算每個解決方案的md5sums的時間）