由网友(夜裡看江南)分享简介：在我写一些关于这个问题，我需要让大家知道的：Before I write something about the problem, I need to let you know:在这个问题是我的功课（我有1周左右返回工作程序）在我工作的这个问题，大约一个星期，每一天，试图找出自己的解决方案在我没有要求完整的程序;...

在我写一些关于这个问题，我需要让大家知道的：

Before I write something about the problem, I need to let you know:

在这个问题是我的功课（我有1周左右返回工作程序） 在我工作的这个问题，大约一个星期，每一天，试图找出自己的解决方案 在我没有要求完整的程序;我需要一个总体思路对算法

问题：

假设：一个词表和一个网格，例如：

Given: a wordlist and a "grid", for example:

栅格（X表示任何字母）：

grid (X means any letter):

X X 
XXXX
X X
XXXX

单词表：

ccaa
baca
baaa
bbbb

您必须找到如解决方案 - 这可能适合从词库的话到给定格？如果至少有一个解决方案，打印一（取正确的）。如果没有 - 打印信息，不存在可能的解决方案。对于给定的例子，有一个解决方案：

You have to find example "solution" - is it possible to fit words from wordlist into a given grid? If there is at least one solution, print one (whichever correct). If no - print message, that there is no possible solution. For given example, there is a solution:

b c 
baca
b a 
baaa

这是我很难写的一切，我已经尝试过（因为英语不是我的母语，我也有很多与纸的错误的意见）。

我的幼稚的算法的工作原理是这样的：

My naive algorithm works something like this:

第一个字只是需要适当长度，如此狼狈不堪（第一？）这个词用的正确的长度（我将使用给出的例子电网和单词表来证明我的想法）：

First word needs just proper length, so find any (first?) word with proper length (I'm going to use given example grid and wordlist to demonstrate what I think):

c X 
cXXX
a X
aXXX

有关第一的通用的函（在2个字路口）找到任何（第一）的话，适合电网（所以，有适当的长度和通用信于适当的位置）。如果没有这样的话，回去（1），并采取另一种第一个字。在原单的例子，没有哪个词以C开头，所以我们回去（1），选择下一个单词（此步骤重复几次，直到我们有BBBB的第1个字）。现在我们有：

For first common letter (on the crossing of 2 words) find any (first) word, that fit the grid (so, have proper length and common letter on proper position). If there is no such words, go back to (1) and take another first word. In the orginal example there is no word which starts with "c", so we go back to (1) and select next words (this step repeats few times until we have "bbbb" for 1st word). Now we have:

b X 
bXXX
b X
bXXX

我们正在寻找一个字（县），其中以B开头，例如：

And we're looking for a word(s) which starts with "b", for example:

b X 
baca
b X
bXXX

一般过程：尽量找单词对其中的配合的给定网格。如果没有这样的话，再回到previous步骤，并使用另一组合 - 如果没有这样的 - 有没有办法解决

General process: try to find pairs of words which fit to the given grid. If there is no such words, go back to previous step and use another combination - if there is no such - there is no solution.

以上一切混乱，我希望你至少了解问题的说明。我写了一个算法的草稿，但我不知道是否可行以及如何正确地$（在我的情况：C ++）C $ C这一点。此外，还有一些情况下（甚至在上面的例子），我们需要找到一个词的依赖的2或多个其他词。

Everything above is chaotic, I hope that you understand at least problem description. I wrote a draft of an algorithm, but I'm not sure if that works and how to properly code this (in my case: c++). Moreover, there are cases (even in example above) that we need to find a word that depends on 2 or more other words.

也许我只是不能看到的东西很明显，也许是我太傻了，也许......嗯，我真的想解决这个问题。我不懂英文足够好，precisely描述我如何看待这个问题，所以我不能把这里所有我的笔记（我试图描述一个想法，这是硬的）。信不信由你，我花很多时间试图找出解决方案，我几乎什么都没有......

Maybe I just can't see something obvious, maybe I'm too stupid, maybe... Well, I really tried to solve this problem. I don't know English well enough to precisely describe what I think about this problem, so I can't put here all my notes (I tried to describe one idea and it was hard). Believe or not, I've spend many long hours trying to figure out solution and I have almost nothing...

如果你能描述一个解决方案，或者给一个提示怎么解决这个问题，我真的AP preciate这一点。

If you can describe a solution, or give a hint how to solve this problem, I would really appreciate this.

推荐答案

该corssword问题是 NP完全 ，所以你最好的拍摄是蛮力：只是尝试所有的可能性，并停止时，可能是有效的。返回失败，当你用尽所有可能的解决方案。

The corssword problem is NP-Complete, so your best shot is brute force: just try all possibilities, and stop when a possibility is a valid. Return failure when you exhausted all possible solutions.

减少可以证明这个问题是NP完全可以在这篇文章被发现第3.3节

reduction that prove that this problem is NP-Complete can be found in this article section 3.3

使用回溯可能是蛮力解决方案：伪code]：

Brute force solution using backtracking could be: [pseudo code]:

solve(words,grid):
   if words is empty:
       if grid.isValudSol():
          return grid
       else:
          return None
   for each word in words:
       possibleSol <- grid.fillFirst(word)
       ret <- solve(words{word},possibleSol)
       if (ret != None):
          return ret
   return None

在这里，我们假设 fillFirst（）是一个函数，填补这是不是已经充满[第一实际上是空舱的任何一致排序的第一个空间，但它应该是一致的！]，和的isValid（）返回一个boolean值，指示给定格是一个有效的解决方案。

in here we assume fillFirst() is a function that fills the first space which was not already filled [first can actually be any consistent ordering of the empty spaces, but it should be consistent!] , and isValid() is returning a boolean indicating if the given grid is a valid solution.