如何获得一个填字游戏的多个解决方案？

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的时间）