Алгоритм поиска слов на доске Boggle - PullRequest
Новая
       30

Алгоритм поиска слов на доске Boggle

0 голосов
/ 06 августа 2009

Я создаю потрясающую игру в vb .net. Прямо сейчас мои кубики в виде двумерного массива (0,0 0,1) и т. Д.

Что я хочу сделать, так это, когда я набираю слово, оно подсвечивает его на доске с помощью подпункта button(x,y).doclick, который выделяет его. Прямо сейчас моя реализация находит первую букву, затем продолжает пробовать каждую букву, пока она не удовлетворяет условию 8 углов (т.е. она соседствует с последней), но это не всегда работает. Если на доске написано 2 "G", а я хочу нижнюю, это не сработает. Может кто-нибудь дать мне пример psuedocode того, что должно произойти. Я был в тупике почти 6 часов, пытаясь понять это. Спасибо

1 Ответ

2 голосов
/ 06 августа 2009

Если я правильно понимаю, учитывая строку, вы хотите выделить один путь через кубик, который соответствует строке. Иногда есть несколько возможных вариантов, поэтому добавление буквы может полностью изменить то, что выделено. Это может быть хорошим подходом для сохранения результатов из предыдущей подстроки, поэтому нам не нужно начинать сначала. Тогда разумно было бы вычислить все возможные пути.

Ответом для заданной строки s будет список путей, где путь - это список координат сетки. Каждый путь - это то, что вы могли бы разумно выделить, поэтому просто выделите первый. При добавлении буквы в строку вы найдете пути, которые вы можете развернуть, и удалите пути, которые вы не можете развернуть.

Боюсь, я не знаю, как написать код VB. Так как вы попросили псевдокод, вместо этого вот вам грубый псевдокод, похожий на python. Я кодирую решетчатую сетку как список из 16 предметов. Функция соседей (x) возвращает список соседних позиций (за исключением крайних случаев, которые будут [x-1, x + 1, x-4, x + 4]). 

def firstLetter(typed):
  answer = []
  for pos in range(16): if grid[pos]==typed: answer += [pos]
  return answer

def addletter(partialanswer, typed):
  answer2 = []
  for partial in partialanswer:
      for neighbor in neighbors(partial[-1]):
          if grid[neighbor]==typed: 
             # partial+[neighbor] is a list. answer2 is a list of such lists.
             answer2 += partial + [neighbor]
  return answer2

Если игрок набирает «go», например, тогда (a) игрок набирает «g», код вызывает firstletter («g») и получает список «ответов» о позициях в сетке, в которых есть «g». Выделите, скажем, первый. (б) игрок набирает «o», код вызывает addletter (answer, «o») и получает список путей в сетке, которые говорят «go». Снова выделите первый.

...