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

Question

Прежде чем написать что-то об этой проблеме, мне нужно, чтобы вы знали:

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

Проблема:

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

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

X X 
XXXX 
X X 
XXXX 

словник:

ccaa 
baca 
baaa 
bbbb 

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

b c 
baca 
b a 
baaa 

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

Мой наивным алгоритм работает что-то вроде этого:

1. Первое слово, нужно только правильную длину, так что найти (первая?) Слово с правильной длины (я буду использовать данный пример сетки и словник, чтобы продемонстрировать то, что я думаю):

   c X 
   cXXX 
   a X 
   aXXX 
   

2. для первого общего письма (на пересечении 2-х слов) найти любое (первое) слово, которое соответствует сетке (так, иметь надлежащую длину и общее письмо на правильное положение). Если таких слов нет, вернитесь к (1) и произнесите другое первое слово. В оригинальном примере нет слова, которое начинается с «c», поэтому мы возвращаемся к (1) и выбираем следующие слова (этот шаг повторяется несколько раз, пока у нас нет «bbbb» для 1-го слова). Теперь мы имеем:

   b X 
   bXXX 
   b X 
   bXXX 
   

   И мы ищем слово (а), который начинается с «Ъ», например:

   b X 
   baca 
   b X 
   bXXX 
   

3. Общий процесс: попытаться найти пары слов, подходит к данной сетке. Если таких слов нет, вернитесь к предыдущему шагу и используйте другую комбинацию - если таковой не существует - решения нет.

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

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

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

Answer 1

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

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

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

Answer 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/