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

Question

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

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

Answer 1

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

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

Боюсь, я не знаю, как писать vb-код.Поскольку вы запросили псевдокод, вместо этого приведу несколько грубых псевдокодов, похожих на python.Я кодирую сетку boggle в виде списка из 16 элементов.Функция neighbors(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".Выделите, скажем, первый из них.(b) игрок вводит "o", код вызывает addletter(ответ, "o") и получает список путей в сетке, на которых написано "go".Опять же, выделите первый из них.