Алгоритм кроссворда с заданной сеткой

Прежде чем написать что-нибудь о проблеме, я должен сообщить вам:

Эта проблема - моя домашняя работа (у меня было около 1 недели, чтобы вернуть рабочую программу)
Я работал над этой проблемой около недели, каждый день, пытаясь выяснить свое решение.
Я не прошу полной программы; Мне нужно общее представление об алгоритме

Проблема:

Учитывая: список слов и "сетка", например:

сетка (X означает любую букву):

X X 
XXXX
X X
XXXX

словник:

ccaa
baca
baaa
bbbb

Вы должны найти пример "решение" - возможно ли вставить слова из списка слов в заданную сетку? Если есть хотя бы одно решение, напечатайте его (в зависимости от того, что правильно). Если нет - печатать сообщение, то нет возможного решения. Для данного примера существует решение:

b c 
baca
b a 
baaa

Мне тяжело писать все, что я уже пробовал (потому что английский не мой родной язык, и у меня также много документов с неправильными идеями).

Мой наивный алгоритм работает примерно так:

Первое слово требует только правильной длины, поэтому найдите любое (первое?) слово с правильной длиной (я собираюсь использовать данную примерную сетку и список слов, чтобы продемонстрировать, что я думаю):
```
c X 
cXXX
a X
aXXX
```
Для первой общей буквы (на пересечении 2-х слов) найдите любое (первое) слово, которое соответствует сетке (таким образом, имеет надлежащую длину и общую букву в правильном положении). Если таких слов нет, вернитесь к (1) и произнесите другое первое слово. В оригинальном примере нет слова, которое начинается с "c", поэтому мы возвращаемся к (1) и выбираем следующие слова (этот шаг повторяется несколько раз, пока у нас нет "bbbb" для 1-го слова). Теперь мы имеем:
```
b X 
bXXX
b X
bXXX
```
И мы ищем слово (слова), которое начинается с "b", например:
```
b X 
baca
b X
bXXX
```
Общий процесс: попытайтесь найти пары слов, которые соответствуют заданной сетке. Если таких слов нет, вернитесь к предыдущему шагу и используйте другую комбинацию - если таковой нет - решения нет.

Все вышеизложенное хаотично, я надеюсь, что вы поймете хотя бы описание проблемы. Я написал проект алгоритма, но я не уверен, что это работает и как правильно его кодировать (в моем случае: С++). Более того, есть случаи (даже в примере выше), что нам нужно найти слово, которое зависит от двух или более других слов.

Может быть, я просто не вижу ничего очевидного, может быть, я слишком глуп, возможно... Ну, я действительно пытался решить эту проблему. Я не знаю английского достаточно хорошо, чтобы точно описать, что я думаю об этой проблеме, поэтому я не могу поставить здесь все свои заметки (я попытался описать одну идею, и это было сложно). Верьте или нет, я потратил много долгих часов, пытаясь найти решение, и у меня почти ничего нет.

Если вы можете описать решение или дать подсказку, как решить эту проблему, я бы очень признателен этому.

Ответ 1

Проблема corssword NP-Complete, поэтому ваш лучший снимок - это грубая сила: просто попробуйте все возможности и остановитесь, когда есть возможность действительный. Возврат отказа, когда вы исчерпали все возможные решения.

которые доказывают, что эта проблема NP-Complete можно найти в в этой статье, раздел 3.3

Решение грубой силы с использованием backtracking может быть: [псевдо-код]:

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, указывающий, является ли данная сетка допустимым решением.

Ответ 2

Сегодня утром я написал прогам. Вот несколько более эффективная версия в псевдокоде:

#pseudo-code
solve ( words , grid ) : solve ( words , grid , None ) 

solve ( words , grid , filledPositions ) :
    if words is empty :
        if grid is solved :
            return grid
        else :
            raise ( no solution )
    for ( current position ) as the first possible word position in grid 
            that is not of filledPositions :
        # note : a word position must have no letters before the word
            # 'before the word' means, eg, to the left of a horizontal word
            # no letters may be placed over a ' ' 
            # no letters may be placed off the grid
        # note : a location may have two 'positions' : one across , one down
        for each word in words :
            make a copy of grid
            try :
                fill grid copy, with the current word, at the current position
            except ( cannot fill position ) :
                break
            try :
                return solve ( words\{word} , grid copy , 
                        filledPositions+{current position} )
            except ( no solution ) :
                break
        raise ( no solution )

Вот мой код для подгонки слова по горизонтали в сетке: http://codepad.org/4UXoLcjR

Вот некоторые вещи, которые я использовал в STL:

http://www.cplusplus.com/reference/algorithm/remove_copy/

http://www.cplusplus.com/reference/stl/vector/