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

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

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

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

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

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

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

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

Ответы

Ответ 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/